汉堡猫猫 - 题解

标签与难度

标签: 位运算, 动态规划, DP, 贪心, 构造, 思维题难度: 1900

题目大意喵~

主人你好呀~ 这道题是关于制作最美味的“汉堡猫猫”的！...啊不对，是关于操作数字数组的，喵~

我们有一个包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ 的数组。我们可以对数组里的任何一个数 $a_i$ 进行一种神奇的操作，而且想做多少次都行！

这个操作是这样的：

首先，选中一个数字 $a_i$ 。
然后，再选中一个二进制位的位置 $k$ (从 1 到 60)。
最后，把第 $k$ 位的值，变成它下面一位，也就是第 $k-1$ 位的值。写成公式就是 $c_k \leftarrow c_{k-1}$ 啦。

我们的目标是，通过这些操作，让整个数组所有数字的异或和（ $a_1 \oplus a_2 \oplus \dots \oplus a_n$ ）变得最大！请你告诉本喵，这个最大的异或和是多少呢？

解题思路分析

喵哈哈，最大化异或和！一看到这个，本喵的猫猫直觉就告诉窝，要从最高位开始，贪心地让它们变成 1，这样得到的数字才会最大嘛！

操作的本质是什么喵？

我们先来研究一下这个神奇的操作： $c_k \leftarrow c_{k-1}$ 。假设一个数是 ...c_3 c_2 c_1 c_0。

我们可以用 k=1，让 c_1 变成 c_0。
我们可以用 k=2，让 c_2 变成 c_1。

如果窝们先用 k=1 把 c_1 变成 c_0，数字就成了 ...c_3 c_2 c_0 c_0。这时再用 k=2，c_2 就会变成新的 c_1，也就是 c_0。数字就成了 ...c_3 c_0 c_0 c_0。

喵呜！本喵发现了一个规律！对于任意一个数 $a_i$ 和任意一个我们选定的“锚点”位 $p$ （ $0 \le p \le 60$ ），我们可以把第 $p$ 位 a_{i,p} 的值，像多米诺骨牌一样，一路向上“传染”给所有比它高的位（ $p+1, p+2, \dots, 60$ ）。而比 $p$ 低的位则保持原样。

举个栗子：a_i = ...011010 (二进制)，如果我们选第 2 位（值为 0）作为锚点，操作之后它就会变成 ...000010。所有第 2 位及以上的位都变成了 0。

所以，对于每个数 $a_i$ ，我们可以做的决策就是：

不进行任何操作。
选择一个锚点位 $p_i \in [0, 60]$ ，将 $a_i$ 改造。

贪心与动态规划的结合！

我们的目标是让最终的异或和从高位到低位尽可能都是 1。那么，让我们来思考一下，我们能达到的最棒的结果是什么形态呢？一定是从某个位 K 开始，直到最高位，所有位都是 1，像这样：0...011...1。

我们的任务就是找到这个神奇的起始位 K，并且让它尽可能地小！K 越小，高位的 1 就越多，结果就越大。

为了让最终异或和的第 $j$ 位（对于所有 $j \ge K$ ）都为 1，我们需要对每个数字 $a_i$ 选择一个锚点 $p_i$ ，使得：

所有选的锚点都不能太高，必须满足 $p_i \le K$ 。因为如果有个 $p_i > K$ ，那 $a_i$ 的第 $K$ 位就还是老样子，我们就没法控制它了。
当每个数字 $a_i$ 都根据锚点 $p_i$ 变成新数 $X_i$ 后，它们被“传染”上去的那个比特值（也就是 $a_{i, p_i}$ ）的异或和必须是 1。也就是 $\bigoplus_{i=1}^n a_{i, p_i} = 1$ 。

这个问题就转化成了：找到最小的 $K$ ，使得我们能为每个 $a_i$ 找到一个锚点 $p_i \le K$ ，并让这些锚点对应的值 $a_{i,p_i}$ 的异或和为 1。

这听起来就像一个动态规划问题了！本喵的爪子已经跃跃欲试了！

DP三部曲

状态定义: 我们从头到尾处理每个数字，需要记录的信息是：为了让目前处理过的数字的“锚点值”异或和为某个结果，所需要的max(p_i) 的最小值是多少。所以，定义 dp[b] 为：使前 i 个数选出的锚点值的异或和为 b (0 或 1) 时，这些锚点 $p_1, \dots, p_i$ 的最大值的最小值。简单来说，dp[b] 就是达成异或和 b 的最小代价（代价就是最高的锚点位置）。
状态转移: 当我们考虑第 i 个数字 a_i 时，我们可以为它选择传播 0 或者传播 1。
- 传播 0: 我们需要找到 a_i 中最低的 0 出现的位置，设为 cost_0。这就是我们为 a_i 传播 0 所需的最小锚点。
- 传播 1: 我们需要找到 a_i 中最低的 1 出现的位置，设为 cost_1。这就是传播 1 的最小锚点。
怎么快速找到这个位置呢？C++ 的 __builtin_ctzll (Count Trailing Zeros) 是我们的好朋友！__builtin_ctzll(x) 可以找到 x 最低位的 1 在哪里。那么最低位的 0 呢？只要找 ~x (按位取反) 的最低位的 1 就好啦！
现在，假设我们已经算好了前 i-1 个数的 dp_prev[0] 和 dp_prev[1]。对于第 i 个数，我们来更新 dp_curr:
- 如果前 i-1 个数的异或和是 b_prev，代价是 dp_prev[b_prev]。
- 第 i 个数选择传播 b_curr，代价是 cost_{b_curr}。
- 那么前 i 个数的异或和就是 b_prev \oplus b_curr。
- 而这 i 个锚点的最大值就是 max(dp_prev[b_prev], cost_{b_curr})。
所以转移方程就是：
$dp_{curr}[b_{prev} \oplus b_{curr}] = \min(dp_{curr}[b_{prev} \oplus b_{curr}], \max(dp_{prev}[b_{prev}], \text{cost}_{b_{curr}}))$
初始化: 在还没开始处理任何数的时候，异或和是 0，也不需要任何锚点，所以代价是 0。而要得到异或和 1 是不可能的，所以代价是无穷大（比如 61）。 dp[0] = 0, dp[1] = 61。

