怎么大家都会网络流和线性基…..
补题链接 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;
}