在给定的\(N\)个整数\(A1，A2……AN\)中选出两个进行xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数N。
第二行输入N个整数\(A1～AN\)。
输出格式
输出一个整数表示答案。
数据范围
\(1≤N≤105,\)
\(0≤Ai<231\)
输入样例
3
1 2 3
输出样例
3
算是一个Trie树的模板题，归纳一下Trie树的相关知识。
Trie树用于实现字符串快速检索，是一种多叉树结构，其每个结点都有若干子结点。一般的操作有：
初始化
一个空Trie只包含一个根节点
int trie[SIZE][26], tot = 1; //trie数组的第二维通常是已知的，这里只考虑小写字母，所以每个节点最多有26个子结点，tot是节点指针，对应于第一维插入
void insert(char* str){
int len = strlen(str), p = 1;
for(int k = 0; k < len; k++){ //遍历str的每一个字符
int ch = str[k]-'a';
if(trie[p][ch] == 0) trie[p][ch] = ++tot; //如果不存在子结点，那么指向一个新的结点
p = trie[p][ch]; //继续移动p指针
}
end[p] = true; //结束标记
}检索
bool search(char* str){
int len = strlen(str), p = 1;
for(int k = 0; k < len; ++k){
p = trie[p][str[k]-'a'];
if(p == 0) return false; //如果这个节点不存在，那么说明trie树中没有存储这个字符串，结束检索并返回false;
}
return end[p];
}回到问题上，这里是统计异或对，那么每个结点的子结点就只有0和1两种情况，即每个结点最多有两个儿子。我们对每个输入的数字，都将它的二进制串存储在trie树上，同时再在trie树上检索这个数字，对某个数A，如果它的某一位二进制数是0，那么我们在检索时就看trie树上对应结点的子结点是否有1，即去搜索与当前数的bit位相反的结点，如果有就记录1，没有就沿着相同结点继续搜索，并记录0.
整个trie树的结点总数（空间复杂度）应该是儿子个数 X 字串最大长度
#include <iostream>
using namespace std;
const int maxn = 3000000; //这里我之前取的是2<<31，然后数组大小就只有5...
const int maxm = 1e5;
int son[maxn][2];
int a[maxm];
int idx = 0;
void insert(int x){
int p = 0, mask = 1 << 30;
int val;
for(int i = 0; i < 31; ++i){
if(x & mask) val = 1; else val = 0;
if(!son[p][val]) { son[p][val] = ++idx;}
p = son[p][val];
mask = mask >> 1;
}
}
int tofind(int x){
int p = 0, res = 0, mask = 1 << 30, val;
for(int i = 0; i < 31; ++i){
if(x & mask) val = 1; else val = 0;
if(son[p][1-val]){
res += (1<<(30-i));
p = son[p][1-val];
}else
p = son[p][val];
mask = mask >> 1;
}
return res;
}
int main(){
int n; scanf("%d", &n);
int ans = 0;
for(int i = 0; i < n; ++i){
scanf("%d", &a[i]);
insert(a[i]);
ans = max(tofind(a[i]), ans);
}
printf("%d", ans);
}