B. Replacement (python解)-codeforces
原题链接:
问题分析:
我们有两个二进制字符串:s
(长度为 n
)和 r
(长度为 n-1
)。根据游戏规则,我们需要在 s
上执行 n-1
次操作。在每次操作中,我们选择一个索引 k
,使得 s[k]
和 s[k+1]
不相同并将这两个字符替换为 r[i]
(第 i
次操作中 r
的第 i
个字符)。如果在某一步无法找到这样的 k
,我们就输掉了游戏。目标是判断是否能成功完成所有 n-1
次操作。
思路:
-
每次操作我们都需要将相邻的字符当中的一个改变为另一个字符。
在可用的情况下,我们需要检查
s
中的 0 和 1 是否足够替换为r
中的数据。 -
由于需要找到相邻不同的字符,我们可以确保至少一个替换操作可以进行,这意味着我们需要在最终构建的
r
中的每一个字符能用s
中的 0 和 1 进行合理替换。 -
因此,我们需要在每次替换时要跟踪
1
和0
的数量,以确保我们可以在r
中按顺序找到这些字符。 -
开始时获取
s
中1
和0
的数量。 -
对于r中的每个字符,检查是否可以合法进行替换:
如果
1
的数量不足以替换r[i]
(其中r[i]
为1
),则此时需要从0
减去一个并确保1
继续存在,反之亦然。 -
如果在过程中任何时间点
1
和0
的数量不足以保证替换,则最终输出NO
。 -
如果所有替换都能成功,输出
YES
。
代码:
for _ in range(int(input())):
n = int(input())
s = input()
one = s.count("1")
zero = s.count("0")
ans = "YES"
for ti in input():
if one == 0 or zero == 0:
ans = "NO"
break
one -= 1
zero -= 1
if ti == "1":
one += 1
else:
zero += 1
print(ans)
标签:字符,python,codeforces,zero,input,替换,Replacement
From: https://www.cnblogs.com/666-777-eto/p/18538263