异或 - 题解

标签与难度

标签: 线性基, 位运算, 贪心, 构造难度: 2200

题目大意喵~

哈喵~！各位算法大师们，这道题是这样的呐：

我们有一个由 $n$ 个非负整数组成的序列 $a$ 。这些数字非常非常大，所以它们是以二进制字符串的形式给我们的。我们的任务是，分别找出两样东西：

从序列 $a$ 中挑选出一个长度为偶数的子序列，让这个子序列里所有数字的异或和最大。
从序列 $a$ 中挑选出一个长度为奇数的子序列，也让它的异或和最大。

最后，把这两个最大的异或和用二进制的形式打印出来就可以啦，喵~

举个栗子，如果序列是 {1, 2, 3}，二进制就是 {01, 10, 11}。

奇数长度的子序列有：{1} (和 1), {2} (和 2), {3} (和 3), {1,2,3} (和 0)。最大是 3。
偶数长度的子序列有：{1,2} (和 3), {1,3} (和 2), {2,3} (和 1)。最大也是 3。

解题思路分析

这道题的核心是求子序列的最大异或和，一看到这个，聪明的我我呀，DNA 就动了！这不就是线性基的经典应用嘛，喵！

但是，它加了一个额外的限制：子序列的长度必须是偶数或奇数。这就让问题变得稍微棘手了一点，因为标准的线性基只能告诉我们能凑出哪些异或和，但并不能告诉我们这个和是由多少个元素凑出来的。

怎么办呢？我们可以用一个超级巧妙的技巧来解决这个问题！既然我们关心长度的奇偶性，那我们就把这个“奇偶性”信息也编码到我们的数字里去，喵~

扩维！给数字加上“奇偶”标签

我们可以给每个数字 $a_i$ 增加一个额外的比特位，我们叫它奇偶校验位。

假设原来数字最多有 M 位，我们就把它们扩展成 M+1 位的向量。对于每个原始数字 $a_i$ ，我们构造一个新的向量 $v_i = (a_i, 1)$ 。这里，前 M 位是 $a_i$ 的二进制表示，最后一位，也就是我们的奇偶校验位，我们统一设置为 1。

为什么这么做呢？考虑一下我们取一个子序列 $\{a_{i_1}, a_{i_2}, \dots, a_{i_k}\}$ ，然后把它们对应的扩维向量 $v_i$ 进行异或：

V = v_{i_1} \oplus v_{i_2} \oplus \dots \oplus v_{i_k}

其中 $\oplus$ 表示按位异或。这个结果 $V$ 会是什么样呢？

$V$ 的前 M 位就是 $a_{i_1} \oplus a_{i_2} \oplus \dots \oplus a_{i_k}$ ，这正是我们想要的子序列异或和！而 $V$ 的奇偶校验位呢？它是 $k$ 个 1 的异或和。

如果子序列长度 $k$ 是奇数，那么奇偶校验位就是 1。
如果子序列长度 $k$ 是偶数，那么奇偶校验位就是 0。

看吧！我们成功地把子序列长度的奇偶性，转化为了扩维向量异或和中一个特定比特位的值！问题就变成了：

求一个数值部分最大的，且奇偶校验位为 0 的扩维向量。
求一个数值部分最大的，且奇偶校验位为 1 的扩维向量。

构建线性基与求解

现在，我们对所有扩维后的向量 $\{v_1, v_2, \dots, v_n\}$ 构建一个线性基。这个线性基张成的空间，就包含了所有可能由子序列凑出来的扩维向量异或和。

接下来就是最激动人心的部分了，怎么从这个线性基里找出我们想要的答案呢？

