HDU 5536 Chip Factory - 字典樹求最大異或值

題目描述

給定 n 個整數 s1, s2, ..., sn，求最大值 (si + sj) ^ sk，其中 i, j, k 互不相同。

解題思路

這是一道經典的字典樹（Trie）應用題。核心思路：

1. 將所有數字插入二進制字典樹（最高位 31 到 0）。
2. 枚舉所有有序對 (i, j)，計算 sum = si + sj。
3. 在字典樹中查詢與 sum 異或值最大的數字，但必須排除 si 和 sj 本身。實現方法：查詢前暫時從樹中刪除 si 和 sj，查詢後再插回。
4. 維護全局最大值。

關鍵技術點

• 字典樹節點存儲子節點索引與經過計數（cnt），支持刪除操作。
• 刪除時沿路徑遞減 cnt，cnt 歸零即視為節點不存在。
• 查詢最大異或時，優先走與 sum 當前位相反的分支（若該分支 cnt > 0）。

完整代碼

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAX_NODE = 70005; // 1000 * 32 略大

int n, T, tot;
int tr[MAX_NODE][2], cnt[MAX_NODE];
int s[MAXN];

void init() {
    tot = 0;
    memset(tr[0], 0, sizeof(tr[0]));
    cnt[0] = 0;
}

int newNode() {
    ++tot;
    tr[tot][0] = tr[tot][1] = 0;
    cnt[tot] = 0;
    return tot;
}

void insert(int x, int delta) { // delta = +1 插入, -1 刪除
    int u = 0;
    for (int i = 31; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (!tr[u][b]) tr[u][b] = newNode();
        u = tr[u][b];
        cnt[u] += delta;
    }
}

int queryMaxXor(int x) {
    int u = 0, res = 0;
    for (int i = 31; i >= 0; i--) {
        int b = (x >> i) & 1;
        int want = b ^ 1;
        if (tr[u][want] && cnt[tr[u][want]] > 0) {
            res |= (1 << i);
            u = tr[u][want];
        } else {
            u = tr[u][b];
        }
    }
    return res;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", &s[i]);
            insert(s[i], 1);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int sum = s[i] + s[j];
                insert(s[i], -1);
                insert(s[j], -1);
                ans = max(ans, queryMaxXor(sum));
                insert(s[i], 1);
                insert(s[j], 1);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

插入/刪除/查詢均為 O(32)。雙重循環 O(n^2)，n ≤ 1000，總操作約 10^6 * 32 = 3.2×10^7，完全可行。

總結

本題展示了字典樹在動態集合最大異或查詢中的強大能力。關鍵在於利用計數器實現臨時刪除，保證查詢時不使用被排除的元素。