得到答案！

当我们处理完所有 n 个数后，dp[1] 的值就是我们心心念念的最小 K 啦！有了 K，最终的答案就是从第 K 位到第 60 位全部是 1 的数。这个数可以用 ((1ULL << 61) - 1) ^ ((1ULL << K) - 1) 来构造，或者更帅一点，用 ((1ULL << 61) - 1) >> K << K。

如果所有数一开始都是 0，那怎么操作都是 0，要特别处理一下哦，喵~

代码实现

这是本喵根据上面的思路，精心为你准备的代码~ 每一步都有注释，保证你能看懂！

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <array>

// 一个乐于助人的我写的函数，用来寻找数字中最低的0或1的位置
// b=0找0，b=1找1
int find_lowest_bit_pos(unsigned long long n, int b) {
    if (b == 1) {
        // 如果n是0，没有1，返回一个很大的值表示不可能
        if (n == 0) return 61;
        // __builtin_ctzll能超快地找到最低位的1！
        return __builtin_ctzll(n);
    } else { // b == 0
        // 找0等价于找 ~n (按位取反) 中的1
        // 如果n所有位都是1，~n就是0，没有1
        if (~n == 0) return 61;
        return __builtin_ctzll(~n);
    }
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<unsigned long long> a(n);
    bool all_zeros = true;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (a[i] != 0) {
            all_zeros = false;
        }
    }

    // 特殊情况：如果所有数都是0，那答案只能是0啦
    if (all_zeros) {
        std::cout << 0 << "\n";
        return;
    }

    // dp[b] = 达到 propagated_xor_sum 为 b 所需的 min_max_pivot
    // dp[0] 初始化为 0 (0个元素异或和为0，代价0)
    // dp[1] 初始化为 61 (不可能)
    std::array<int, 2> min_max_pivot = {0, 61};

    for (int i = 0; i < n; ++i) {
        // 计算当前数字 a[i] 传播 0 和 1 的最小锚点代价
        int cost0 = find_lowest_bit_pos(a[i], 0);
        int cost1 = find_lowest_bit_pos(a[i], 1);

        std::array<int, 2> next_min_max_pivot = {61, 61};

        // 遍历之前的异或和结果 (prev_xor_sum)
        for (int prev_xor_sum = 0; prev_xor_sum < 2; ++prev_xor_sum) {
            if (min_max_pivot[prev_xor_sum] > 60) continue; // 跳过不可能的状态

            // 尝试为 a[i] 传播 0
            int current_propagated_bit = 0;
            int new_xor_sum = prev_xor_sum ^ current_propagated_bit;
            int new_max_pivot = std::max(min_max_pivot[prev_xor_sum], cost0);
            next_min_max_pivot[new_xor_sum] = std::min(next_min_max_pivot[new_xor_sum], new_max_pivot);

            // 尝试为 a[i] 传播 1
            current_propagated_bit = 1;
            new_xor_sum = prev_xor_sum ^ current_propagated_bit;
            new_max_pivot = std::max(min_max_pivot[prev_xor_sum], cost1);
            next_min_max_pivot[new_xor_sum] = std::min(next_min_max_pivot[new_xor_sum], new_max_pivot);
        }
        min_max_pivot = next_min_max_pivot;
    }

    // K 是我们能让高位全为1的最低起始位
    int K = min_max_pivot[1];
    
    unsigned long long ans = 0;
    if (K <= 60) {
        // 构造一个从第K位到第60位都是1的数
        // (1ULL << 61) - 1 是 61 个 1
        // >> K 右移K位，清空低K位
        // << K 左移回来，高位是1，低K位是0
        ans = ((1ULL << 61) - 1) >> K << K;
    }

    std::cout << ans << "\n";
}

int main() {
    // 加速输入输出，让本喵跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 对于每个测试用例，我们遍历一次包含 $n$ 个数字的数组。在循环内部，我们执行常数次操作（计算 cost，以及一个大小为 2x2 的循环来更新DP状态）。所以总的时间复杂度是线性的，也就是 $O(N)$ ，非常快哦！
空间复杂度: $O(N)$ 我们用了一个 std::vector 来存储输入的 n 个数字，所以空间复杂度是 $O(N)$ 。DP状态本身只占用了 O(1) 的空间，因为我们每次都用 next_min_max_pivot 覆盖旧的状态。

知识点总结

这道题真有趣，像是在玩二进制的拼图游戏！我们从中可以学到：

深入理解位运算: 问题的核心是对二进制位的操作。正确分析操作的本质——“锚点传播”，是解题的第一步。
贪心思想: 最大化异或和的问题，通常从高位到低位贪心是正确的方向。我们把问题转化为寻找一个最优的形态 0...011...1。
动态规划建模: 将寻找“最小的起始位 K”这个问题，巧妙地转化为一个DP问题。DP状态的定义（最小化最大代价）是一个常见的技巧。
C++ 内建函数: __builtin_ctzll 这样的函数是处理位运算问题的神器，能极大地简化代码并提高效率。

希望本喵的题解能帮到你！如果还有问题，随时可以再来问我哦，喵~

汉堡猫猫 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

操作的本质是什么喵？ ​

贪心与动态规划的结合！ ​

DP三部曲 ​

得到答案！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​