Moe's CF Life

Appearance

喵~ 主人，欢迎来到我的题解小屋！今天我们要解决的是一道关于异或构造的有趣问题，嘻嘻。别担心，只要跟着我的思路，这道题就像挠猫咪下巴一样简单哦！

D. XOR Construction ​

题目大意 ​

好嘞，让本喵先来给主人解释一下题目吧！

题目会给我们一个整数 n 和一个长度为 n-1 的整数数组 a。我们的任务是，找到一个长度为 n 的数组 b，它需要满足下面两个条件喵：

  1. 数组 b 里的 n 个数字，正好是 0, 1, 2, ..., n-1 这 n 个数，每个数都只出现一次。换句话说，b 是 0 到 n-1 的一个排列。
  2. 对于数组 b 中所有相邻的元素，它们的异或值等于数组 a 中对应的元素。也就是 b_i ⊕ b_{i+1} = a_i，这里的 i 从 1 到 n-1。

题目还贴心地保证了，给定的输入一定能构造出至少一个满足条件的 b 数组。如果有很多个解，我们随便输出一个就可以啦~

解题思路 ​

拿到这道题，本喵的直觉告诉我，关键一定在那个异或关系式上！b_i ⊕ b_{i+1} = a_i。

这个式子可以变形一下，根据异或的性质 (A ⊕ B = C 等价于 A ⊕ C = B)，我们得到 b_{i+1} = b_i ⊕ a_i。

这说明什么呢？说明只要我们知道了 b 数组的第一个元素 b_1，整个 b 数组就都能确定下来啦！

你看喵：

  • b_2 = b_1 ⊕ a_1
  • b_3 = b_2 ⊕ a_2 = (b_1 ⊕ a_1) ⊕ a_2
  • b_4 = b_3 ⊕ a_3 = (b_1 ⊕ a_1 ⊕ a_2) ⊕ a_3
  • ...
  • b_i = b_1 ⊕ a_1 ⊕ a_2 ⊕ ... ⊕ a_{i-1}

为了方便，我们可以先预处理出一个前缀异或和数组，我们叫它 x 吧。

  • x_1 = 0
  • x_2 = a_1
  • x_3 = a_1 ⊕ a_2
  • ...
  • x_i = a_1 ⊕ a_2 ⊕ ... ⊕ a_{i-1}

这样，b 数组的每个元素都可以表示成 b_i = b_1 ⊕ x_i。

现在，整个问题就变成了：“如何找到那个神秘的 b_1 呢？”

这就要用到题目的第一个条件了：b 是 0 到 n-1 的一个排列。这意味着集合 {b_1, b_2, ..., b_n} 和集合 {0, 1, ..., n-1} 是完全相同的。

利用这个性质，我们可以分两种情况来讨论，就像猫咪白天和晚上有两种不同的状态一样，喵~

情况一：当 n 是奇数时 ​

当 n 是奇数时，我们可以利用集合元素的异或和来找到 b_1。 一个集合里所有元素的异或和是固定的。所以： (b_1 ⊕ b_2 ⊕ ... ⊕ b_n) = (0 ⊕ 1 ⊕ ... ⊕ (n-1))

我们把 b_i = b_1 ⊕ x_i 代入左边的式子： (b_1 ⊕ x_1) ⊕ (b_1 ⊕ x_2) ⊕ ... ⊕ (b_1 ⊕ x_n)= (b_1 ⊕ b_1 ⊕ ... ⊕ b_1) [n个b_1] ⊕ (x_1 ⊕ x_2 ⊕ ... ⊕ x_n)

因为 n 是奇数，所以 n 个 b_1 异或起来的结果就是 b_1 本身。 所以左边的式子变成了 b_1 ⊕ (x_1 ⊕ x_2 ⊕ ... ⊕ x_n)。

