← 返回题目列表

Codeforces · 2049/A

A. MEX 破坏

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

龙埃维里尔潜入巫师的城堡并发现了一个神秘的装置,他们顽皮的本能促使他们玩弄(摧毁)它......

龙 Evirir 发现了一个由 $$$n$$$ 非负整数组成的数组 $$$a_1, a_2, \ldots, a_n$$$。

在一次操作中,他们可以选择 $$$a$$$ 的一个非空子数组$$$^{\text{∗}}$$$ $$$b$$$ 并将其替换为整数 $$$\operatorname{mex}(b)$$$$$$^{\text{†}}$$$。他们想要多次使用此操作以使 $$$a$$$ 只包含零。可以证明,在问题约束下这总是可能的。

需要的最少操作次数是多少?

输入

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

每个测试用例的第一行包含一个整数$$$n$$$ ($$$1 \le n \le 50$$$),长度为$$$a$$$。

每个测试用例的第二行包含 $$$n$$$ 空格分隔的整数,$$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 100$$$)。

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

输出

对于每个测试用例,在一行上输出一个整数,使 $$$a$$$ 只包含零所需的最少操作数。

示例

输入 #1

10
4
0 1 2 3
6
0 0 0 0 0 0
5
1 0 1 0 1
5
3 1 4 1 5
4
3 2 1 0
7
9 100 0 89 12 2 3
4
0 3 9 0
7
0 7 0 2 0 7 0
1
0
2
0 1

输出 #1

1
0
2
1
1
2
1
2
0
1

注意

在第一个测试用例中,Evirir 可以选择子数组 $$$b = [1, 2, 3]$$$ 并将其替换为 $$$\operatorname{mex}(1, 2, 3) = 0$$$,将 $$$a$$$ 从 $$$[0, \underline{1, 2, 3}]$$$ 更改为 $$$[0, 0]$$$ (其中所选子数组带有下划线)。因此,答案是$$$1$$$。

在第二个测试用例中,$$$a$$$ 已经只包含 $$$0$$$s,因此不需要任何操作。

在第三个测试用例中,Evirir 可以按如下方式更改 $$$a$$$:$$$[1, \underline{0, 1, 0, 1}] \to [\underline{1, 2}] \to [0]$$$。这里,$$$\operatorname{mex}(0, 1, 0, 1) = 2$$$ 和 $$$\operatorname{mex}(1, 2) = 0$$$。

在第四个测试用例中,Evirir 可以选择 $$$b$$$ 作为整个数组 $$$a$$$,将 $$$a$$$ 从 $$$[\underline{3, 1, 4, 1, 5}]$$$ 更改为 $$$[0]$$$。