codeforces 282C

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;
}

上一篇:Codeforces Round #749 (Div. 1 + Div. 2)


下一篇:codeforces lorry