当前位置: 代码迷 >> 综合 >> codeforces 1504B Flip the Bits
  详细解决方案

codeforces 1504B Flip the Bits

热度:45   发布时间:2023-12-02 23:04:42.0

链接:

https://codeforces.com/problemset/problem/1504/B

题意:

给两个长度相同的01串,对于每个0和1数量相等的字符串前缀,可以将它们翻转1变0,0变1。问,第一个字符串,是否能通过这种方式变成第二个字符串。

对于每一个0和1数量相等的字符串前缀,只要在内的对应数字相互异或值相等即可,最后判断一下剩下的数字,是否异或值均为0即可。我们把每个01串用一个数字cnt记录0和1是否相等,当为1是cnt++,当为0时,cnt--。每当cnt等于0时(即0和1相等),就重置异或值,供后面的数字判断异或值是否一样。

代码如下:

#include<iostream>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<string.h>
#include<random>
using namespace std;
typedef long long ll;
int main() {int T;cin >> T;while (T--) {int n;cin >> n;string s1, s2;cin >> s1 >> s2;int c1 = 0, c2 = 0;bool f = true;bool flag = true;int a;for (int i = 0; i < n; i++) {if (s1[i] == '1') {c1++;}else if (s1[i] == '0') {c1--;}if (s2[i] == '1') {c2++;}else if (s2[i] == '0') {c2--;}if (f) {a = ((s1[i] - '0') ^ (s2[i] - '0'));f = false;}else {if (a != ((s1[i] - '0') ^ (s2[i] - '0'))) {flag = false;break;}if (!c1) {f = true;if (c2) {flag = false;break;}}}}if (c1 && flag) {if (a) {flag = false;}}if (flag) {cout << "YES" << endl;}else {cout << "NO" << endl;}}return 0;
}