Boneca Ambalabu 的异或问题 详细题解

问题描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$（$0 \le a_i < 2^{30}$）。对于每一个 $k$（$1 \le k \le n$），定义：

$$S(k) = (a_k \oplus a_1) + (a_k \oplus a_2) + \cdots + (a_k \oplus a_n) $$

要求求出 $\max_{1 \le k \le n} S(k)$。其中 $\oplus$ 表示按位异或运算。

输入格式

第一行一个整数 $t$，表示测试用例数（$1 \le t \le 10^4$）。
每个测试用例第一行一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。
第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i < 2^{30}$）。
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示最大可能的 $S(k)$。

核心思路：按位独立计算

计算 $S(k) = \sum_{j=1}^n (a_k \oplus a_j)$ 时，如果对每个 $k$ 都直接计算，复杂度将达到 $O(n^2)$，不可接受。
观察异或运算的性质：

• 异或是按位独立的，即两个数异或结果的第 $i$ 位只由这两个数在第 $i$ 位上的值决定。
• 加法可交换、可结合，所以总和可以按位拆开：先求每一位上异或结果为 1 的次数，再乘以该位的权值 $2^i$，最后相加。

若我们固定一个 $k$，对于第 $i$ 位（$0 \le i < 30$），$a_k \oplus a_j$ 在该位为 $1$ 的个数取决于：

• 如果 $a_k$ 的第 $i$ 位是 0：那么 $a_k \oplus a_j$ 的第 $i$ 位是 $1$ 当且仅当 $a_j$ 的第 $i$ 位是 $1$。
  我们设整个数组中第 $i$ 位为 $1$ 的元素个数为 $cnt[i]$，则这种情况下的贡献为 $cnt[i]$ 次。
• 如果 $a_k$ 的第 $i$ 位是 1：那么 $a_k \oplus a_j$ 的第 $i$ 位是 $1$ 当且仅当 $a_j$ 的第 $i$ 位是 $0$。
  这样的 $a_j$ 的个数是 $n - cnt[i]$。

因此，该位对 $S(k)$ 的总贡献可以写成：

• 若 $a_k$ 的第 $i$ 位为 0：贡献 $cnt[i] \cdot 2^i$
• 若 $a_k$ 的第 $i$ 位为 1：贡献 $(n - cnt[i]) \cdot 2^i$

这样，对于任何一个 $k$，我们只要知道 $cnt$ 数组和 $a_k$ 的值，就可以在 $O(30)$ 时间内算出 $S(k)$。

算法步骤

1. 读入数据：$n$ 和数组 $a$（代码中从下标 1 开始）。
2. 预处理 $cnt$ 数组：
   • 初始化长度为 $30$ 的全零数组 $cnt$。
   • 遍历每个元素 $a_i$，对每个位 $j$（$0 \le j < 30$），若 $(a_i >> j) \mathbin{\&} 1 = 1$，则 $cnt[j]$ 加 1。
   • 时间复杂度 $O(30n)$。
3. 计算每个 $k$ 的 $S(k)$ 并更新答案：
   • 初始化答案 $ans = 0$。
   • 对于每个 $i$ 从 $1$ 到 $n$：
     • 初始化 $tot = 0$。
     • 对于每个位 $j$ 从 $0$ 到 $29$：
       • 提取 $a_i$ 的第 $j$ 位 $f = (a_i >> j) \mathbin{\&} 1$。
       • 若 $f = 1$：$tot \mathrel{+}= (1 << j) \times (n - cnt[j])$
       • 若 $f = 0$：$tot \mathrel{+}= (1 << j) \times cnt[j]$
     • $ans = \max(ans, tot)$
   • 时间复杂度 $O(30n)$。
4. 输出 $ans$。

总时间复杂度 $O(30n) = O(n \log \max a_i)$，空间复杂度 $O(30 + n)$。

标准程序详解

下面是题目提供的标准程序，我们将逐段分析。

#include <bits/stdc++.h>
using namespace std;
#define int long long           // 避免溢出，使用 64 位整数

void solve() {
    int n; cin >> n;
    int arr[n+1];               // 存储原数组，下标从 1 开始
    vector<int> cnt(30, 0);    // 记录每一位 1 的个数
    // 预处理 cnt
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        for (int j = 0; j < 30; j++) {
            cnt[j] += ((arr[i] >> j) & 1);
        }
    }
    int ans = 0;
    // 枚举每个可能的 k
    for (int i = 1; i <= n; i++) {
        int tot = 0;
        for (int j = 0; j < 30; j++) {
            bool f = ((arr[i] >> j) & 1);
            if (f) {
                tot += (1 << j) * (n - cnt[j]);  // 第 j 位为 1，计算贡献
            } else {
                tot += (1 << j) * cnt[j];         // 第 j 位为 0，计算贡献
            }
        }
        ans = max(ans, tot);
    }
    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}