AcWing 835. Trie字符串统计

最大异或树解题思路：

与之前的Trie数组示例类似，只不过输入元素由原来的char数组改为数字。 如果使用暴力就会超时，同时异或运算会等于0。 因此，对于每棵树，你只需要尽力在当前树的每个位上找到一棵与该树不同的树（二叉格式），首先将所有输入的数字存储在二叉树中，然后使用for循环遍历每个要检索的数字；

具体实现过程中，是从高位开始判断数字的。 如果一个数字的当前位数与查找到的数字对应的位数不同，则1将左移i位，因为这个差异保证了答案将被转换为二进制。 之后，该位的值为1；

与模板相似度较高的题解：

#include 
#include 
#include 
using namespace std;
const int N = 1e5+10,M=3100010;
int n;
int a[N],son[M][2],idx;
void insert(int x){
    int p=0;
    //从最高位开始进行判断，由于位数越高，右移需要的位数越多，因此i要从30开始不断--；
    for (int i = 30;i>=0; i -- ){
        //这里之所以要使用&来修饰是因为s的值需要被修改，加上引用符号之后，s的值改变时，son[][]的值也会改变。
        //这里先右移i位，然后&1是用来判断第i位是否为1
        //int u=x>>i&1;
        int &s=son[p][x>>i&1];
        //如果s为空，开辟一个新的位置
        if(!s)  s=++idx;
        //让p移动到下一个节点位置
        p=s;
    }
}
int query(int x){
    int p=0,res=0;
    for (int i = 30; i>=0; i -- ){
        //这里s只是用来判断是否存在，不需要使用引用符号
        int s=x>>i&1;
        //如果与当前判断的值的第i位正好相反的数存在，那么就进入这条分支，同时res要进行二进制转10进制的运算
        if(son[p][!s]){
            res+=1<>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,query(a[i]));
    cout<