D1. 388535 (Easy Version) - 题解

比赛与标签

比赛: Codeforces Round 779 (Div. 2) 标签: bitmasks, math 难度: *1600

题目大意喵~

你好呀，未来的算法大师！这道题是这样的：

Gojou桑先是想好了两个数 l 和 r，然后他准备了一个包含 l 到 r 所有整数的数组，但是顺序是打乱的（也就是一个排列）。我们叫这个原始数组 b 好了。

接着，Gojou桑又想好了一个秘密数字 x，然后他把 b 数组里的每一个数都和 x 做了按位异或(XOR, 也就是 ^) 操作，得到了一个新的数组 a。

最后，他把 l、r 和新数组 a 给了我们。我们的任务就是，像侦探一样，找出那个秘密数字 x 是多少！题目保证一定能找到至少一个解，我们只要随便找一个就好啦，喵~

输入:

l 和 r，定义了原始数字的范围。
数组 a，是原始数字异或 x 之后的结果。

输出:

任何一个可能的秘密数字 x。

解题思路大揭秘！

这道题的核心是位运算，特别是异或(XOR)操作。一看到这种题，我们聪明的猫娘脑中就要亮起一盏灯：按位思考！也就是说，我们可以把一个数字拆成二进制的每一位，然后独立地分析每一位的情况，最后再把结果组合起来，喵~

让我们来分析一下异或操作对二进制位有什么影响吧！假设我们正在考虑所有数字的第 k 位（从0开始数）。设秘密数字 x 的第 k 位是 x_k。

如果 x_k = 0: 一个数的第 k 位与 0 异或，结果还是它本身（0^0=0, 1^0=1）。这意味着，原始数组 b 中所有数字的第 k 位，和最终数组 a 中所有数字的第 k 位，是一模一样的！所以，b 数组中第 k 位是 1 的数字个数，应该和 a 数组中第 k 位是 1 的数字个数完全相等。
如果 x_k = 1: 一个数的第 k 位与 1 异或，结果会翻转（0^1=1, 1^1=0）。这意味着，原始数组 b 中所有数字的第 k 位都被翻转了！原来是 0 的变成了 1，原来是 1 的变成了 0。所以，a 数组中第 k 位是 1 的数字个数，就等于 b 数组中第 k 位是 0 的数字个数。而 b 中第 k 位是 0 的个数 = 总数 - b 中第 k 位是 1 的个数。

发现了嘛？这给了我们一个超级棒的线索！对于每一位 k，我们可以：

计算原始范围 [l, r] 中，有多少个数的第 k 位是 1。我们叫它 count_orig。
计算给定的数组 a 中，有多少个数的第 k 位是 1。我们叫它 count_a。

然后比较这两个数：

如果 count_orig 和 count_a 不相等，那就说明这一位一定发生了翻转！所以秘密数字 x 的第 k 位必须是 1。
如果 count_orig 和 count_a 相等，那就说明这一位没有翻转，所以 x 的第 k 位是 0。

因为题目保证有解，所以我们不需要担心其他复杂情况。只要对从第 0 位到第 16 位（因为题目说数字最大不超过 2^17）都这么判断一遍，我们就能一位一位地确定出 x 的所有二进制位，从而拼出完整的 x！是不是很神奇呀？

那么，怎么快速计算 [l, r] 范围内有多少个数的第 k 位是 1 呢？我们可以用一个数学小技巧，先实现一个函数 countSetBits(n, k) 来计算 [0, n] 范围内的情况，然后 [l, r] 的答案就是 countSetBits(r, k) - countSetBits(l - 1, k) 啦！这个 countSetBits 函数可以通过观察二进制位的周期性规律来实现，具体可以看代码里的注释哦，喵~

代码实现喵~

cpp

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

