B. Flip the Bits | Round #712 Div.2
6142 ワード
https://codeforces.com/contest/1504/problem/B
1秒、256 MBメモリ
input : t (1 ≤ t ≤ 104) n (1 ≤ n ≤ 3⋅105) a b(長さn、符号0と符号1からなる) output : For each test case, output "YES"if it is possible to transform a into b, or "NO"if it is impossible. You can print each letter in any case (upper or lower).
a文字列をbに設定できる場合、YESがない場合はNOを出力します. 条件: There is a binary string a of length n. In one operation, you can select any prefix of a with an equal number of 0 and 1 symbols. Then all symbols in the prefix are inverted: each 0 becomes 1 and each 1 becomes 0.
バイナリ形式で構成された文aが存在する.演算を実行するときは、1と0の数が等しい接頭辞を選択し、この部分を構成する0については、1を1、0で置き換えます. 後ろからずっと違う場所を見つけて、ひっくり返そうとした.そうすると、コードも長くなり、複雑さに時間がかかります.別の方法が必要です.
交換が必要
1秒、256 MBメモリ
input :
a文字列をbに設定できる場合、YESがない場合はNOを出力します.
バイナリ形式で構成された文aが存在する.演算を実行するときは、1と0の数が等しい接頭辞を選択し、この部分を構成する0については、1を1、0で置き換えます.
交換が必要
交換が必要な場合を考えます.
接頭辞セクションの現在のインデックスの文字が異なる場合は、置換する必要があります.でも今の位置は今の位置+1が違うと?現在の位置の接頭辞に反転し、+1で反転した場合にのみ元のシェイプが得られます.
このような状況を考慮すべきだ.
スワップ
このようにインデックスを表示する場合
このような形態を保つには,交換を行う.でもこの時交換できる条件を満たさないと?できません.
boolean値を使用して計算します.import sys
t = int(sys.stdin.readline())
for _ in range(t):
n = int(sys.stdin.readline())
a = list(sys.stdin.readline().rstrip())
b = list(sys.stdin.readline().rstrip())
a.append('1')
b.append('1')
cnt, flag = 0, 0
for i in range(n):
cnt += (a[i] == '1') - (a[i] == '0')
if ((a[i] == b[i]) != (a[i + 1] == b[i + 1])) and cnt != 0:
flag = 1
break
print("NO" if flag else "YES")
最後に同じ値を追加することで、計算がより便利になります.
Reference
この問題について(B. Flip the Bits | Round #712 Div.2), 我々は、より多くの情報をここで見つけました
https://velog.io/@jsin2475/B.-Flip-the-Bits-Round-712-Div.2
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
このようにインデックスを表示する場合
このような形態を保つには,交換を行う.でもこの時交換できる条件を満たさないと?できません.
boolean値を使用して計算します.
import sys
t = int(sys.stdin.readline())
for _ in range(t):
n = int(sys.stdin.readline())
a = list(sys.stdin.readline().rstrip())
b = list(sys.stdin.readline().rstrip())
a.append('1')
b.append('1')
cnt, flag = 0, 0
for i in range(n):
cnt += (a[i] == '1') - (a[i] == '0')
if ((a[i] == b[i]) != (a[i + 1] == b[i + 1])) and cnt != 0:
flag = 1
break
print("NO" if flag else "YES")Reference
この問題について(B. Flip the Bits | Round #712 Div.2), 我々は、より多くの情報をここで見つけました https://velog.io/@jsin2475/B.-Flip-the-Bits-Round-712-Div.2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol