← 返回题目列表

Codeforces · 2115/D

D. 水母和勿忘我

中文机器翻译题面 查看原题

水母和花正在玩游戏。

游戏由两个 $$$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 = \mathtt{0}$$$,Gellyfish 将成为活跃玩家。否则,如果 $$$c_i = \mathtt{1}$$$,Flower 将成为活跃玩家。
  2. 活跃玩家将执行 正好一个 以下操作:
    • 设置$$$x:=x \oplus a_i$$$。
    • 设置 $$$x:=x \oplus b_i$$$。

这里,$$$\oplus$$$ 表示按位异或运算。

Gellyfish 希望在 $$$ n $$$ 轮后最小化 $$$ x $$$ 的最终值,而 Flower 希望最大化它。

如果两名玩家都发挥最佳状态,则在所有 $$$ n $$$ 轮后求 $$$ x $$$ 的最终值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 游戏的轮数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \lt 2^{60}$$$)。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \leq b_i \lt 2^{60}$$$)。

每个测试用例的第四行包含一个长度为$$$n$$$的二进制字符串$$$c$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一个整数 - 所有 $$$ n $$$ 轮后 $$$ x $$$ 的最终值。

示例

输入
复制

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

输出
复制

0
15
6
11
5

注意

在第一个测试用例中,只有一轮,Gellyfish 是该轮的活跃玩家。因此,她会选择$$$a_1$$$,$$$x$$$的最终值为$$$0$$$。

在第二个测试用例中,Flower 将是两轮中的活跃玩家。她会选择$$$a_1$$$和$$$b_2$$$,$$$x$$$的最终值为$$$a_1 \oplus b_2 = 15$$$。 Flower 也可以选择 $$$b_1$$$ 和 $$$a_2$$$ 来代替 $$$x=a_2 \oplus 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$$$的最终值,所以Flower会在第二轮选择$$$b_2$$$。因此,$$$x$$$ 的最终值为$$$6$$$。