最大异或对(The XOR Largest Pair) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int ch[2];
    Node() { ch[0] = ch[1] = 0; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<Node> tr;
    tr.reserve(n * 31 + 5);
    tr.emplace_back();

    auto insert = [&](uint32_t x) {
        int u = 0;
        for (int b = 30; b >= 0; --b) {
            int bit = (x >> b) & 1;
            if (!tr[u].ch[bit]) {
                tr[u].ch[bit] = (int)tr.size();
                tr.emplace_back();
            }
            u = tr[u].ch[bit];
        }
    };

    auto query = [&](uint32_t x) -> uint32_t {
        int u = 0;
        uint32_t res = 0;
        for (int b = 30; b >= 0; --b) {
            int bit = (x >> b) & 1;
            int want = bit ^ 1;
            if (tr[u].ch[want]) {
                res |= (1u << b);
                u = tr[u].ch[want];
            } else {
                u = tr[u].ch[bit];
            }
        }
        return res;
    };

    uint32_t ans = 0;
    for (int i = 0; i < n; ++i) {
        uint32_t x;
        cin >> x;
        if (i > 0) ans = max(ans, query(x));
        insert(x);
    }
    cout << ans << "\n";
    return 0;
}