求出绝对最大异或和 V_max 首先，我们不管奇偶性，先用标准贪心法求出这个线性基能凑出的绝对最大的扩维向量。我们称之为 V_max。（方法：从 0 开始，从高位到低位贪心地与基向量异或，只要能变得更大就异或）。
分析 V_max 的奇偶性 现在我们检查 V_max 的奇偶校验位：
- 情况A：V_max 的奇偶校验位是 1 这说明，绝对最大的异或和是由一个奇数长度的子序列产生的！太棒了，我们直接就找到了奇数情况的答案，就是 V_max 的数值部分！那偶数情况的最大值呢？我们不能直接取 V_max 了。为了得到一个偶数和（奇偶校验位为 0），我们必须用 V_max（校验位为 1）再去异或上一个同样校验位为 1 的向量。为了让结果的数值部分损失最小，我们应该选择异或上整个线性基空间里数值最小的、且奇偶校验位为 1 的向量。我们叫它 SVOPO (Smallest Vector with Odd Parity in Span)。所以，偶数情况的答案就是 (V_max ⊕ SVOPO) 的数值部分。
- 情况B：V_max 的奇偶校验位是 0 同理，这说明绝对最大异或和来自一个偶数长度的子序列。我们直接找到了偶数情况的答案！而奇数情况的答案，就是用 V_max（校验位 0）去异或上 SVOPO（校验位 1），得到一个校验位为 1 的新向量。所以，奇数情况的答案是 (V_max ⊕ SVOPO) 的数值部分。
寻找 SVOPO 那这个神奇的 SVOPO 怎么找呢？首先，我们在所有奇偶校验位为 1 的基向量中，找到那个主元位（最高位的 1）最低的一个，设为 b_seed。这个 b_seed 是生成奇校验位向量的“种子”。然后，我们用这个 b_seed 从高到低去贪心地异或线性基里其他的基向量，目标是让它变得尽可能小。这样就能找到 SVOPO 啦！如果线性基里根本没有奇偶校验位为 1 的基向量，说明凑不出奇数长度的子序列，SVOPO 不存在。

总结一下我们的策略：

给所有数增加一个奇偶校验位 1。
对这些新向量构建线性基。
求出能凑出的最大向量 V_max 和最小的奇校验位向量 SVOPO。
根据 V_max 的奇偶性，一个答案就是 V_max，另一个就是 V_max ⊕ SVOPO！

是不是很优雅呢？喵~ 接下来就让我们把这个思路变成代码吧！

代码实现

cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
#include <optional>

// 定义一个足够大的位数，考虑到数字本身最多2000位，再加1位奇偶校验位
const int MAX_BITS = 2001; 

// 使用 bitset 来处理大整数的位运算，效率很高喵~
using BigInt = std::bitset<MAX_BITS>;

// 线性基结构体
struct LinearBasis {
    BigInt basis[MAX_BITS];
    int max_len = 0; // 记录原始数字的最大位数

    LinearBasis() {
        for (int i = 0; i < MAX_BITS; ++i) {
            basis[i].reset();
        }
    }

    // 插入一个扩维向量 v
    void insert(BigInt v) {
        // 从高位到低位进行高斯消元
        for (int i = MAX_BITS - 1; i >= 0; --i) {
            if (!v[i]) continue; // 如果当前位是0，跳过
            if (basis[i].none()) { // 如果这个位置的基向量是空的
                basis[i] = v; // 把它放进去
                return;
            }
            v ^= basis[i]; // 否则，用基向量消掉 v 的当前位
        }
    }

    // 查询能凑出的最大向量
    BigInt query_max() const {
        BigInt res;
        res.reset();
        // 从高位到低位贪心
        for (int i = MAX_BITS - 1; i >= 0; --i) {
            // 如果异或上基向量能让结果变大，就异或！
            // 等价于 res = std::max(res, res ^ basis[i])
            if (!res[i]) {
                res ^= basis[i];
            }
        }
        return res;
    }

    // 寻找空间中最小的、且奇偶校验位为1的向量 (SVOPO)
    std::optional<BigInt> find_svopo() const {
        BigInt svopo;
        svopo.reset();
        bool found = false;

        // 找到主元位最低的、奇偶校验位为1的基向量作为种子
        for (int i = 0; i <= max_len; ++i) {
            if (basis[i].any() && basis[i][max_len]) {
                svopo = basis[i];
                found = true;
                break;
            }
        }

        if (!found) {
            return std::nullopt; // 没找到，说明凑不出奇数长度的子序列
        }

        // 用其他基向量把 svopo 变得尽可能小
        for (int i = MAX_BITS - 1; i >= 0; --i) {
            if (svopo[i]) {
                svopo ^= basis[i];
            }
        }
        return svopo;
    }
};

