最大异或对（ Trie + 字典树 + 贪心 ）

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

输入格式

第一行输入一个整数 N。

第二行输入 N 个整数 A1AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤105,
0≤Ai<231

输入样例：

3
1 2 3

输出样例：

3

 M表示一个数字串二进制可以有多长

在b站看到一个视频感觉讲得细一点点：https://www.bilibili.com/video/BV1zY4y1B7FF?spm_id_from=333.880.my_history.page.click&vd_source=5f9ec6f15dc7e203f0b71bdf06232b7e

 如果出现位数不够前缀补 0  

 k 的含义是 取X的第 k 位的二进制数表示里面是 0 还是 1

对于 i = 30 ：int的最高位是第31位，且最高位是符号，这里规定了所有数都是正数，所以不用考虑符号位，只用考虑30~0。

如图所示为创建 2 的结点

 对于左移累加位权

 

 

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 3 * 1e6 + 10;
int n;
int a[N], son[M][2], idx;
void insert(int x){
    int p = 0;
    for(int i = 30; i >= 0; i -- ){  // i 等于30 是指从最大位开始找
        int &s = son[p][x >> i & 1];
        //  s 是son的引用，s变化，son 也要变化；若不加引用只会变化 s
        if(!s)
            s = ++ idx;
        p = s;
    }
}
int query(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 res = 0;
    for(int i = 0; i < n; i ++ ){
        res = max(res, query(a[i]));
    }
    cout << res << endl;
    return 0;
}