【題解】AtCoder AGC 045A – Xor Battle

【題目敘述】https://atcoder.jp/contests/agc045/tasks/agc045_a

#include <bits/stdc++.h>
using namespace std;

long long t, n, a[205];
string s;

int main(){
    cin >> t;
    while (t--){
        cin >> n;
        for (int i = 0; i < n; i++){
            cin >> a[i];
        }
        cin >> s;
        long long b[63] = {};
        auto add = [&](long long x)->bool{
            for (int i = 62; i >= 0; i--){
                if (!((x>>i)&1)) continue;
                if (!b[i]){
                    b[i] = x;
                    return true;
                }
                x ^= b[i];
            }
            return false;
        };
        bool flag = true;
        for (int i = n-1; i >= 0; i--){
            if (add(a[i]) && s[i] == '1'){
                flag = false;
                break;
            }
        }
        if (!flag) cout << 1 << "\n";
        else cout << 0 << "\n";
    }
}

分享本文 Share with friends