题目传送门

一、分析思路

//最大异或对
//用暴力是超时的
for(int i=0;i<n;i++)
   for(int j=0;j<i;j++)
      res=max(res,a[i]^a[j]);
  cout<<res<<endl;

结果不出意外，\(TLE\),只能想办法进行优化

最终结论如下：

1、将整数解析为二进制数，即有符号整数，31位，就是0-30，认为这31位是字符，按\(Trie\)树进行存储。

2、每个数字的每一个二进制位，需要从高位到低位，即for(int i = 30; i >= 0; i--)，原因是想像一下你在构建一个\(Trie\)树，那么根就是最高位，然后一路走到\(31\)位，就是最低位。

3、构建就是这样的，总结一下：
(1)\(Trie\)里可以用来保存数字，数字需要通过二进制进行保存。
(2)增加一个数字进来，其实就是增加了一个层级为\(31\)级的树节点。
(3)假设最高位，肯定只有两个数，\(0\)和\(1\)，当然，要是最高位是\(1\)，那这个数就很大了~，就是说，大多数情况下，多个数是有一部分相同的路径的，比如最开始的\(00000\)之类。
(4)放入一个数字，那么它肯定会在任意一级（共\(31\)级）存在一边，另一边可能存在，也可能不存在。存在是因为另一个数字在那边。也可能没有数字在另一边。
(5)上面的\(4\)就解答了为什么后面取反后找不到，就一定要本方能找到的问题。

4、你想找与自己高位不同的数字，但这个数字不一定就存在于字典中，比如你喜欢漂亮的，学历高，脾气好的，结果现实中没有，只能退而求其次

5、那就在\(Trie\)中去\(Query\)时，尽量找每一位与自己不同的路径，如果有的话，就走，如果没有的话，就只能退而求其次。
其实，这个查询是此算法的难点和重点，下面主要讨论这个问题：
（1）如果存在异或边，也就是本位在Tire树中存在取反值（0就是存在1，1就是存在0），那么这个数就可以表示为
res = (res<<1) + !u; 否则就是 res = (res<<1) + u;

6、直到走到节点尽头，就得到了与之异或最大的数字，然后计算两个数字的最大异或，与最大值打擂台。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = N * 31; //M代表节点的最终个数，因为一共N个数字，每个数字的转为二进制都是31位（首位一般用于符号，所以不是32），N*31就是M了

int n;
int a[N], son[M][2], idx;

void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;
        if (!son[p][u])son[p][u] = ++idx;
        p = son[p][u];
    }
}

//这个查询的含义: 在Trie树中查找到与x异或最大的数
int query(int x) {
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;     //取出x的每一位，看看是0还是1
        if (son[p][!u]) {       //如果存在可以异或的路可以走的话
            //res = (res<<1) + !u; 
            res = res * 2 + !u; //这里和10进制是一样的，比如 123=12*10+3,这里是一模一样的，只不过是二进制，需要乘以2，另外，当前位由于走的是!u,所以要加上!u
        } else {
            p = son[p][u];      //否则只能走与自己本位一样的路线
            res = (res<<1) + u;   //这里和10进制是一样的，比如 123=12*10+3,这里是一模一样的，只不过是二进制，需要乘以2，另外，当前位由于走的是u,所以要加上u
        }
    }
    return res;
}

int main() {
    //构建Trie树
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        //insert(a[i]);
        //这个insert放在这里，还是放在下在的查询循环内，都是可以的
        // 原因是我们需要找到 a(i) 与 a(i-1),a(i-2)....a(0)当中的最大值，没必要向上找，因为每一个都向下找了，就覆盖掉所有可能性了。
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        insert(a[i]);
        int t = query(a[i]);
        //打擂台，看看哪组异或值最大
        res = max(res, a[i] ^ t);
    }
    printf("%d\n", res);
    return 0;
}