求解可无限生成子集异或最大值问题——Codeforces 1847C遇挫

问题回顾 #

给定序列a，可无限次选取任意子集的异或值追加到a末尾，求最终序列中的最大值。

原思路的核心问题 #

你的思路存在两个关键错误，可能导致输出异常值：

1. 对异或空间的理解偏差：
   你试图通过前缀异或的贪心组合寻找最大值，但所有可通过追加操作得到的元素，本质是原序列线性基所张成的异或空间中的元素。前缀异或的组合只能覆盖部分子集异或，无法完整表示整个异或空间，容易遗漏更优组合，甚至因排序逻辑缺陷生成错误值。
2. 数据类型溢出风险：
   若代码使用int而非long long存储数值，处理接近或超出int范围的数时会溢出，导致负数被错误当作大数参与排序和计算，最终输出异常的“过大值”。

正确解法思路 #

最终能得到的所有元素，都是原序列线性基生成的异或值（包括原序列本身的元素）。解决步骤为：

1. 构建线性基：线性基可高效表示所有可能的子集异或值。
2. 计算最大异或值：通过线性基的贪心遍历，得到异或空间中的最大值，这就是最终序列的最大值。

线性基核心逻辑 #

• 插入操作：从高位到低位遍历每个数，若当前位未被线性基覆盖，则将该数插入基中；否则用已有的基元素异或当前数，继续处理低位。
• 求最大值：从高位到低位尝试异或基元素，若异或后结果更大，则保留该操作。

修正后的代码示例 #

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

typedef long long ll;
const int MAX_BIT = 60; // 覆盖1e18以内的数值范围

ll basis[MAX_BIT];

void insert(ll x) {
    for (int i = MAX_BIT - 1; i >= 0; --i) {
        if ((x >> i) & 1) {
            if (!basis[i]) {
                basis[i] = x;
                break;
            } else {
                x ^= basis[i];
            }
        }
    }
}

ll get_max_xor() {
    ll res = 0;
    for (int i = MAX_BIT - 1; i >= 0; --i) {
        if ((res ^ basis[i]) > res) {
            res ^= basis[i];
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        memset(basis, 0, sizeof(basis));
        int n;
        cin >> n;
        ll max_original = 0;
        for (int i = 0; i < n; ++i) {
            ll x;
            cin >> x;
            max_original = max(max_original, x);
            insert(x);
        }
        ll max_possible = get_max_xor();
        cout << max(max_original, max_possible) << '\n';
    }
    return 0;
}

原思路错误案例分析 #

假设你用int存储数值，输入序列包含2147483648（超出int范围），该数会溢出为-2147483648。降序排序时负数会排在正数前面，导致cur初始值为负数，后续异或操作生成错误结果，最终输出看起来“过大”的异常值。改用long long即可避免这类问题。

内容的提问来源于stack exchange，提问作者Szyszka947