七濑悠月

冷却心 · 2025-06-11 12:43:08 · 题解

赛后过的，但感觉难度 2900* 高了，为啥我场上不会做。

二选一异或有点复杂，我们不妨记 c_i=a_i \oplus b_i，这样如果让答案一开始为所有 a_i 异或和，那么就是每次可以选择是否异或 c_i，使最终答案最大或最小。

我们经典地从高位往低位考虑，设 d 为所有 c_i 中最高位的位置，那么此时不论前面怎么决策，最后一个最高位为 d 的位置总能使得这一位变成决策者希望的最大或最小。形式化地，我们记下标集合 S 表示最高位为 d 的 c_i 的位置集合，记 t=\max S，那么如果 S\setminus \{t\} 这个集合中最终操作得到答案的第 d 位和 c_t 的决策者想要的不同，那么 c_t 就会异或进入答案，否则不变。于是我们先判断当前答案的第 d 位是否需要 c_t 异或，然后把全部 c_i 中最高位是 d 的位置全部异或上 c_t，表示如果这一位选进答案，那么 c_t 是否选择的状态就要改变。容易发现这样操作一次最高位会降低，并且后面的操作不会改变更高的位置，所以最优。

时间复杂度 \mathcal O(n\log V)。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 10;
int n; LL A[N]; char S[N];

int main() {
    freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int _; cin >> _;
    while (_ --) {
        cin >> n; LL Ans = 0, x;
        for (int i = 1; i <= n; i ++) cin >> A[i], Ans ^= A[i];
        for (int i = 1; i <= n; i ++) cin >> x, A[i] ^= x;
        cin >> (S + 1);
        for (int i = 59; i >= 0; i --) {
            int t = n; while (t && !((A[t] >> i) & 1)) t --;
            if (!t) continue;
            if (((Ans >> i) & 1) ^ (S[t] == '1')) Ans ^= A[t];
            for (int j = 1; j <= n; j ++) if ((A[j] >> i) & 1) A[j] ^= A[t];
        } cout << Ans << "\n";
    }
    return 0;
}