// 打印 bitset，去掉前导零
void print_big_int(const BigInt& num, int max_len) {
    int first_bit = -1;
    for (int i = max_len; i >= 0; --i) {
        if (num[i]) {
            first_bit = i;
            break;
        }
    }

    if (first_bit == -1) {
        std::cout << "0\n";
    } else {
        for (int i = first_bit; i >= 0; --i) {
            std::cout << (num[i] ? '1' : '0');
        }
        std::cout << "\n";
    }
}


int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    LinearBasis lb;
    int max_len_actual = 0;
    std::vector<std::string> s(n);

    for (int i = 0; i < n; ++i) {
        std::cin >> s[i];
        max_len_actual = std::max(max_len_actual, (int)s[i].length());
    }

    // 奇偶校验位放在 max_len_actual 这个位置
    lb.max_len = max_len_actual; 

    for (int i = 0; i < n; ++i) {
        BigInt v;
        int current_len = s[i].length();
        for (int j = 0; j < current_len; ++j) {
            if (s[i][current_len - 1 - j] == '1') {
                v[j] = 1;
            }
        }
        // 设置奇偶校验位为1
        v[max_len_actual] = 1;
        lb.insert(v);
    }

    BigInt v_max = lb.query_max();
    auto svopo_opt = lb.find_svopo();

    // 偶数长度情况
    BigInt ans_even;
    if (v_max[max_len_actual] == 0) { // V_max 本身就是偶数和
        ans_even = v_max;
    } else { // V_max 是奇数和，需要异或SVOPO来翻转奇偶性
        ans_even = v_max ^ svopo_opt.value();
    }
    print_big_int(ans_even, max_len_actual - 1);

    // 奇数长度情况
    BigInt ans_odd;
    if (!svopo_opt.has_value()) { // 根本凑不出奇数长度
        ans_odd.reset();
    } else if (v_max[max_len_actual] == 1) { // V_max 本身就是奇数和
        ans_odd = v_max;
    } else { // V_max 是偶数和，需要异或SVOPO
        ans_odd = v_max ^ svopo_opt.value();
    }
    print_big_int(ans_odd, max_len_actual - 1);

    return 0;
}

复杂度分析

时间复杂度: $O(N \cdot L + L^2)$ ，其中 $N$ 是数字的数量， $L$ 是数字的最大位数（在这里是 MAX_BITS）。
- 读入和构建扩维向量需要 $O(N \cdot L)$ 。
- 每次向线性基插入一个向量，最多需要 $O(L)$ 次异或操作，每次异或操作是 $O(L)$ 的（因为 bitset 长度是 $L$ ）。但由于 bitset 操作很快，我们可以近似看作 $O(L)$ 。所以总插入时间是 $O(N \cdot L)$ 。
- 查询最大值和 SVOPO 都需要遍历线性基，复杂度是 $O(L)$ 次异或，总共是 $O(L^2)$ 。
- 所以总的时间复杂度由插入主导，为 $O(N \cdot L)$ 。
空间复杂度: $O(L^2)$ 。
- 我们用了一个 basis 数组来存储线性基，大小为 $L \times L$ 的比特位，所以空间复杂度是 $O(L^2)$ 。

知识点总结

这道题真是太有趣啦，让我们一起总结一下学到了什么吧，喵~

线性基 (Linear Basis): 解决子集异或和问题的超级神器！一定要掌握它的构建（高斯消元法）和查询（贪心法求最大/最小值）哦。
扩维思想 (Dimension Augmentation): 当遇到带有附加条件的约束时（比如本题的奇偶性），可以尝试将这个约束信息编码成一个新的维度加入到问题中。这是一种非常强大和灵活的构造技巧，能把复杂问题转化为我们熟悉模型。
异或的性质: a ^ b ^ b = a。这个性质是解决问题的关键。当我们想从一个最优解（比如 V_max）调整到满足新条件的解时，我们通过异或一个“差值”向量（比如 SVOPO）来实现，同时要让这个“差值”对结果的影响最小。
std::bitset: 处理大整数位运算的利器。当数字位数超过 unsigned long long 时，bitset 就是你的好朋友，它的位运算速度非常快！

希望这篇题解能帮到你！如果还有不明白的地方，随时可以再来问我哦，喵~ >w<

异或 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

扩维！给数字加上“奇偶”标签 ​

构建线性基与求解 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​