自动搬运

查看原文

来自洛谷，原作者为

	NewInTown NewInTown

搬运于2025-08-24 23:07:40，当前版本为作者最后更新于2024-12-24 12:07:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

出题人来啦~

~大家要好好品鉴题目背景哦~

以下是正文：

不妨假设 $a_1⊕a_2⊕\cdots⊕a_n$ 不大于 $b_1⊕b_2⊕\cdots⊕b_n$。所以我们需要最大化 $a_1⊕a_2⊕\cdots⊕a_n$。

令 $c_i=a_i\cdot(2^{31})+b_i$。对 $c$ 做线性基得到线性基 $C$。

从高向低枚举答案的第 $i$ 位，对于第 $i$ 位，先假设其为 $1$：

• 由于 $a$ 小于 $b$，所以可以确定 $a$ 的 $i$ 至 $30$ 位的值，使用线性基 $C$ 的 $i+31$ 至 $61$ 位构造 $a$。

• 将 $C$ 的 $0$ 至 $i+30$ 位取出，将这 $i+31$ 个数分别并上 $(2^{31}-1)$ 后，再做一次线性基得到线性基 $D$。

• 不难发现可以使用 $D$ 确定 $b$ 的最大值 $b_{\max}$，若 $\frac{b_{\max}}{2^{i}}<\frac{a}{2^{i}}$ 则与 $a$ 不大于 $b$ 矛盾。

不难发现若第一步构造成功并且第三步没有矛盾则表明答案的第 $i$ 位可以为 $1$，否则一定为 $0$。

枚举结束即可得到 $a$ 和 $b$，注意需要再次判断 $a$ 与 $b$ 的大小，即可得到答案。至此此题完结。

单次询问时间复杂度 $O(n\log v+\log^3v)$。

std：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll long long
const int MAXN=2e5+5;
int a[MAXN],b[MAXN],n;
void add(ll *a,ll x) {
	for(int j=61; j>=0; j--)if(x>>j&1) {
			if(!a[j]) {
				a[j]=x;
				return;
			} else x^=a[j];
		}
}
int work(int* a,int* b) {
	ll c[62]= {0},d[62]= {0};
	for(int i=1; i<=n; i++)add(c,(ll)a[i]<<31|b[i]);
	int A=0,B=0;
	for(int i=30; i>=0; i--)if(c[i+31]) {
			if(~A>>i&1) {
				A^=c[i+31]>>31;
				B^=c[i+31]&0x7fffffff;
			}
			memcpy(d,c,sizeof(ll)*31);
			for(int j=31; j<i+31; j++)add(d,c[j]&0x7fffffff);
			int nb=B;
			for(int j=30; j>=0; j--)nb=max((ll)nb,nb^d[j]);
			if((nb>>i)<(A>>i)) {
				A^=c[i+31]>>31;
				B^=c[i+31]&0x7fffffff;
			}
		}
	for(int j=30; j>=0; j--)B=max((ll)B,B^c[j]);
	return min(A,B);
}
int main() {
	int t;
	cin>>t;
	while(t--) {
		scanf("%d",&n);
		for(int i=1; i<=n; i++)scanf("%d",a+i);
		for(int i=1; i<=n; i++)scanf("%d",b+i);
		printf("%d\n",max(work(a,b),work(b,a)));
	}
	return 0;
}