最大异或对（每周一类）

        今天我们来看这个最大异或类这道题 最大异或对 

        1.首先，我们先来了解一下异或是什么，之后还要讲一下同或。

        众所周知，数字在计算机中是由二进制来表示的，比如十进制的7，用二进制表示就是 111，十进制的3，用二进制表示就是011,。形象一点表示如下图：

        3与7进行异或操作就是将二进制相同的地方变成0，不同的地方变成1，在示例中，就变成了4。

        简单理解，就异（不一样的地方）变成1,。

        同或就是相反，同（相同的地方）变成1，不相同的地方变成0。

        好，在理解了基础概念再看这道题，就是我们用暴力的方法，就是两重循环，一个个来做异或，比较他们的大小，最后找出最大的异或对。在c++中，异或的运算符号是^，比如要计算a异或b，就写 a ^ b 就好。

        在理解了题意之后，我们来做一下代码（暴力）：

#include <iostream>
#include <algorithm>using namespace std;
const int N = 100010;int main(){int n;cin >> n;int a[N];for(int i = 0; i < n ; i ++ ){scanf("%d",&a[i]);}int res = -1;for(int i = 0; i < n ; i ++ ){for(int j = i + 1; j < n; j ++ ){int x = a[i]^a[j];res = max(res,x);}}printf("%d\n",res);return 0;
}

        时间复杂度是O（n^2）有点太大了，我们要进行优化，方法就是 Trie 树，由于对于每一个数，我们总有办法找到最好的，能匹配它的数，使得他们的异或值最大，如下图，我们找和十进制的 5 匹配的数字，5变成二进制是101，我们要找的就是二进制是010的数字，就是2。

        按照这个思路，我们在存进去一个数的时候，就可以存储Trie树，当查找最大值的时候，我们就可以对刚刚暴力循环的第二层进行优化之后的查找，效率会更高。具体代码如下：

#include <iostream>
#include <algorithm>using namespace std;
const int N = 100010, M = 3100010;int n;
int a[N], son[M][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(){int n;cin >> n;for(int i = 0; i < n ; i ++ ){scanf("%d",&a[i]);insert(a[i]);}int res = 0;for(int i = 0; i < n ; i ++ ) res = max(res, search(a[i]));printf("%d",res);return 0;
}

        和上一节一样，我们存储的时候要定义索引 p ，刚开始是 0 ，随着 idx 的增加，而递增，用于判断不同的数字变成的二进制串，如果输入的串存在，那么就继续；如果不存在，就创建。在查找的时候，如果查找的串存在，就继续，如果不存在，就输出相反字符，比如我们对 101 的 期望是 010，但如果没有 010 ，只有 011，我们就找 011串。

        其中对于每一个数字的处理，我们是从高位到低位进行处理，我们从31到0位进行存入或者查找。

        这节课可以参照着上节课一起看，将Trie树的模版掌握并会自己写，就可以迎刃而解