CSU 1216 最大異或值：Trie 樹貪心查找 O(n) 解法

問題描述

給定 n（≤10⁵）個 32 位非負整數，求任意兩數異或的最大值。

Trie 樹核心思想

從高位到低位（31→0）將所有數插入二進制 Trie。查詢最大異或時，貪心地嘗試走與當前位相反的分支（使該位異或結果為 1），若不存在則走同位分支。

關鍵操作

const int MAXN = 100005;
const int MAXNODE = MAXN * 32;
int ch[MAXNODE][2], tot = 1;

void insert(int x) {
    int u = 1;
    for (int i = 31; i >= 0; --i) {
        int b = (x >> i) & 1;
        if (!ch[u][b]) ch[u][b] = ++tot;
        u = ch[u][b];
    }
}

int query_max_xor(int x) {
    int u = 1, res = 0;
    for (int i = 31; i >= 0; --i) {
        int b = (x >> i) & 1;
        int want = 1 - b;  // 期望相反位
        if (ch[u][want]) {
            res |= (1 << i);
            u = ch[u][want];
        } else {
            u = ch[u][b];
        }
    }
    return res;
}

完整代碼

#include 
using namespace std;
const int MAXN = 100005;
const int MAXNODE = MAXN * 33;
int ch[MAXNODE][2], tot;

void clear() {
    fill(ch[1], ch[1] + 2, 0);
    tot = 1;
}

void insert(int x) {
    int u = 1;
    for (int i = 31; i >= 0; --i) {
        int b = (x >> i) & 1;
        if (!ch[u][b]) { ch[u][b] = ++tot; fill(ch[tot], ch[tot] + 2, 0); }
        u = ch[u][b];
    }
}

int query(int x) {
    int u = 1, res = 0;
    for (int i = 31; i >= 0; --i) {
        int b = (x >> i) & 1;
        if (ch[u][1-b]) { res |= (1<> n) {
        clear();
        int ans = 0;
        for (int i = 0, x; i < n; ++i) {
            cin >> x;
            if (i > 0) ans = max(ans, query(x));
            insert(x);
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度分析

• 插入單個數：O(32) = O(1)
• 查詢單個數：O(32) = O(1)
• 總計：O(n) 時間，O(n × 32) 空間 ≈ 330 萬節點，約 26 MB

避坑指南

• 多測試用例需清空 Trie（重置 tot=1，根節點清零）
• 先查詢後插入，避免數與自己異或得 0 干擾最大值（雖然不影響結果）
• 32 位有符號整數最高位為符號位，題目說非負整數，直接用 31~0 位
• 輸入以 EOF 結束，while(cin>>n)

擴展：可持久化 Trie 求區間最大異或

對前綴構建可持久化 Trie，查詢 [L,R] 區間最大異或用版本 R 減版本 L-1。利用異或性質 a^b=c ⇔ a^c=b，前綴異或轉化區間查詢。