算法（最大异或对）

143. 最大异或对​​​​

在给定的 N𝑁 个整数 A1，A2……AN𝐴1，𝐴2……𝐴𝑁 中选出两个进行 xor𝑥𝑜𝑟（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 N𝑁。

第二行输入 N𝑁 个整数 A1𝐴1～AN𝐴𝑁。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤1051≤𝑁≤105,

思路：

暴力的做法是对于第i个输入的数，分别于前i-1个数异或，得到一个最大值，然后用当前的最大值和ans比较大小，更大的给ans。当i从0到n走一遍以后完成求解，所用时间是o（N*N）。

优化的地方是内层的循环，即每次第i个数不用和前i-1个数都比较一遍，而是可以利用tire树找出其中能得到当前最大异或对的解，具体原理是对于已经存入tire树的前i-1个数，用到大到小遍历第i个数的二进制每一位，看tire数对于当前位，有无相反的那个数（1就是找0，0就是找1），若存在，则最大的异或一定是在这个分支上（因为高位大的一定大），若不存在，则只能选择相同的数，然后继续看下一位，重复上述过程。

注意idx是先加一，再去赋值，要把第0位空出来。开始用++idx出错了，因为若开头位数是0放下标位0的位置，相当于没动。

#include<iostream>
#include<cstring>
using namespace std;const int N=3000100;
int e[N][2];
int idx;
int n;void insert(int x)
{   int p=0;for(int i=30;i>=0;i--){int t=x>>i&1;if(!e[p][t])e[p][t]=++idx;p=e[p][t];}
}int serch(int x)
{   int ans=0;int p=0;for(int i=30;i>=0;i--){int t=x>>i&1;if(e[p][!t]){ans=ans*2+1;p=e[p][!t];}else{p=e[p][t];ans*=2;}}return ans;
}int main()
{   scanf("%d",&n);int ans=0;while(n--){int a;scanf("%d",&a);insert(a);ans=max(ans,serch(a));}printf("%d\n",ans);return 0;}