Codeforces Round #712 (Div. 2) B

B. Flip the Bits

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

void solve(){
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    vector<int> az(n, 0), ao(n, 0);
    az[0] = a[0] == '0' ? 1 : 0;
    ao[0] = a[0] == '1' ? 1 : 0;
    for(int i = 1; i < n; i++){
        az[i] = az[i-1];
        az[i] += a[i] == '0' ? 1 : 0;
        ao[i] = ao[i-1];
        ao[i] += a[i] == '1' ? 1 : 0;
    }
    bool reverse = false;
    for(int i = n-1; i >= 0; i--){
        if(!reverse){
            if(a[i] != b[i]){
                if(az[i] == ao[i]){
                    reverse = !reverse;
                }
                else{
                    cout << "NO\n";
                    return;
                }
            }
        }
        else{
            if(a[i] == b[i]){
                if(az[i] == ao[i]){
                    reverse = !reverse;
                }
                else{
                    cout << "NO\n";
                    return;
                }
            }
        }
    }
    cout << "YES\n";
}

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        solve();
    }
    return 0;
}

항상 0, 1 의 개수가 같은 prefix 만 문자열 비트를 반전시킬 수 있다. 위치별 0, 1 의 각각의 누적합을 구해놓고 맨 오른쪽에서부터 a 와 b 의 문자가 같은지를 확인한다. 만약 문자가 다르면 해당 위치의 0, 1 의 개수를 확인한 후 같으면 반전시키고, 다르면 a 를 b 문자열로 만들 수 없으므로 NO 를 출력한다. 반복문이 끝날 때 까지 문제가 없다면 YES 를 출력한다.

후기

A 번이 A 번 답지 않게 느껴졌던 대회.