ZOJ 3870 Team Formation：XOR 技能值組隊計數（位運算 + 排序）

問題分析

給定 N（≤10⁵）個技能值，求無序數對 (i,j) 使得 a_i ⊕ a_j > max(a_i, a_j)。

關鍵性質

設 x < y。則 x ⊕ y > y **當且僅當** y 的最高位在 x 中為 0。
即：x 的最高位**必須低於** y 的最高位。

算法

1. 排序數組。
2. 維護 `cnt[bit]` = 當前已處理元素中最高位為 `bit` 的個數。
3. 遍歷排序後的數組，對當前值 y，其最高位為 `hb`。所有最高位 < `hb` 的已處理元素均可與 y 組成合法數對。累加 `sum(cnt[0..hb-1])`。
   然後 `cnt[hb]++`。

代碼

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector a(n);
        for (int &x : a) cin >> x;
        sort(a.begin(), a.end());
        long long ans = 0;
        array cnt{}; // 最高位 0..30
        for (int x : a) {
            int hb = 31 - __builtin_clz(x); // 最高位位置
            for (int b = 0; b < hb; ++b) ans += cnt[b];
            cnt[hb]++;
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

O(N log N + N × 31)，線性通過。