#10050. 「一本通 2.3 例 2」The XOR Largest Pair最大异或对(Trie 字典树)

题目链接：The XOR Largest Pair

在给定的N个整数A1，A2……AN中选出两个进行xor（异或）运算，得到的结果最大是多少？
输入格式：
第一行输入一个整数N。
第二行输入N个整数A1～AN。
输出格式

输出一个整数表示答案。
数据范围

1≤N≤105,
0≤Ai<231.
输入样例：

3
1 2 3
输出样例：

3

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int n,a[maxn];
int ch[maxn*31][2],o;
//ch[u][c] u代表当前所在树枝
//ch[u][c] c代表当前所在结点是1还是0 
void insert(int x)
{
	int u=0;
	for(int i=30;i>=0;i--)//从最高位30位进行遍历 
	{
		int c=x>>i&1;//当前位数为1的话就是1 
		if(!ch[u][c])//如果不存在当前节点,就建立	
		ch[u][c]=++o;
		u=ch[u][c];//更新树枝,往下遍历
	}
}
int query(int x)
{
	int sum=0,u=0;//sum代表和
	for(int i=30;i>=0;i--)//从高位遍历
	{
		int c=x>>i&1;//当前位数为1的话就是1.
		if(ch[u][!c])
		//如果有和当前位不同的分支,我们就走该分支保证异或最大
		{
			u=ch[u][!c];//更新分支
			sum+=1<<i;//加上当前位所代表的数量(因为只要不相同就是1,不用管数是谁)
		}
		else
		u=ch[u][c];//没有不同的结点就继续往下遍历
	}
	return sum;
 } 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
	cin>>a[i];
	insert(a[i]);	
	}
	int sum=0;
	for(int i=1;i<=n;i++)//寻找最大值
	sum=max(sum,query(a[i]));
	cout<<sum<<endl;
}