AcWing 143. 最大异或对（Trie字典树）

【题目描述】
在给定的 N N N个整数 A 1 , A 2 , . . . , A N A_1,A_2,...,A_N A1​,A2​,...,AN​中选出两个进行 x o r xor xor（异或）运算，得到的结果最大是多少？

【输入格式】
第一行输入一个整数 N N N。
第二行输入 N N N个整数 A 1 ∼ A N A_1sim A_N A1​∼AN​。

【输出格式】
输出一个整数表示答案。

【数据范围】
1 ≤ N ≤ 1 0 5 1≤N≤10^5 1≤N≤105
0 ≤ A i < 2 31 0≤A_i<2^{31} 0≤Ai​<231

【输入样例】

3
1 2 3

【输出样例】

3

【分析】
这道题目很难想到是字典树，如果不是放在字典树单元的话。
其实来说，一个整数，是可以转化成为一个 32 32 32位的二进制数，而也就可以变成长度为 32 32 32位的二进制字符串。
既然如此话，那么我们可以这么做：遍历数组 A A A，对于每一个元素 A i A_i Ai​，每一次检索的时候，我们都往与当前 A i A_i Ai​这一位相反的位置走，也就是让 x o r xor xor值最大，如果说没有路可以走的话，那么就走相同的路。这样可以迅速找到 A A A中所有元素与 A i A_i Ai​异或的最大值，对于每一个 A i A_i Ai​的最大异或值取 m a x max max即为最终答案。

【代码】

#include 
using namespace std;

const int N = 100010, M = N * 31;
int son[M][2], idx;
int n, a[N];

void insert(int x)
{
    int p = 0;
    //从x的二进制数的最高位开始做
    for (int i = 30; ~i; i--)
    {
        if (!son[p][x >> i & 1])
            son[p][x >> i & 1] = ++idx;
        p = son[p][x >> i & 1];
    }
}

int query(int x)
{
    int p = 0, res = 0;
    for (int i = 30; ~i; i--)
    {
        //优先选择与x的第i位异或值为1的节点
        if (son[p][!(x >> i & 1)])
        {
            res += 1 << i;
            p = son[p][!(x >> i & 1)];
        }
        else p = son[p][x >> i & 1];
    }
    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;
}