python/TangDou/AcWing/Trie/143.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = N * 31;

int n, res;
int a[N];
int tr[M][2];
int idx;

// 构建数字二进制位的Trie树
void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1;            // 取出当前位的值
        if (!tr[p][u]) tr[p][u] = ++idx; // 构建Trie树
        p = tr[p][u];
    }
}

// 所谓与x异或最大，就是利求在高位上尽量不一样，如果找不到不一样的，就只能找一样的，下一个继续优先找不一样的
// 在Trie树中查找到与x异或最大的数
int query(int x) {
    int p = 0, ans = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1; // 取出x的当前二进制位
        if (tr[p][!u]) {      // 如果存在可以异或的路可以走的话,尽量先走
            p = tr[p][!u];
            ans = ans * 2 + !u; // 还原二进制数字为十进制
        } else {
            p = tr[p][u];      // 否则只能走与自己本位一样的路线
            ans = ans * 2 + u; // 还原二进制数字为十进制
        }
    }
    return ans;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], insert(a[i]);

    for (int i = 1; i <= n; i++) {
        int t = query(a[i]);
        res = max(res, a[i] ^ t);
    }
    printf("%d", res);
    return 0;
}