题意描述
在给定的N个整数A1，A2……AN中选出两个进行xor（异或）运算，得到的结果最大是多少？
输入格式 第一行输入一个整数N。
第二行输入N个整数A1～AN。
输出格式 输出一个整数表示答案。
数据范围 1≤N≤105, 0≤Ai<231 输入样例： 3 1 2 3 输出样例： 3
思路
这道题的思路非常巧妙，可以用trie树来很快的解决这个问题。想要异或值最大，那么从某一数的二进制最高位开始，如果存在与该位不同的数，则取该数，否则就继续顺着这个结点走下去。因为题目规定数据范围是231，所以将数字转为31位的二进制，然后再遍历即可。
AC代码
代码语言：javascript复制#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=1e5 10;
const int maxm=31*1e5 10;
int a[maxn],son[maxm][2],idx=0;
void insert(int u){
int p=0;
for(int i=30;i>=0;i--){
int t=u>>i&1;
if(!son[p][t]) son[p][t]= idx;
p=son[p][t];
}
}
int query(int u){
int p=0,res=0;
for(int i=30;i>=0;i--){
int t=u>>i&1;
//如果存在与t相反的话，就走着一条
if(son[p][!t]){
p=son[p][!t];
res=res*2 !t;
}else{//否则就走唯一存在的一条
p=son[p][t];
res=res*2 t;
}
}
return res;
}
int main(){
int n;
int ans=0;
cin>>n;
for(int i=0;i<n;i ) cin>>a[i];
for(int i=0;i<n;i ){
insert(a[i]);
ans=max(ans,query(a[i])^a[i]);
}
cout<<ans<<endl;
}
