01Trie

01Trie 是一种基于 Trie字典树 上的数据结构，是一种解决关于异或类问题的数据结构。

01Trie 的本质就是把每个数变成二进制串再放到字典树上，在贪心求解。

把每一个数转化成 $31$ 位二进制，想让它的异或值最大，那就是让 $0$ 尽量遇到 $1$，$1$ 尽量遇到 $0$。所以就要从最高位开始，尽可能的让这个数的在二进制下的每一位都与枚举的数不同，如果不能满足，那就相同。 实现就是把每一个数的二进制放在 Trie 上维护，让后直接上模板即可。

貌似有更高端的压位01Trie。学了再补。

时间复杂度 $O(nk)$，$k$ 是个 $\le100$ 的常数。

注意点 1.要从高位到低位枚举，且枚举 $31$ 位二进制时注意是到 $i\ge 0$ 而不是 $i\ge 1$。 2.$son$ 数组的第二位因为是存二进制，所以只用开 $5$ 就够了。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int son[N][5];
int cnt[N],idx;
void insert(int x){
	int p=0;
	for(int i=31;i>=0;i--){	
		int u=(x>>i)&1;
		if(!son[p][u])son[p][u]=++idx;
		p=son[p][u];
	}
	cnt[p]++;
}
int query(int x){
	int p=0;
	int res=0;
	for(int i=31;i>=0;i--){
		int u=(x>>i)&1;
		if(son[p][1^u])res=res^(1<<i),p=son[p][1^u];
		else p=son[p][u];
	}
	return res;
}
int n,a[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		insert(a[i]);
	}
	int mx=-1e9;
	for(int i=1;i<=n;i++)mx=max(mx,query(a[i]));
	cout<<mx;
	return 0;
}