D. Co-growing Sequence | 喵喵的位运算魔法 ✨
哈喽，各位主人~ 🐾 今天我们来看一道关于位运算的有趣题目，喵~ 这道题叫做 "Co-growing Sequence"，听起来是不是有点小复杂？别担心，跟着本喵的爪印，一步一步就能搞明白啦！
题目大意
题目给了我们一个整数序列 x，要求我们找到另一个序列 y，让它和 x “共同成长”（co-growing）。
那什么是 “共同成长” 呢？就是把 x 和 y 对应位置的数做按位异或（XOR, ⊕）运算，得到一个新的序列 z（也就是 z_i = x_i ⊕ y_i）。如果这个 z 序列是 “成长” 的，那么 x 和 y 就是 “共同成长” 的。
一个序列 a 是 “成长” 的，如果对于任意相邻的两个数 a_i 和 a_{i+1}，都有 a_i & a_{i+1} = a_i。这里的 & 是按位与（AND）运算哦。
这个条件 a_i & a_{i+1} = a_i 的意思是，a_i 二进制表示中所有为 1 的位，在 a_{i+1} 的对应位置也必须是 1。就像小树苗长成大树，原来的枝丫都还在，只会多出新的枝丫，不会减少，喵~
我们的任务，就是在所有满足条件的 y 序列中，找到一个字典序最小的。也就是说，我们要让 y_1 尽可能小，在 y_1 最小的前提下让 y_2 尽可能小，以此类推。是不是很简单呀？那就让我们开始分析吧！ฅ'ω'ฅ
解题思路
要找字典序最小的 y 序列，我们就要用贪心的思想，从 y_1 开始，一个一个地确定它们的值，并且每一步都让当前的 y_i 尽可能小，喵~
我们先来处理第一个数 y_1。为了让 y_1 最小，我们当然是选 y_1 = 0 啦！这是最小的非负整数了嘛。
接下来，我们来考虑如何确定 y_i（当 i > 1 时）。我们已经知道了 x_i，也知道了前一个 z 序列的项 z_{i-1} = x_{i-1} ⊕ y_{i-1}。我们的目标是：
- 找到一个
y_i，使得z_i = x_i ⊕ y_i满足z_{i-1} & z_i = z_{i-1}。 - 这个
y_i必须是满足条件 1 的所有数中最小的那个。
让我们把条件 z_{i-1} & z_i = z_{i-1} 拆开，从二进制的每一位来分析。对于第 k 位（从右往左数，从 0 开始）：
✨ 如果 z_{i-1} 的第 k 位是 0： 那么 z_{i-1} 的第 k 位 & z_i 的第 k 位，结果肯定是 0，条件 0 & z_i[k] = 0 恒成立。所以 z_i 的第 k 位可以是 0 也可以是 1。为了让 y_i 最小，我们当然希望 y_i 的第 k 位是 0。这时 z_i[k] = x_i[k] ⊕ 0 = x_i[k]。所以，我们选择 y_i 的第 k 位为 0。
✨ 如果 z_{i-1} 的第 k 位是 1： 为了满足条件 1 & z_i[k] = 1，z_i 的第 k 位必须是 1！这是强制的要求，喵呜~ 所以我们必须有 x_i[k] ⊕ y_i[k] = 1。
- 如果
x_i的第k位是 0，那么为了0 ⊕ y_i[k] = 1，y_i的第k位必须是 1。 - 如果
x_i的第k位是 1，那么为了1 ⊕ y_i[k] = 1，y_i的第k位必须是 0。这也是我们想要的，因为它能让y_i更小！
总结一下我们对 y_i 第 k 位的选择：
- 当
z_{i-1}的第k位是 0 时，y_i的第k位是 0。 - 当
z_{i-1}的第k位是 1 时：- 若
x_i的第k位是 0，则y_i的第k位是 1。 - 若
x_i的第k位是 1，则y_i的第k位是 0。
- 若
喵~ 各位主人有没有发现，y_i 的第 k 位被设为 1，有且仅有一种情况：z_{i-1} 的第 k 位是 1，并且 x_i 的第 k 位是 0。
这可以用一个简洁的位运算来表示！y_i 的第 k 位为 1 当且仅当 z_{i-1} 的第 k 位为 1 且 x_i 的第 k 位为 0。x_i 的第 k 位为 0，就等价于 ~x_i（按位取反）的第 k 位为 1。所以，y_i 的第 k 位为 1 的条件就是 z_{i-1}[k] = 1 且 (~x_i)[k] = 1。
这不就是按位与（AND）运算嘛！所以，我们得到了一个超级优雅的公式：y_i = z_{i-1} & (~x_i)。
所以我们的算法就很清晰啦：
- 设定一个变量
prev_z来记录前一个z的值，初始为0(因为y_1是 0，所以可以认为在z_1之前有一个z_0 = 0，这样z_0 & z_1 = 0 & z_1 = 0 = z_0总是成立的)。 - 遍历输入的
x序列，对于每个x_i： a. 计算y_i = prev_z & (~x_i)。 b. 输出y_i。 c. 更新prev_z为x_i ⊕ y_i，为下一次计算做准备。
这样，我们就能一步步构造出字典序最小的 y 序列啦！是不是很神奇？这就是位运算的魔法，喵~ 🪄
题解代码
下面就是具体的代码实现啦，本喵已经加上了可爱的注释，方便主人理解哦~
#include <iostream>
// 快点快点，要开始解题啦，喵~
void solve() {
int n;
std::cin >> n;
// 我们需要一个变量来记住上一个 z_i 的值，就叫它 prev_z 吧！
// 初始时，可以认为 y_1 前面有个 z_0 = 0，这样对 z_1 没有任何限制。
int prev_z = 0;
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
// 这就是我们推导出的魔法公式喵！
// y_i 的某一位是 1，当且仅当 prev_z 的对应位是 1，而 x 的对应位是 0。
// 这正是为了满足 z_{i-1} & z_i = z_{i-1} 这个条件，同时让 y_i 最小。
// ~x 就是按位取反，所以 y = prev_z & (~x) 就实现了这个逻辑。
int y = prev_z & (~x);
// 输出计算出的 y_i，记得处理好空格哦！
std::cout << y << (i == n - 1 ? "" : " ");
// 计算当前的 z_i = x_i ⊕ y_i
int current_z = x ^ y;
// 更新 prev_z，为下一轮循环做准备，喵~
prev_z = current_z;
}
std::cout << "\n";
}
int main() {
// 加速一下输入输出，不然要超时啦 >_<
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}知识点小鱼干
做完题啦，来和喵喵一起学习一下这道题里用到的知识点吧！巩固一下才能变得更强哦！
1. 位运算 (Bitwise Operations) 🐱
位运算是直接对整数在内存中的二进制位进行操作，速度非常快，是算法竞赛中的常客喵！
- 按位与 (AND,
&): 只有当两个操作数的对应位都为 1 时，结果的对应位才为 1。例如1010 & 1100 = 1000。在题目中，a & b = a意味着a是b的一个 "子集"，a中为 1 的位，b中也必须为 1。 - 按位异或 (XOR,
^): 当两个操作数的对应位不同时，结果的对应位为 1。它有一个很棒的性质：a ^ b = c等价于a ^ c = b和b ^ c = a。我们就是用这个性质来思考z_i = x_i ^ y_i的。 - 按位取反 (NOT,
~): 将操作数的所有位反转，0 变 1，1 变 0。在我们的解法中，~x_i帮助我们快速找到x_i中为 0 的位。
2. 字典序 (Lexicographical Order) 📜
字典序就像查字典一样！比较两个序列 a 和 b，我们会从第一个元素开始比较。如果 a_1 < b_1，那么序列 a 就比 b 小。如果 a_1 = b_1，就继续比较第二个元素 a_2 和 b_2，以此类推。直到找到第一个不相等的位置，那个位置上元素较小的序列就是字典序较小的序列。要求字典序最小，通常暗示着我们可以使用贪心策略。
3. 贪心算法 (Greedy Algorithm) 🍰
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。就像一只贪吃的小猫，每次都先吃掉离自己最近最好吃的小鱼干！ 在这道题里，我们的贪心策略就是：在确定 y_i 时，不考虑它对后续 y_{i+1}, y_{i+2}, ... 的影响，只专注于让当前的 y_i 取得满足条件的最小值。事实证明，这种局部最优的选择最终导向了全局最优（字典序最小的 y 序列），所以贪心是正确的！
好啦，今天的讲解就到这里啦！希望主人能有所收获，喵~ 下次再见！🐾