CF1722G 题解

题目

构造一个长度为 \(n\) 的数列，数列中每个数各不相同且都不超过 \(2^{31}\)，使得奇数项和偶数项的异或和相等。

思路

我提供一种比较神奇的构造方法。

首先，两个数相等可以转化成两个数异或和为 \(0\)，那么这题就变成了，构造一个异或和为 \(0\) 的数列。

考虑将 \(n\) 个数分成若干组，每组异或和为 \(0\)，这样整个数列的异或和为 \(0\)。

我们把 \(4\) 个数分成一组，大概就是用最高 \(3\) 位构造 \(4\) 个不相同且异或和为 \(0\) 的数。

然后每组数要各不相同，所以我们用低位偏移。

所以我们就可以写出一个构造 \(4k\) 个数的函数：

void Walk (int x) { // x 为 4 的倍数
    int z = 0;
    for (int i = 1; i <= x / 4; i++) {
        int a = (1 << 30), b = (1 << 29), c = (1 << 28);
        cout << a + b + c + z << ' ' << a + b + z << ' ' << ' ' << a + c + z << ' ' << a + z << ' ';
        z++; // 偏移
    }
}

但是不能保证 \(n\) 为 \(4\) 的倍数，所以我们对 \(n\) 除以 \(4\) 的余数分类讨论：

• 余数为 \(0\)，直接 Walk(n)。
• 余数为 \(1\)，用一个 \(0\) 占位，然后 Walk(n - 1)。
• 余数为 \(2\)，构造 \(6\)个异或和为 \(0\) 的数（比如样例中的 \(1,2,3,4,8,12\)），然后 Walk(n - 6)。
• 余数为 \(3\)，构造 \(3\) 个异或和为 \(0\) 的数（比如 \(1,2,3\)），然后 Walk(n - 3)。

最后补充一下，\(3\) 个数一组应该也可以，我赛时没想到就写了一个 \(4\) 个数一组的。

代码

#include <bits/stdc++.h>
 
using namespace std;
 
int t;
int n, m;
 
void Walk (int x) {
    int z = 0;
    for (int i = 1; i <= x / 4; i++) {
        int a = (1 << 30), b = (1 << 29), c = (1 << 28);
        cout << a + b + c + z << ' ' << a + b + z << ' ' << ' ' << a + c + z << ' ' << a + z << ' ';
        z++;
    }
}
 
int main () {
    cin >> t;
    while (t--) {
        cin >> n;
        if (n % 4 == 0) {
            Walk(n);
            cout << '\n';
        }
        if (n % 4 == 1) {
            Walk(n - 1);
            cout << "0\n";
        }
        if (n % 4 == 2) {
            Walk(n - 6);
            cout << "4 1 2 12 3 8\n";
        }
        if (n % 4 == 3) {
            Walk(n - 3);
            cout << "1 2 3\n";
        }
    }   
    return 0;
}