← 返回题目列表

Codeforces · 1870/E

E. 另一个 MEX 问题

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

给定一个整数数组 $$$a$$$,大小为 $$$n$$$。您可以选择给定数组的一组不重叠的子数组(请注意,某些元素可能不包含在任何子数组中,这是允许的)。对于每个选定的子数组,计算其元素的 MEX,然后计算所有获得的 MEX 值的按位异或。可以获得的最大按位异或是多少?

数组的 MEX(排除最小值)是不属于该数组的最小非负整数。例如:

- $$$[2,2,1]$$$ 的 MEX 是 $$$0$$$,因为 $$$0$$$ 不属于该数组。
- $$$[3,1,0,1]$$$ 的 MEX 是 $$$2$$$,因为 $$$0$$$ 和 $$$1$$$ 属于数组,但 $$$2$$$ 不属于该数组。
- $$$[0,3,1,2]$$$ 的 MEX 是 $$$4$$$,因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 属于数组,但 $$$4$$$ 不属于该数组。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5000$$$) — 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 5000$$$) — 数组 $$$a$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$) — 数组 $$$a$$$。

保证所有测试用例中所有 $$$n$$$ 值的总和不超过 $$$5000$$$。

输出

对于每个测试用例,输出一个数字 — 所选子数组的 MEX 值的最大可能异或。

示例

输入 #1

4
2
1 0
10
1 2 0 7 1 2 0 2 4 3
10
2 1 0 7 1 2 0 2 4 3
3
1 2 1

输出 #1

2
6
7
0

注意

在第一个测试用例中,如果我们采用整个数组 $$$\operatorname{MEX}([1, 0]) = 2$$$,则最大 XOR 为 $$$2$$$。

在第二个测试用例中,如果我们将数组分为 $$$[1, 2, 0]$$$ 和 $$$[7, 1, 2, 0, 2, 4, 3]$$$ 段,则最大 XOR 为 $$$6$$$:

- $$$\操作员名称{MEX}([1, 2, 0]) = 3$$$,
- $$$\操作员名称{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$$$,

在第三个测试用例中,如果我们将数组分为 $$$[1, 0]$$$ 和 $$$[7, 1, 2, 0, 2, 4, 3]$$$ 段,则最大 XOR 为 $$$7$$$:

- $$$\operatorname{MEX}([1, 0]) = 2$$$,
- $$$\操作员名称{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$$$,