A16606. Gellyfish and Forget-Me-Not
编程题
省选/NOI-
知识点
题目描述
Gellyfish 和 Flower 正在玩一个游戏。
该游戏包含两个长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$ 和 $b_1,b_2,\ldots,b_n$，以及一个长度为 $n$ 的二进制字符串 $c_1c_2\ldots c_n$。
还有一个整数 $x$，初始值为 $0$。
游戏进行 $n$ 回合。对于 $i = 1,2,\ldots,n$，每一回合如下进行：
1. 如果 $c_i = 0$，那么 Gellyfish 是该回合的操作者。否则，如果 $c_i = 1$，那么 Flower 是该回合的操作者。
2. 当前操作者必须执行以下两个操作之一：
* 将 $x := x \oplus a_i$；
* 将 $x := x \oplus b_i$。
这里，$⊕$ 表示按位异或操作。
Gellyfish 希望使 $x$ 的最终值尽可能小，而 Flower 则希望使它尽可能大。
如果双方都采取最优策略，求 $n$ 回合后 $x$ 的最终值。
该游戏包含两个长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$ 和 $b_1,b_2,\ldots,b_n$，以及一个长度为 $n$ 的二进制字符串 $c_1c_2\ldots c_n$。
还有一个整数 $x$，初始值为 $0$。
游戏进行 $n$ 回合。对于 $i = 1,2,\ldots,n$，每一回合如下进行：
1. 如果 $c_i = 0$，那么 Gellyfish 是该回合的操作者。否则，如果 $c_i = 1$，那么 Flower 是该回合的操作者。
2. 当前操作者必须执行以下两个操作之一：
* 将 $x := x \oplus a_i$；
* 将 $x := x \oplus b_i$。
这里，$⊕$ 表示按位异或操作。
Gellyfish 希望使 $x$ 的最终值尽可能小，而 Flower 则希望使它尽可能大。
如果双方都采取最优策略，求 $n$ 回合后 $x$ 的最终值。
输入格式
每个测试包含多个测试用例。第一行是一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。接下来的内容为各个测试用例的描述。
每个测试用例的第一行是一个整数 $n$（$1 \le n \le 10^5$）——游戏的回合数。
第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$0 \le a_i < 2^{60}$）。
第三行包含 $n$ 个整数 $b_1, b_2, ..., b_n$（$0 \le b_i < 2^{60}$）。
第四行是一个长度为 $n$ 的二进制字符串 $c$。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。
每个测试用例的第一行是一个整数 $n$（$1 \le n \le 10^5$）——游戏的回合数。
第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$0 \le a_i < 2^{60}$）。
第三行包含 $n$ 个整数 $b_1, b_2, ..., b_n$（$0 \le b_i < 2^{60}$）。
第四行是一个长度为 $n$ 的二进制字符串 $c$。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。
输出格式
对于每个测试用例，输出一行一个整数，表示所有 $n$ 回合结束后 $x$ 的最终值。
输入输出样例
输入 #1
5 1 0 2 0 2 12 2 13 3 11 3 6 1 2 6 2 3 010 4 1 12 7 2 4 14 4 2 0111 9 0 5 10 6 6 2 6 2 11 7 3 15 3 6 7 6 7 8 110010010
输出 #1
0 15 6 11 5
说明/提示
在第一个测试用例中，只有一轮，且 Gellyfish 是操作者。因此她会选择 $a_1$，最终 $x = 0$。
在第二个测试用例中，Flower 是两轮的操作者。她可以选择 $a_1$ 和 $b_2$，最终 $x = a_1 ⊕ b_2 = 15$。她也可以选择 $b_1$ 和 $a_2$，此时 $x = a_2 ⊕ b_1 = 15$，结果相同。
在第三个测试用例中，$a_1 = b_1$，因此 Gellyfish 无论怎么选都一样。在第二轮：
* 若 Flower 选择 $a_2$，则 $x$ 变成 $7$，Gellyfish 选择 $b_3$，最终 $x = 4$；
* 若 Flower 选择 $b_2$，则 $x$ 变成 $4$，Gellyfish 选择 $a_3$，最终 $x = 6$。
Flower 想要最大化 $x$，因此她会选 $b_2$，最终 $x = 6$。
在第二个测试用例中，Flower 是两轮的操作者。她可以选择 $a_1$ 和 $b_2$，最终 $x = a_1 ⊕ b_2 = 15$。她也可以选择 $b_1$ 和 $a_2$，此时 $x = a_2 ⊕ b_1 = 15$，结果相同。
在第三个测试用例中，$a_1 = b_1$，因此 Gellyfish 无论怎么选都一样。在第二轮：
* 若 Flower 选择 $a_2$，则 $x$ 变成 $7$，Gellyfish 选择 $b_3$，最终 $x = 4$；
* 若 Flower 选择 $b_2$，则 $x$ 变成 $4$，Gellyfish 选择 $a_3$，最终 $x = 6$。
Flower 想要最大化 $x$，因此她会选 $b_2$，最终 $x = 6$。