【位运算】XOR Construction—CF1895D

XOR Construction—CF1895D"/>

【位运算】XOR Construction—CF1895D

XOR Construction—CF1895D
参考文章

翻译

题目要求构造一个长度为 n n n 的数组 b b b，满足以下条件：

• 数组 b b b 中包含从 0 0 0 到 n − 1 n-1 n−1 的每个整数，且每个整数仅出现一次；
• 对于 i i i 从 1 1 1 到 n − 1 n-1 n−1， b i ⊕ b i + 1 = a i b_i \oplus b_{i+1} = a_i bi​⊕bi+1​=ai​（其中 ⊕ \oplus ⊕ 表示按位异或运算符）。

输入

第一行包含一个整数 n n n（ 2 ≤ n ≤ 2 ⋅ 1 0 5 2 \le n \le 2 \cdot 10^5 2≤n≤2⋅105）。

第二行包含 n − 1 n-1 n−1 个整数 a 1 , a 2 , … , a n − 1 a_1, a_2, \dots, a_{n-1} a1​,a2​,…,an−1​（ 0 ≤ a i ≤ 2 n 0 \le a_i \le 2n 0≤ai​≤2n）。

输入的附加限制条件：始终可以从给定序列 a a a 构造出至少一个有效的数组 b b b。

输出

输出 n n n 个整数 b 1 , b 2 , … , b n b_1, b_2, \dots, b_n b1​,b2​,…,bn​。如果存在多个满足条件的数组，可以输出其中任意一个。

思路

由 b i ⊕ b i + 1 = a i b_i \oplus b_{i+1}=a_i bi​⊕bi+1​=ai​ 得：
b 1 ⊕ b 2 = a 1 b_1 \oplus b_2=a_1 b1​⊕b2​=a1​
b 2 ⊕ b 3 = a 2 b_2 \oplus b_3=a_2 b2​⊕b3​=a2​
b 3 ⊕ b 4 = a 3 b_3 \oplus b_4=a_3 b3​⊕b4​=a3​，异或累加得：
b 1 ⊕ b i = a 1 ⊕ a 2 ⊕ a 3 ⊕ . . . ⊕ a i − 1 b_1 \oplus b_i=a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_{i-1} b1​⊕bi​=a1​⊕a2​⊕a3​⊕...⊕ai−1​，即：
b i = b 1 ⊕ a 1 ⊕ a 2 ⊕ a 3 ⊕ . . . ⊕ a i − 1 b_i=b_1 \oplus a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_{i-1} bi​=b1​⊕a1​⊕a2​⊕a3​⊕...⊕ai−1​。

因为题目保证有解，所以 b 1 b_1 b1​ 存在某个取值，使得 b b b 中元素各不相同，即 a a a 的所有前缀异或和各不相同，且不存在 0 0 0。那么我们很容易得到：
对于 b 1 b_1 b1​ 的任意取值， b b b 中元素都互不相同。

因为 every integer from 0 0 0 to n − 1 n-1 n−1 appears in b b b exactly once，而我们已经知道了 b b b 中元素互不相同，现在的任务就是保证 b b b 中元素最小化。为了达到这一目的，我们只能修改 b 1 b_1 b1​ 的大小。

让 b 1 b_1 b1​ 的二进制第 k k k 位最优，使得 b 2 , . . . , b n b_2, ..., b_n b2​,...,bn​ 中二进制第 k k k 位上的“1”的数量最小，进而使得 b b b 数组整体最小。这里使用了贪心的思路来实现（局部最优得到整体最优，二进制每一位最优得到二级制所有位最优）。

C o d e Code Code

#include <bits/stdc++.h>
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;int n;void solve(int Case) {cin >> n;vector <int> a(n + 1, 0);for (int i = 1; i <= n - 1; i ++) {cin >> a[i];a[i] ^= a[i - 1];}int b1 = 0;for (int i = 0; i <= 30; i ++) {int num1 = 0;int num0 = 0;for (int j = 1; j <= n - 1; j ++) {if (a[j] >> i & 1) {num1 ++;} else {num0 ++;}}if (num1 > num0) {b1 += 1 << i;}}cout << b1 << " ";for (int i = 2; i <= n; i ++) {cout << (a[i - 1] ^ b1) << " ";}cout << "\n";
}signed main() {cin.tie(0)->ios::sync_with_stdio(false);int T = 1;
//	cin >> T; cin.get();int Case = 0;while (++ Case <= T) solve(Case);return 0;
}