Moe's CF Life

Appearance

G. Even-Odd XOR - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 817 (Div. 4) 标签: bitmasks, constructive algorithms, greedy 难度: *1500

题目大意喵~ ​

喵~ 主人 sama，今天我们来挑战一道非常有趣的构造题哦！

题目要求我们，对于一个给定的整数 n，找到一个由 n 个互不相同的非负整数组成的数组 a。这个数组需要满足一个特殊的条件：所有位于奇数位置的元素的按位异或（XOR）和，必须等于所有位于偶数位置的元素的按行异或和。

比如说，对于 n=8，一个合法的数组可以是 4 2 1 5 0 6 7 3。

  • 奇数位置 (第1, 3, 5, 7个) 的元素是 4, 1, 0, 7，它们的异或和是 4 ^ 1 ^ 0 ^ 7 = 2。
  • 偶数位置 (第2, 4, 6, 8个) 的元素是 2, 5, 6, 3，它们的异或和是 2 ^ 5 ^ 6 ^ 3 = 2。
  • 两边的异或和相等，所以这是一个合法的答案，喵！

我们的任务就是为每个 n 找到任意一个这样的数组。

解题思路大揭秘！ ​

嘿嘿，这道题看起来有点复杂，但只要我们稍微转换一下思路，它就会变得非常清晰哦！

首先，我们把题目的条件用数学语言表达一下。设奇数位置元素的异或和为 X_odd_pos，偶数位置元素的异或和为 X_even_pos。题目要求 X_odd_pos = X_even_pos。

喵~ 如果我们把这两个相等的数再异或一次，会发生什么呢？ X_odd_pos ^ X_even_pos = 0 （因为 A ^ A = 0）

而 X_odd_pos ^ X_even_pos 不就是整个数组所有元素的异或和嘛！ 所以，题目的条件等价于：整个数组 a 的所有元素的异或和为 0！

这下问题就变得简单多啦，对吧？我们只需要构造一个包含 n 个不同非负整数的数组，使其总异或和为 0 就行了。

为了构造这个数组，我们可以利用一个关于异或前缀和的奇妙性质。我们定义 S(k) = 0 ^ 1 ^ 2 ^ ... ^ k。这个 S(k) 的值是有一个非常规律的周期的，周期为 4：

  • 当 k % 4 == 0 时, S(k) = k
  • 当 k % 4 == 1 时, S(k) = 1
  • 当 k % 4 == 2 时, S(k) = k + 1
  • 当 k % 4 == 3 时, S(k) = 0

有了这个强大的工具，我们就可以根据 n 除以 4 的余数来分情况讨论啦！

情况一：n % 4 == 0 ​

这是最简单的情况！我们可以尝试构造最简单的数组：0, 1, 2, ..., n-1。 这个数组的总异或和就是 S(n-1)。 因为 n % 4 == 0，所以 (n-1) % 4 == 3。根据我们的公式，S(n-1) = 0！ 哇！简直是完美！这些数互不相同，非负，且总异或和为 0。问题解决！

情况二：n % 4 == 3 ​

这种情况也很友好。如果我们还用 0, 1, ..., n-1，总异或和是 S(n-1)。此时 (n-1) % 4 == 2，所以 S(n-1) = n，不为 0。 那我们换个思路，试试 1, 2, ..., n 呢？ 总异或和为 1 ^ 2 ^ ... ^ n，这等于 (0 ^ 1 ^ ... ^ n) ^ 0 = S(n) ^ 0 = S(n)。 因为 n % 4 == 3，所以 S(n) = 0！ 又成功啦！我们真是太聪明了，喵！

情况三：n % 4 == 1 ​

这下有点棘手了。上面两种简单的构造方法都不行了。 不过没关系，我们可以先构造数组的前 n-2 个元素，然后再想办法确定最后两个。 让我们先用 0, 1, ..., n-3 作为数组的前 n-2 个元素。它们的异或和是 X_prefix = S(n-3)。 因为 n % 4 == 1，所以 (n-3) % 4 = (1 - 3 + 4) % 4 = 2。 所以 X_prefix = (n-3) + 1 = n-2。 现在我们需要找到两个新的、互不相同、且不在这 n-2 个数里的数，我们叫它们 A 和 B。它们需要满足 X_prefix ^ A ^ B = 0，也就是 A ^ B = X_prefix = n-2。 怎么找到这样的 A 和 B 呢？我们可以用一个“大数”技巧！ 我们让 A 是一个非常大的数，比如 P = 1 << 29 (即 2 的 29 次方)。这个数足够大，肯定不会和 0, ..., n-3 里的任何数重复。 然后，我们就可以计算出 B = X_prefix ^ P = (n-2) ^ P。 因为 P 很大，B 也会是一个很大的数，它既不等于 P（因为 n-2 不为0），也和前面的小数们不同。 这样，我们构造的数组就是 0, 1, ..., n-3, P, (n-2)^P。所有条件都满足啦！

情况四：n % 4 == 2 ​

