← 返回题目列表

Codeforces · 2042/B

B. 彩色弹珠游戏

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

Alice 和 Bob 玩游戏。有 $$$n$$$ 个弹珠,其中第 $$$i$$$ 的颜色为 $$$c_i$$$。玩家轮流进行;爱丽丝先走,然后是鲍勃,然后是爱丽丝,然后是鲍勃,依此类推。

在他们的回合中,玩家必须拿走剩余的一颗弹珠并将其从游戏中移除。如果没有剩余弹珠(所有 $$$n$$$ 弹珠已被拿走),游戏结束。

Alice在游戏结束时的得分计算如下:

- 她为每种颜色 $$$x$$$ 获得 $$$1$$$ 点,这样她至少拿走了一个该颜色的弹珠;
- 此外,她为每种颜色 $$$x$$$ 获得 $$$1$$$ 点,这样她就拿走了该颜色的所有弹珠(当然,只考虑游戏中存在的颜色)。

例如,假设有 $$$5$$$ 弹珠,它们的颜色为 $$$[1, 3, 1, 3, 4]$$$,游戏如下:Alice 拿走 $$$1$$$-第一个弹珠,然后 Bob 拿走 $$$3$$$-rd 弹珠,然后 Alice 拿走 $$$5$$$-第一个弹珠,然后 Bob 拿走 $$$2$$$-nd弹珠,最后,爱丽丝拿走了第 $$$4$$$ 弹珠。然后,爱丽丝收到 $$$4$$$ 点:$$$3$$$ 点,因为拥有至少一个颜色为 $$$1$$$、$$$3$$$ 和 $$$4$$$ 的弹珠,以及 $$$1$$$ 点,因为拥有所有颜色为 $$$4$$$ 的弹珠。请注意,此策略不一定对双方都是最佳策略。

Alice 希望在游戏结束时最大化她的分数。鲍勃想将其最小化。两个玩家都处于最佳状态(即爱丽丝选择了一种可以让她获得尽可能多分数的策略,而鲍勃则选择了一种可以最大限度地减少爱丽丝可以获得的分数的策略)。

计算游戏结束时爱丽丝的得分。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例由两行组成:

- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 弹珠的数量;
- 第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — 弹珠的颜色。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。

输出

对于每个测试用例,打印一个整数 - Alice 在游戏结束时的得分,假设两个玩家都发挥最佳。

示例

输入 #1

3
5
1 3 1 3 4
3
1 2 3
4
4 4 4 4

输出 #1

4
4
1

注意

在示例的第二个测试用例中,所有弹珠的颜色都是不同的,因此,无论玩家如何行动,Alice 都会因为拥有两种颜色的所有弹珠而没有第三种颜色的弹珠而获得 $$$4$$$ 分。

在示例的第三个测试用例中,所有弹珠的颜色都是相同的,因此,无论玩家如何行动,Alice 都会因拥有至少一个(但不是全部)颜色为 $$$4$$$ 的弹珠而获得 $$$1$$$ 分。