令 S_x = x_1 ⊕ x_2 ⊕ ... ⊕ x_n，T_{n-1} = 0 ⊕ 1 ⊕ ... ⊕ (n-1)。 我们就得到了一个关于 b_1 的方程：b_1 ⊕ S_x = T_{n-1}。 解得 b_1 = S_x ⊕ T_{n-1}。

S_x 我们可以通过预处理出的 x 数组求得。T_{n-1} 也有一个快速计算的规律哦（见下面的知识点介绍）。这样 b_1 就找到啦！

情况二：当 n 是偶数时 ​

当 n 是偶数时，n 个 b_1 异或起来就等于 0 了，上面的方法就不管用了，喵呜... S_x = T_{n-1}，这个等式里没有 b_1，我们得想个新办法。

这时候，就要祭出位运算大法了！我们可以按位来确定 b_1 的值。

对于二进制的第 j 位，我们来数一数在 {b_1, ..., b_n} 和 {0, ..., n-1} 这两个集合里，有多少个数的第 j 位是 1。因为两个集合是相同的，所以这个数量也必须相同。

  • C_j: {0, ..., n-1} 中第 j 位是 1 的数的个数。这个是可以预先计算的。
  • F_j: {x_1, ..., x_n} 中第 j 位是 1 的数的个数。这个也可以通过我们构造的 x 数组算出来。

现在我们来看 b_i 的第 j 位，它是 (b_1)_j ⊕ (x_i)_j（这里 (v)_j 表示 v 的第 j 位）。

  • 如果 b_1 的第 j 位 (b_1)_j 是 0，那么 (b_i)_j = 0 ⊕ (x_i)_j = (x_i)_j。此时 b 数组中第 j 位是 1 的个数就等于 x 数组中第 j 位是 1 的个数，也就是 F_j。所以 F_j 必须等于 C_j。
  • 如果 b_1 的第 j 位 (b_1)_j 是 1，那么 (b_i)_j = 1 ⊕ (x_i)_j。这会把 x_i 的第 j 位翻转。此时 b 数组中第 j 位是 1 的个数，就等于 x 数组中第 j 位是 0 的个数，也就是 n - F_j。所以 n - F_j 必须等于 C_j。

因为题目保证有解，所以对于每一位 j，上面两种情况必有一种成立。 我们可以遍历每一位 j（从 0 到 20 左右就足够了），计算出 C_j 和 F_j。

  • 如果 F_j 和 C_j 不相等，那必然是第二种情况成立，即 n - F_j = C_j，这说明 b_1 的第 j 位是 1。
  • 如果 F_j 和 C_j 相等，那就是第一种情况成立，b_1 的第 j 位是 0。

通过这种方式，我们就能一位一位地把 b_1 的二进制表示给构造出来，从而得到 b_1 的值。

找到 b_1 之后，剩下的就简单啦，b_i = b_1 ⊕ x_i，计算并输出整个 b 数组就好啦！是不是很清晰呀，喵~

题解代码 ​

cpp
#include <iostream>
#include <vector>
#include <numeric> // 嘻嘻，虽然代码里没用，但有时候异或求和可以用 accumulate

// 使用猫娘口癖可以让代码变得可爱喵~
using namespace std;

