一道字典树的趣题

我们先将所有数的二进制从高位往低位建字典树：

然后枚举每一个 $A_i$ ，贪心地尽量走与 $A_i$ 每一位都相反的数（这样的异或和最大），算出来的最大异或和就是答案了。

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define S 3200005
int ch[S][2],n,a[N],tot,ans;
void write(int x){
	if(x>=2)write(x>>1);
	putchar((x&1)+'0');
}
void insert(int num,int x=0){
	for(int i=1;i<=31;++i){
		short c=((num&0x40000000)>>30); //意思是取 num 最高位的值
		if(ch[x][c]==0)ch[x][c]=++tot;
		x=ch[x][c];
		num<<=1;
	}
}
int search(int num,int x=0,int ret=0){
	for(int i=1;i<=31;++i){
		short c=1-((num&0x40000000)>>30);
		if(ch[x][c]==0){               //如果相反的数不存在，那就求其次取相同者
			ret<<=1;
			c=1-c;   
		}else ret=((ret<<1)|1);
		x=ch[x][c];
		num<<=1;
	}
	return ret;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		insert(a[i]);
	}
	for(int i=1;i<=n;++i){
		ans=max(ans,search(a[i]));
	}
	printf("%d\n",ans);
	return 0;
}