CF2115D 题解

DaiRuiChen007 · 2025-10-07 20:04:57 · 题解

Problem Link

可以看成从 \oplus a_i 开始每次选择是否异或上 v_i=a_i\oplus b_i。

从高到低确定每一位的取值，首先最高位 k 的取值只和最后一个包含 2^k 的 v_i 对应的 c_i 有关。

然后考虑 k-1，如果最后一个包含 2^{k-1} 的 v_j 满足 j\ne i，那么只要考虑 c_j，否则玩家 c_i 应该尽可能让异或和的 k,k-1 位相同。

所以从 j 继续往前找一个 k,k-1 位不同的即可，继续类推 k-2,k-3,\dots 的情况，可以发现最终每个位置的决策都形如 f_i,g_i，即当前的异或和 S 若 \mathrm{popcount}(f_i\operatorname{AND}S)\bmod 2\ne g_i 就异或上 a_i。

维护 f_i,g_i 只要从后往前维护玩家 0 的目标 (w,h) 表示尽可能让 \mathrm{popcount}(w\operatorname{AND}S)\bmod 2= h。

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

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
ll a[MAXN],b[MAXN],f[MAXN];
bool c[MAXN],g[MAXN];
bool mul(ll x,ll y) { return __builtin_popcountll(x&y)&1; }
void solve() {
    int n; ll z=0,S=0;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i],S^=a[i],f[i]=g[i]=0;
    for(int i=1;i<=n;++i) cin>>b[i],a[i]^=b[i];
    for(int i=1;i<=n;++i) { char o; cin>>o,c[i]=o-'0'; }
    for(int k=59;~k;--k) {
        int x=n; ll w=1ll<<k; bool h=0;
        for(;;--x) {
            for(;x&&!mul(a[x],w);--x);
            if(!x) { z|=(mul(S,w)^h)*(1ll<<k); break; }
            h^=c[x]^g[x],w^=f[x];
            if(!f[x]) { f[x]=w,g[x]=h^c[x],z|=c[x]*(1ll<<k); break; }
        }
    }
    cout<<z<<"\n";
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int _; cin>>_;
    while(_--) solve();
    return 0;
}