这是最棘手的情况，但我们不怕！ 如果我们像上一种情况一样，用 0, 1, ..., n-3 作为前缀，它们的异或和是 S(n-3)。 因为 n % 4 == 2，所以 (n-3) % 4 = (2 - 3 + 4) % 4 = 3。 所以 S(n-3) = 0。 这意味着我们需要找两个不同的数 A 和 B，使得 0 ^ A ^ B = 0，即 A ^ B = 0。这只有在 A = B 时才成立，但题目要求所有数互不相同！这可不行呀！ 所以，我们需要换一个前缀，让它的异或和不为 0。 我们可以尝试用 0, 1, ..., n-4，再加上一个 n-2。这个前缀的长度也是 n-2。 它的异或和是 X_prefix' = S(n-4) ^ (n-2)。 因为 n % 4 == 2，所以 (n-4) % 4 = 2。S(n-4) = (n-4) + 1 = n-3。 所以 X_prefix' = (n-3) ^ (n-2)。两个相邻整数的异或值永远不为 0，太棒了！ 现在我们又回到了熟悉的情景：找两个数 A 和 B，使得 A ^ B = X_prefix'。 我们再次使用大数技巧：令 A = P = 1 << 29，则 B = X_prefix' ^ P。 最终的数组就是 0, 1, ..., n-4, n-2, P, ((n-3)^(n-2))^P。搞定！

代码实现喵！ ​

下面就是把我们的聪明才智变成代码的时刻啦！

cpp
#include <iostream>
#include <vector>
#include <numeric>

// 这个函数是我们的秘密武器哦，用来计算 0 ^ 1 ^ ... ^ k 的值
// S(k) = 0 ^ 1 ^ ... ^ k
// k mod 4 = 0 -> S(k) = k
// k mod 4 = 1 -> S(k) = 1
// k mod 4 = 2 -> S(k) = k+1
// k mod 4 = 3 -> S(k) = 0
int get_xor_sum_up_to(int k) {
    if (k < 0) {
        return 0;
    }
    int rem = k % 4;
    if (rem == 0) {
        return k;
    }
    if (rem == 1) {
        return 1;
    }
    if (rem == 2) {
        return k + 1;
    }
    // rem == 3
    return 0;
}

void solve() {
    int n;
    std::cin >> n;

    int rem_n = n % 4;
    
    // 情况一: n = 4k
    // 构造 0, 1, ..., n-1。它们的总异或和是 S(n-1)。
    // 因为 (n-1)%4 = 3，所以 S(n-1) = 0。完美！
    if (rem_n == 0) {
        for (int i = 0; i < n; ++i) {
            std::cout << i << (i == n - 1 ? "" : " ");
        }
        std::cout << "\n";
    } 
    // 情况二: n = 4k+3
    // 构造 1, 2, ..., n。它们的总异或和是 S(n)。
    // 因为 n%4 = 3，所以 S(n) = 0。也完美！
    else if (rem_n == 3) {
        for (int i = 1; i <= n; ++i) {
            std::cout << i << (i == n ? "" : " ");
        }
        std::cout << "\n";
    } 
    // 情况三: n = 4k+1
    // 构造 0, 1, ..., n-3，再加上两个特制的数。
    // 前缀的异或和是 S(n-3) = n-2。
    // 我们需要两个数 A, B 使得 A^B = n-2。
    // 使用大数技巧：A = P, B = (n-2)^P
    else if (rem_n == 1) {
        for (int i = 0; i <= n - 3; ++i) {
            std::cout << i << " ";
        }
        int prefix_xor = get_xor_sum_up_to(n - 3); // 这就是 n-2
        int p1 = 1 << 29; // 一个足够大的数，保证不与前面的数重复
        int p2 = prefix_xor ^ p1;
        std::cout << p1 << " " << p2 << "\n";
    } 
    // 情况四: n = 4k+2
    // 构造 0, ..., n-4, n-2，再加上两个特制的数。
    // 这个前缀的异或和是 S(n-4) ^ (n-2) = (n-3) ^ (n-2)，不为0。
    // 同样使用大数技巧来构造最后两个数。
    else { // rem_n == 2
        for (int i = 0; i <= n - 4; ++i) {
            std::cout << i << " ";
        }
        std::cout << n - 2 << " ";
        int prefix_xor = get_xor_sum_up_to(n - 4) ^ (n - 2);
        int p1 = 1 << 29;
        int p2 = prefix_xor ^ p1;
        std::cout << p1 << " " << p2 << "\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 次左右来输出数字，所以时间复杂度和 n 是线性关系。总的时间复杂度就是 O(Σn)，非常快呢！
  • 空间复杂度: O(1) 的说。我们没有使用额外的数组来存储结果，而是直接边计算边输出，所以几乎不占用额外的内存空间。超级节省空间的说！

知识点与总结 (Purr-fect Takeaways) ​

这道题真是太棒了，让我们学到了很多东西喵！

  1. 核心思想转换: 最重要的一步就是把 X_odd_pos == X_even_pos 这个条件，巧妙地转换为了 Total_XOR_Sum == 0。这个思维转换是解决问题的金钥匙！
  2. 位运算性质 (Bitmask Magic): 一定要记住或者学会推导 0^1^...^k 的前缀异或和规律！这个性质在很多位运算题目中都有奇效。
  3. 构造性算法 (Constructive Crafting): 当题目要求“找到任意一个解”时，通常就是在暗示我们使用构造法。我们不需要遍历所有可能性，只需要按照一定的规则直接构建出一个合法的解即可。
  4. 大数技巧: 当需要在满足某个异或和 S 的同时保证数字不重复时，A = P, B = S^P (其中 P 是一个很大的数) 是一个非常强大的技巧。它可以帮我们轻松绕开与小数字的冲突。

希望这篇题解能帮助到主人 sama 哦！下次再一起愉快地解题吧，喵~

Released under the MIT License.

Copyright © 2024-present Moe