https://codeforces.com/contest/282/problem/C
给定两个01字符串ab,每次可以在a中选择两个相邻的字符xy,使得a=x^y,b=x|y,然后给xy赋值为ab(或者ba),问最后a能否变成b
考虑所有情况:
10/01:可以变成11
00:不能改变
11:可以变成10
那么只要a中有一个1就可以变出所有除全部为0的所有情况,(可以先变换出b中0和1的对应个数,10可以变成11然后变成01,相当于是相邻数字可以交换)
#include <bits/stdc++.h> #define eb emplace_back #define divUp(a,b) (a+b-1)/b #define mkp(x,y) make_pair(x,y) #define all(v) begin(v),end(v) #define int long long #define deb(x) cout<<#x<<" "<<x<<endl; using namespace std; typedef unsigned long long ull; typedef pair<int, int> pii; bool checkP2(int n) {return n > 0 and (n & (n - 1)) == 0;}; template<typename... T> void read(T&... args) { ((cin >> args), ...); } template<typename... T> void put(T... args) { ((cout << args << " "), ...); cout << endl; } void solve() { string a, b; read(a, b); if (a.size() != b.size()) { put("NO"); return; } if (a == b) { put("YES"); return; } if (a.size() == 1) { put("NO"); return; } int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0; for (auto i : a) { if (i == '1') cnt1++; else cnt2++; } for (auto i : b) { if (i == '1') cnt3++; else cnt4++; } if (cnt2 == a.size() or !cnt3) { put("NO"); return; } put("YES"); } signed main() { ios::sync_with_stdio(false); cin.tie(0); // int _; cin >> _; while (_--) solve(); return 0; }