acwing-143. 最大异或对

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

输入格式

第一行输入一个整数 N。

第二行输入 N 个整数 A1~AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤10⁵,
0≤Ai<2³¹

输入样例：

3
1 2 3

输出样例：

3

方法一：

字典树模板题2，使用贪心的思想，从二进制高位到低位，尽量找当前位相反的位（根据异或的运算性质，相反的位异或=1）

#include 

using namespace std;

const int N = 100010;
const int M = 1 << 30;

int n, trie[N * 32 + 10][2], idx, cnt[N*32+10], nums[N];

void insert(int a) {
    int m = M, p = 0;
    for (int i = 0; i < 31; ++i, m>>=1) {
        int b = (a & m) != 0;
        if (!trie[p][b]) trie[p][b] = ++idx;
        p = trie[p][b];
    }
    cnt[p] = 1;
}

int getmax(int a) {
    int m = M, p = 0, res = 0;
    for (int i = 0; i < 31; ++i, m>>=1) {
        int b = a & m;
        if (trie[p][!b]) {
            res += m;
            p = trie[p][!b];
        } else {
            p = trie[p][b!=0];
        }
    }
    return res;
}

int main() {
    int a;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &nums[i]);
        insert(nums[i]);
    }
    int res = 0;
    for (int i = 0; i < n; ++i) {
        res = max(res, getmax(nums[i]));
    }
    printf("%d", res);
}