AcWing 143 最大异或对

题目描述：

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

输入格式

第一行输入一个整数N。第二行输入N个整数A1～AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤10^5,0≤Ai<2^31

输入样例：

3
1 2 3

输出样例：

3

 分析：

本题要求我们从N个数中找出两个数来进行异或，并输出异或后的最大结果。暴力的做法就是两层循环来枚举进行异或的两个数，时间复杂度为平方级别的，而N的大小是10w，所以会超时。考虑对于一个数x而言，是否有办法在其他数中快速找出与之异或值最大的那个数而不用遍历所有数去找到呢？

我们知道，对于异或运算，需要相同位置的数不同最后异或得到的数才为1，即0 ^ 1 = 1。对于一个int类型的正整数，除去符号位以外，剩下31位数与它都相反最后异或的结果才是最大的。于是将N个数构建出一颗字典树，形状为二叉树。例如01001100（以8位为例，实际要考虑的是31位数），最高位为0，首先判断字典树上该层次结点有没有为1的，有则沿着1往下继续遍历，每次遍历都尽可能的走与原位置数相反的路径（没有相反的就走相同的），最后到达叶子结点时，得到的数也就是异或能得到的最大的数了，当然，需要我们在遍历的同时记录下对应位置异或的结果，这样最后只需要一重循环即可解决问题了。

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100005,maxm = 3000000;
int n;
int a[maxn],son[maxm][2],idx;
void insert(int x){
    int p = 0;
    for(int i = 30;i >= 0;i--){
        int &s = son[p][x >> i & 1];
        if(!s)  s = ++idx;
        p = s;
    }
}
int search(int x){
    int p = 0,res = 0;
    for(int i = 30;i >= 0;i--){
        int s = x >> i & 1;
        if(son[p][!s]){
            res += 1 << i;
            p = son[p][!s];
        }
        else    p = son[p][s];
    }
    return res;
}
int main(){
    cin>>n;
    for(int i = 0;i < n;i++){
        cin>>a[i];
        insert(a[i]);
    }
    int ans = 0;
    for(int i = 0;i < n;i++)    ans = max(ans,search(a[i]));
    cout<<ans<<endl;
    return 0;
}