题意
给你 \(n-1\) 个整数 \(a_1, a_2, \dots, a_{n-1}\) 。
你的任务是构造一个数组 \(b_1, b_2, \dots, b_n\) ，使得：
- 从 \(0\) 到 \(n-1\) 的每个整数都在 \(b\) 中出现一次；
- 对于从 \(1\) 到 \(n-1\) 的每个 \(i\) ， \(b_i \oplus b_{i+1} = a_i\) （其中 \(\oplus\) 表示整数 \(b_i \oplus b_{i+1} = a_i\) 。(其中 \(\oplus\) 表示位向 XOR 运算符）。
输入
第一行包含一个整数 \(n\) ( \(2 \le n \le 2 \cdot 10^5\) )。
第二行包含 \(n-1\) 个整数 \(a_1, a_2, \dots, a_{n-1}\) ( \(0 \le a_i \le 2n\) )。
输入的其他限制条件：从给定的序列 \(a\) 中总是可以构造出至少一个有效的数组 \(b\) 。
思路
一般来说，区间异或的题目往往和前缀有关，所以我们不妨将公式进行罗列
\[\begin{aligned} b_1 \oplus b_2 &= a_1\\ b_2 \oplus b_3 &= a_2\\ \cdots\\ b_j \oplus b_{j + 1} &= a_j\\ \end{aligned} \]把左右两边都异或起来可以推出：\(b_1 \oplus b_{j + 1} = \bigoplus\limits_{i = 1}^{j}a_i\)。
记前缀异或和 \(sum_x = \bigoplus\limits_{i = 1}^{x}a_i\)。
那么 \(b_{j + 1} = b_1 \oplus sum_{j}\)，那么实际上是只要确定了 \(b_1\) 就可以算出所有的 \(b_j\)。
题目中要求要让 \(b\) 在 \(0\sim n - 1\) 之内，这是\(b\)数组和的最小状态
所以这实际上实在寻找一个 \(b_1\) 使得异或出来的所有\(b_i\)值和越小越好。
因为\(b_i\)和\(a_i\)和\(b_1\)有关，在这里\(a\)数组我们无法改变，为了让\(b_i\)减小，只能靠修改\(b_1\)
让每一位最小化，自然最后整体就会最小化，这就是局部最优达成全局最优，贪心的思路。
所以我们对于每一位进行考虑，假设所有\(a_i\)的第 \(i\) 位为 \(1\) 的个数有\(sum1\)个，第\(i\)位为 \(0\) 的个数有\(sum2\)个。
如果说\(sum2 < sum1\)
那我们最好让\(b_1\)异或上一个 \(2^i\)，这样可以让第\(i\)位为\(0\)的\(b_i\)的个数变成\(sum1\)，为\(1\)的个数变为\(sum2\)
从而达到让\(b_i\)整体变小的结果。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+20;
int n,a[N],b[N];
inline void init()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1; i<n; i++)
{
cin>>a[i];
a[i]^=a[i-1];//前缀异或和
}
for(int i=0; i<30; i++)//枚举每一位
{
int sum1=0,sum2=0;
for(int j=1; j<n; j++)
if (a[j]>>i & 1)
sum1++;
else sum2++;
if (sum1>sum2)//这样可以减小整体该位为1的个数
b[1]+=(1<<i);
}
for(int i=2; i<=n; i++)
b[i]=a[i-1]^b[1];//根据上述公式
for(int i=1; i<=n; i++)
cout<<b[i]<<" ";
}
signed main()
{
init();
return 0;
}