HDU 5014 贪心位运算：异或最大化配对

题目大意

给定数组 a[0..n]，需构造排列 b 使 sum = Σ (a[i] XOR b[i]) 最大化。输出最大和及任意最优排列。

核心观察

对每个 i，选择 X_i 使 i XOR X_i 的二进制位全为 1，且位数等于 i 的位数。即 X_i = (2^{k+1}-1) XOR i，其中 k = floor(log2(i))。

贪心构造算法

1. 从 n 递减到 0 遍历
2. 若 b[i] 已配对则跳过
3. 计算 ans = 位反码（仅保留 i 的有效位）
4. 配对 b[i]=ans, b[ans]=i
5. 累加贡献 2*(i XOR ans)

C++ 实现

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

const int N = 100000 + 100;
int a[N], b[N];

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        memset(b, -1, sizeof(b));
        for (int i = 0; i <= n; ++i) scanf("%d", &a[i]);
        long long sum = 0;
        for (int i = n; i >= 0; --i) {
            if (b[i] != -1) continue;
            int tmp = i, ans = 0, cnt = 1;
            while (tmp) {
                if ((tmp & 1) == 0) ans += cnt;
                tmp >>= 1;
                cnt <<= 1;
            }
            sum += 2LL * (i ^ ans);
            b[i] = ans;
            b[ans] = i;
        }
        printf("%lld\n", sum);
        for (int i = 0; i <= n; ++i) {
            if (i) printf(" ");
            printf("%d", b[a[i]]);
        }
        printf("\n");
    }
    return 0;
}

原理证明

• 对每个 i，最大异或值为 2^{k+1}-1（全 1 掩码）
• 该值对应的配对数 X_i 唯一且在 [0,n] 内
• 从大到小贪心保证大数优先获得最大贡献，不冲突

复杂度

• 时间：O(n log n) —— 每数处理位数
• 空间：O(n)

扩展

若求最小和，则应使异或结果最小（尽量配对相近数），可用字典树贪心匹配。