HDU 5536 Chip Factory：字典樹優化查找最大異或值

題意

給定 n 個整數 s₁…sₙ，求最大值 (sᵢ + sⱼ) ^ sₖ，其中 i、j、k 互不相同。

解法：字典樹 + 枚舉

1. 將所有數插入二進制字典樹（0/1 兩叉），每個節點記錄通過次數 cnt。
2. 雙重循環枚舉 i、j（i < j），計算 sum = sᵢ + sⱼ。
3. 查詢前：在樹中刪除 sᵢ 和 sⱼ（避免 k 與 i/j 重合），查詢與 sum 異或值最大的數，再插回 sᵢ、sⱼ。
4. 全局維護最大值。

複雜度：O(n² · 32)，n ≤ 10⁴ 可行。

核心代碼

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 70005;
int tr[MAXN][2], cnt[MAXN], tot;
int s[1005];

void init(int u) { tr[u][0]=tr[u][1]=0; cnt[u]=0; }

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

int query(int x) { // 找與 x 異或最大的數
    int u = 0, ans = 0;
    for (int i = 31; i >= 0; i--) {
        int p = (x >> i) & 1;
        if (tr[u][p^1] && cnt[tr[u][p^1]] > 0) {
            ans |= (1 << i);
            u = tr[u][p^1];
        } else u = tr[u][p];
    }
    return ans;
}

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