《算法竞赛进阶指南》The XOR Largest Pair题解

题目描述
在给定的N个整数A1,A2,…,AN中选出两个进行异或运算，得到的结果最大是多少？

输入描述
第一行一个整数N。
第二行N个整数Ai。

输出描述
一个整数表示答案。

思路

这题可以用字典树做，首先把所有的数都变成有32位的二进制数， 然后像字符串一样处理，由于要求j<i，所以边输入边处理。

代码
#include<bits/stdc++.h>
using namespace std;
int n,tot=1,Max,a[100005],tree[100000*32+5][2];
void insert(int x){
int p=1;
for(int k=30;k>=0;--k){
int temp=((x>>k)&1);
if (!tree[p][temp])tree[p][temp]=++tot;
p=tree[p][temp];
}
}
int search(int x){
int p=1,ans=0;
for(int k=30;k>=0;--k){
int temp=((x>>k)&1);
if (tree[p][(temp^1)]){
p=tree[p][(temp^1)];
ans|=(1<<k);
}
else p=tree[p][temp];
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);insert(a[i]);
Max=max(Max,search(a[i]));
}
printf("%d\n",Max);
return 0;
}