怎么大家都会网络流和线性基…..

补题链接 2024CCPC网络预选赛

J

令 $c_i=a_i\bigoplus b_i$ ，则对于交换 $a_i$ 和 $b_i$ 的操作，就相当于 $a_i\bigoplus c_i,b_i\bigoplus c_i$ 。

求出序列 $a$ 和 $b$ 的异或和 $A$ 和 $B$ ，于是问题便转化为从 $c_i$ 中选择若干个数的异或和，一起与 $A$ 和 $B$ 异或，使得 $\max(A,B)$ 的值最小。

由于 $c$ 的线性基可以得到任何由序列 $c$ 中选择若干个数的异或和，所以考虑求出序列 $c$ 的线性基（用 $p[i]$ 表示线性基内最高有效位为第 $i$ 位的数的写法），接着从高位到低位贪心的考虑异或是否会使答案更优即可。

代码

#include<bits/stdc++.h>
#define N 1000010

using namespace std;

int T;
int n,a[N],b[N],A,B;

int p[N];
void insert(int x) {
    for(int i=31;~i;i--) {
        if(x>>i&1) {
            if(!p[i]) {
                p[i]=x;
                break;
            }
            x^=p[i];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--) {
        A=B=0;
        for(int i=31;~i;i--) p[i]=0;
        cin>>n;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            A^=a[i];
        }
        for(int i=1;i<=n;i++) {
            cin>>b[i];
            B^=b[i];
        }
        for(int i=1;i<=n;i++) insert(a[i]^b[i]);
        for(int i=31;~i;i--) if(max(A,B)>max(A^p[i],B^p[i])) A^=p[i],B^=p[i];
        cout<<max(A,B)<<endl;
    }
    return 0;
}