首页 > 分享 > 牛客小白月赛105 (Python题解) A~E

牛客小白月赛105 (Python题解) A~E

花匠小妙招
2025-09-21 19:52

牛客小白月赛105 (Python题解)

比赛链接：点击传送

A-lz的吃饭问题

代码：

a, b = map(int,input().split()) c, d = map(int,input().split()) print("gzy") if a*b >= c*d else print("lz")

B-lz的数字问题

代码:

def func(a1, b1): a_int, a_frac = (a1 + '.0').split('.')[:2] b_int, b_frac = (b1 + '.0').split('.')[:2] if a_int != b_int: return "NO" a_frac = (a_frac + "000000")[:6] b_frac = (b_frac + "000000")[:6] return "YES" if a_frac == b_frac else "NO" a, b = input().split() print(func(a, b))

C-lz的蛋挞问题

1.问题重述:

1.1.背景:

一个两行 n 列的盒子中有两种物品：蛋挞（.）和奶贝（x），蛋挞之间如果在上下左右四个方向相邻，就可以连通，连通块是指一组可以相互连通的蛋挞。

1.2.要求:

可以吃掉一个蛋挞，并在原位置放置奶贝，找出吃掉后能改变蛋挞连通块数量的蛋挞个数。

2.求解思路：

2.1.核心思路:

遍历每个蛋挞位置

判断吃掉该蛋挞是否会改变连通块数量

设计4种判断条件

2.2.四种判断条件详解：

左侧连通性改变

j > 0 and m[i][j] == m[1-i][j] == m[i][j-1] != m[1-i][j-1]

检查左侧相邻蛋挞是否形成特定连通模式，同行和对行的蛋挞值相同，与左下/左上蛋挞值不同

右侧连通性改变

j + 1 < n and m[i][j] == m[1-i][j] == m[i][j+1] != m[1-i][j+1]

检查右侧相邻蛋挞是否形成特定连通模式，同行和对行的蛋挞值相同，与右下/右上蛋挞值不同

三连通情况

j > 0 and j + 1 < n and m[i][j-1:j+2] == '.' * 3 and m[1-i][j] == 'x'

当前行有连续三个蛋挞，对应行为奶贝

孤立点情况

(j == 0 or m[i][j-1] == 'x') and (j + 1 == n or m[i][j+1] == 'x') and m[1-i][j] == 'x'

当前蛋挞左右被奶贝包围，对应行为奶贝

3.代码:

n = int(input()) m = [input() for _ in range(2)] ans = 0 for i in range(2): for j in range(n): if m[i][j] == 'x': continue conditions = [j > 0 and m[i][j] == m[1-i][j] == m[i][j-1] != m[1-i][j-1],j + 1 < n and m[i][j] == m[1-i][j] == m[i][j+1] != m[1-i][j+1],j > 0 and j + 1 < n and m[i][j-1:j+2] == '.' * 3 and m[1-i][j] == 'x',(j == 0 or m[i][j-1] == 'x') and (j + 1 == n or m[i][j+1] == 'x') and m[1-i][j] == 'x' ]#四种判断条件 ans += any(conditions) print(ans)

D-lz的染色问题

1.问题重述:

1.1.背景:

花园包含 n 朵花,每朵花有自己的颜色,在接下来的 m 天里，每天观察两朵花,如果观察的两朵花颜色不同，lz会生气。

1.2.要求:

需要选择最少数量的花进行重新染色，让 lz 在 m 天观察中不会生气

2.求解思路：

2.1.核心思路:

使用并查集将需要颜色相同的花分组

对每个连通分量，找出出现最多的颜色

计算需要染色的花的数量

2.2.详细解题步骤:

初始化并查集

将需要颜色相同的花合并到同一个集合

分组统计

找出每个连通分量的根节点，将同一连通分量的花分到同一组

计算最小染色数

对每个连通分量，统计出现最多的颜色数量，用连通分量的总花数减去最多颜色的数量，得到需要染色的最少花数

3.代码:

class UnionFind: def __init__(self, n): self.far = list(range(n + 1)) self.rank = [0] * (n + 1) def find(self, x): if self.far[x] == x: return x self.far[x] = self.find(self.far[x]) return self.far[x] def unite(self, x, y): x = self.find(x) y = self.find(y) if x == y: return if self.rank[x] > self.rank[y]: self.far[y] = x else: self.far[x] = y if self.rank[x] == self.rank[y]: self.rank[y] += 1 def main(): n, m = map(int, input().split()) uf = UnionFind(n) c = [0] + list(map(int, input().split()))# 读取颜色 a = [] for _ in range(m):# 处理边的连接 x, y = map(int, input().split()) uf.unite(x, y) a.extend([x, y]) cnt = 0 mp = {} G = {} for x in a: root = uf.find(x) if root not in mp: cnt += 1 mp[root] = cnt if mp[root] not in G: G[mp[root]] = set() G[mp[root]].add(x) ans = 0 for i in range(1, cnt + 1): s = {} ma = 0 for x in G[i]: s[c[x]] = s.get(c[x], 0) + 1 ma = max(ma, s[c[x]]) ans += len(G[i]) - ma print(ans) main()

E- lz的括号问题

1.问题重述:

1.1.背景:

给定一个由 n 对括号组成的字符串，字符串仅由字符 ( 和 ) 组成。每对括号需要按照出现的顺序进行编号。

1.2.要求:

计算每对括号在删除之前最多可以删除多少对括号。如果字符串中的括号无法完全匹配，则输出 -1。

2.求解思路：

使用一个计数器 len_ 来跟踪当前的括号深度。每遇到一个 (，计数器加一；每遇到一个 )，计数器减一。如果 len_ 变为负值，说明有多余的 )，此时输出 -1 并结束程序。若 len_ 不为零，说明括号没有完全匹配，输出 -1。
用一个列表 l 来存储每个 ( 的编号。每当遇到一个 ( 时，将当前的深度记录到列表中。使用 n - len_ 来表示当前括号可以在删除之前删除的对数。

3.代码:

n = int(input()) s = input().strip() l = [] len_ = 0 for i in s: len_ += 1 if i == "(" else -1 if len_ < 0: print(-1) exit() if i == "(": l.append(n - len_) print(" ".join(map(str, l)))

祝ACCCCCCC...

牛客小白月赛105 (Python题解) 比赛链接：点击传送 A-lz的吃饭问题代码： B-lz的数字问题代码: C-lz的蛋挞问题 1.问题重述: 1.1.背景: 1.2.要求: 2.求解思路： 2.1.核心思路: 2.2.四种判断条件详解： 3.代码: D-lz的染色问题 1.问题重述: 1.1.背景: 1.2.要求: 2.求解思路： 2.1.核心思路: 2.2.详细解题步骤: 3.代码: E- lz的括号问题 1.问题重述: 1.1.背景: 1.2.要求: 2.求解思路： 3.代码:祝ACCCCCCC...