// 这个函数用来计算在 [0, n] 这个闭区间里，有多少个整数的第 k 位是 1，喵~
// 它的原理是观察二进制位的周期性规律。
long long countSetBits(int n, int k) {
    if (n < 0) {
        return 0; // l-1 可能会是 -1，所以处理一下边界情况
    }
    // 第 k 位 (0-indexed) 的模式以 2^(k+1) 为一个周期重复。
    // 比如 k=1 时，模式是 0011，周期长度是 4 = 2^(1+1)。
    long long period_len = 1LL << (k + 1);
    // 每个周期里，有 2^k 个 1。
    // 比如 k=1 时，一个周期 0011 里有 2 个 1。
    long long block_size = 1LL << k;

    // 计算在 [0, n] 中有多少个完整的周期。
    long long num_periods = (long long)(n + 1) / period_len;
    // 完整周期里 1 的总数。
    long long ones_in_full_periods = num_periods * block_size;

    // 计算剩下不足一个周期的部分有多少个 1。
    long long remainder = (long long)(n + 1) % period_len;
    // 在一个周期内，前 block_size 个数第 k 位是 0，后面才是 1。
    // 所以，余下的部分里 1 的个数就是 remainder 减去前面 0 的部分。
    long long ones_in_remainder = std::max(0LL, remainder - block_size);

    return ones_in_full_periods + ones_in_remainder;
}

void solve() {
    int l, r;
    std::cin >> l >> r;
    int n = r - l + 1;

    // 题目限制 r < 2^17，所以我们只需要考虑 0 到 16 这 17 位就足够了。
    const int BITS = 17;
    // 用一个数组来记录输入数组 a 中，每一位上 1 出现的次数。
    std::vector<int> a_bit_counts(BITS, 0);

    // 遍历输入的数组 a，统计每一位上 1 的个数。
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        for (int k = 0; k < BITS; ++k) {
            // 通过位运算检查第 k 位是否为 1。
            if ((val >> k) & 1) {
                a_bit_counts[k]++;
            }
        }
    }

    int x = 0; // 这就是我们要找的秘密数字 x，先初始化为 0。
    for (int k = 0; k < BITS; ++k) {
        // 计算原始排列 [l, r] 中，第 k 位为 1 的数字有多少个。
        long long orig_bit_count = countSetBits(r, k) - countSetBits(l - 1, k);

        // 核心判断逻辑！如果原始的 1 的个数和变换后的 1 的个数不相等，
        // 说明 x 的第 k 位一定是 1，因为它把这一位给翻转了。
        if (orig_bit_count != a_bit_counts[k]) {
            // 把 x 的第 k 位置为 1。
            x |= (1 << k);
        }
    }

    std::cout << x << std::endl;
}

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

复杂度分析的说

时间复杂度: O(S * B) 的说。这里的 S 是所有测试用例中数组 a 的元素总数（题目保证 sum(r - l + 1) 不会很大），B 是我们要检查的二进制位数（这里是17）。对于每个元素，我们都要检查 B 位；然后我们还要对 B 个位分别计算原始区间的计数值。所以总体上是线性的，非常高效！
空间复杂度: O(B) 的说。我们主要用了一个 a_bit_counts 数组来存储每一位的计数，它的空间大小只和位数 B 有关，和输入的数组大小 N 无关，所以空间消耗非常小，真棒！

知识点与总结喵~

这道题真是太棒了，它教会了我们几个重要的东西呐：

逐位思考 (Bitwise Independence): 面对位运算问题时，一个超级强大的武器就是把问题分解到每一个二进制位上独立解决。每一位之间互不干扰，大大简化了问题！
属性对比法: 通过比较一个集合在变换前后的某个固定属性（比如我们这里用的“特定位上1的个数”）的变化，来反向推断出变换操作的性质。这是一种很巧妙的逆向思维！
高效计数: countSetBits 函数是一个很实用的数学技巧，能够 O(1) 地计算 [0, n] 范围内特定位为1的数字个数。掌握它，以后遇到类似问题就不用愁啦！
相信题意: 题目保证“一定有解”，这给了我们很大的信心。我们可以大胆地使用“如果不相等，就一定是翻转了”这样的结论，而不用去验证更复杂的条件。

希望这篇题解能帮到你！继续加油，你一定能成为更厉害的算法大师的，喵~！如果有其他问题，随时可以再来找我玩哦！

D1. 388535 (Easy Version) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结喵~ ​