int main() {
    // 关掉同步流，让输入输出快一点，像小猫快跑一样！
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n - 1);
    for (int i = 0; i < n - 1; i++) {
        cin >> a[i];
    }

    // 第一步：构造 x 数组，x[i] = a[0] ^ a[1] ^ ... ^ a[i-1]
    // x[0] 对应 b_1，所以是 0
    vector<int> x(n);
    x[0] = 0;
    for (int i = 0; i < n - 1; i++) {
        x[i + 1] = x[i] ^ a[i];
    }

    // b_1 的值，我们先叫它 b1 吧
    int b1 = 0;

    if (n % 2 == 1) {
        // n 是奇数的情况，喵~
        // 计算 T_{n-1} = 0 ^ 1 ^ ... ^ (n-1)
        int k = n - 1;
        int T;
        if (k % 4 == 0) {
            T = k;
        } else if (k % 4 == 1) {
            T = 1;
        } else if (k % 4 == 2) {
            T = k + 1;
        } else { // k % 4 == 3
            T = 0;
        }

        // 计算 S_x = x[0] ^ x[1] ^ ... ^ x[n-1]
        int S = 0;
        for (int val : x) {
            S ^= val;
        }

        // b1 = T ^ S
        b1 = T ^ S;

    } else {
        // n 是偶数的情况，需要用位运算大法！
        // c[j] 记录 0..n-1 中第 j 位为 1 的个数
        // f[j] 记录 x 数组中第 j 位为 1 的个数
        vector<int> c(21, 0); 
        vector<int> f(21, 0);

        for (int i = 0; i < n; i++) {
            // 统计 0..n-1
            for (int j = 0; j < 21; j++) {
                if ((i >> j) & 1) {
                    c[j]++;
                }
            }
            // 统计 x 数组
            for (int j = 0; j < 21; j++) {
                if ((x[i] >> j) & 1) {
                    f[j]++;
                }
            }
        }

        // 逐位确定 b1
        b1 = 0;
        for (int j = 0; j < 21; j++) {
            // 如果 f[j] != c[j]，那么一定是 (b1)_j = 1 的情况
            // 也就是 n - f[j] == c[j]
            // 代码里直接判断 n - f[j] == c[j] 也可以，因为保证有解
            if (f[j] != c[j]) {
                b1 |= (1 << j);
            }
        }
    }

    // 最后，用我们求出的 b1 和 x 数组，构造并输出 b 数组
    for (int i = 0; i < n; i++) {
        cout << (b1 ^ x[i]) << (i == n - 1 ? "" : " ");
    }
    cout << "\n";

    return 0;
}

知识点介绍 ​

嘻嘻，主人，这道题里藏着一些很有用的知识点哦，让本喵来给你总结一下！

  1. 位运算 - 异或 (XOR)

    • 异或是二进制下的不进位加法，符号是 ^ 或者 ⊕。
    • 重要性质：
      • A ⊕ A = 0 (一个数和自己异或等于0)
      • A ⊕ 0 = A (一个数和0异或等于自己)
      • A ⊕ B = B ⊕ A (交换律)
      • (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) (结合律)
      • 从 A ⊕ B = C 可以推出 A ⊕ C = B 和 B ⊕ C = A。这在解方程时非常有用，就像本题解中 b_{i+1} = b_i ⊕ a_i 的推导。

  2. 前缀和思想 (Prefix Sum Idea)

    • 虽然这里用的是“前缀异或和”，但思想是相通的。通过预处理一个前缀数组，可以将依赖于前一个元素计算的 O(N) 过程，优化为 O(1) 的查询。在本题中，我们用前缀异或和 x 数组，将所有 b_i 都和 b_1 关联起来，这是解题的关键一步。

  3. 排列的性质 (Properties of Permutation)

    • 题目给出的“b 是 0 到 n-1 的一个排列”是核心约束。我们正是利用了这个排列的整体性质（比如所有元素的异或和、每一位的 1 的个数）来反推出未知量 b_1 的。

  4. 从 0 到 k 的异或和

    • T_k = 0 ⊕ 1 ⊕ ... ⊕ k 的值是有规律的，这在竞赛中是个常用的小技巧。
    • 令 m = k % 4：
      • 如果 m = 0，T_k = k
      • 如果 m = 1，T_k = 1
      • 如果 m = 2，T_k = k + 1
      • 如果 m = 3，T_k = 0
    • 记住这个规律，在需要求连续数字异或和的时候就不用傻傻地循环啦！

好啦，这次的题解就到这里！主人有没有完全明白呀？如果有任何问题，随时可以再来问我哦！喵~ (ฅ'ω'ฅ)

Released under the MIT License.

Copyright © 2024-present Moe