← 返回题目列表

AtCoder · wtf22_day2_e

E. 相邻异或游戏

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

分数: 2500 点

问题陈述

你被给予 N 非负整数 A_1,A_2,\cdots,A_N。 对于每个 k=1,2,\cdots,N,解决以下问题。

爱丽丝和鲍勃玩以下游戏。

  • 爱丽丝选择 k 号码来自 A_1,A_2,\cdots,A_N。 让 x_1,x_2,\cdots,x_k 作为被选中的数字(顺序任意)。

  • 鲍勃形成一个序列 2k 非负整数 y=(y_1,y_2,\cdots,y_{2k}),必须满足以下条件。

    • 0 \leq y_1 \leq y_2 \leq \cdots \leq y_{2k}.
    • 让 z_i=y_{2i-1} \oplus y_{2i}。然后, \{z_1,z_2,\cdots,z_k\} 与 \{x_1,x_2,\cdots,x_k\} 作为一个多重集合。

在这里, \oplus 表示按位 \mathrm{XOR}.

让 分数 本实验的 游戏的值为 y_{2k}。 鲍勃的目标是最小化分数。 考虑到这一点,爱丽丝的目标是最大化分数。 分数会是多少?

什么是按位 \mathrm{XOR}?

按位 \mathrm{XOR} 非负整数 A 和 B, A\ \mathrm{XOR}\ B定义如下。

  • 当 A\ \mathrm{XOR}\ B 以二进制形式写入, k- 第最低位 (k \geq 0) 是 1 如果恰好是其中之一 k- 第最低位 A 和 B is 1,和 0 否则。
例如, 3\ \mathrm{XOR}\ 5 = 6 (二进制: 011\ \mathrm{XOR}\ 101 = 110).
一般来说,按位 \mathrm{XOR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k),可以证明它与顺序无关 p_1, p_2, p_3, \dots p_k.

约束

  • 1 \leq N \leq 250000
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \cdots A_N

输出

打印答案。


示例输入 1

3
1 2 3

示例输出 1

2
6
6

考虑这种情况 例如 k=1.

  • 如果爱丽丝选择 x_1=1:鲍勃做出 y=(0,1),得分为 1.
  • 如果爱丽丝选择 x_1=2:鲍勃做出 y=(0,2),得分为 2.
  • 如果爱丽丝选择 x_1=3:鲍勃做出 y=(1,2),得分为 2.

因此,爱丽丝将选择 x_1=2 or x_1=3,得分为 2.

考虑这种情况 例如 k=2。 如果爱丽丝选择 (x_1,x_2)=(2,3) 而鲍勃做出 y=(1,2,4,6),分数将为 6。 这是双方最佳玩法的一个例子,答案是 6.

考虑这种情况 例如 k=3。 如果爱丽丝选择 (x_1,x_2,x_3)=(1,2,3) 而鲍勃做出 y=(0,1,1,2,4,6),分数将为 6。 这是双方最佳玩法的一个例子,答案是 6.


示例输入 2

5
1 1 1 1 1

示例输出 2

1
3
5
7
9

示例输入 3

5
1 2 4 8 16

示例输出 3

16
24
28
30
31

示例输入 4

20
167660508 377125547 866003430 419036363 234113368 201296307 408194538 249252693 207212853 190504619 306027011 652875643 335898069 545795899 204268068 274532279 342039277 975300308 901270584 360957186

示例输出 4

536870912
1610612736
2684354560
3758096384
4831838208
4831838208
4831838208
4831838208
4831838208
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664