题目解析

我们有一个由 $n$ 个彩色弹珠组成的序列，两个人轮流取弹珠，Alice 先手。
得分规则：

1. 对每种颜色 $x$，如果 Alice 至少取了一个该颜色的弹珠，得 $1$ 分。
2. 对每种颜色 $x$，如果 Alice 取走了该颜色的 所有 弹珠，再得 $1$ 分（即总共 $2$ 分）。

因此，对某种颜色：

• 如果 Alice 取走了全部，她得 $2$ 分。
• 如果 Alice 取走了一部分（但不是全部），她得 $1$ 分。
• 如果 Alice 一颗没取，她得 $0$ 分。

Bob 的目标是最小化 Alice 的得分，Alice 的目标是最大化。

---

关键观察

1. 只出现一次的弹珠（unique marbles）

如果某种颜色的弹珠数量为 $1$：

• 如果 Alice 取走它，她得 $2$ 分（至少取一个 + 取完所有）。
• 如果 Bob 取走它，Alice 得 $0$ 分。

这是一个双方都会争夺的对象。由于轮流取，这类颜色会 被双方轮流取走。
设 $u$ 为数量为 $1$ 的颜色数。
按最优玩法：

• Alice 能取到 $\lceil \frac{u}{2} \rceil$ 个这种弹珠，每个让她得 $2$ 分。
  所以这部分得分为：

$$2 \times \lceil \frac{u}{2} \rceil$$

2. 出现次数 ≥ 2 的颜色

对于数量 $≥ 2$ 的颜色，任何玩家都无法独自取完（因为双方都会取）。
一个经典的对称策略：如果上回合对方取了某个颜色的 第一个 弹珠，那么当前玩家就取同一个颜色的另一个弹珠，否则随便取一个。

这个策略保证：

• 每种这样的颜色，Alice 至少取到 $1$ 个（得 $1$ 分）。
• 但 Alice 无法取完任何这种颜色（因为 Bob 会在她第一次取完后立刻取走另一个）。
• 因此 Alice 最多得 $1$ 分每种。

设 $k$ 为数量 $≥ 2$ 的颜色数，这部分得分为：

$$k$$

---

最终公式

$$\text{score} = k + 2 \times \lceil \frac{u}{2} \rceil $$

其中 $\lceil \frac{u}{2} \rceil$ 在代码中可以用 $(u + 1)/2$ 实现整除。

---

示例验证

样例 1

$[1,3,1,3,4]$
计数：颜色 $1$: $2$ 个，颜色 $3$: $2$ 个，颜色 $4$: $1$ 个
$u = 1$，$k = 2$
得分 = $2 + 2 \times \lceil 1/2 \rceil = 2 + 2 = 4$

样例 2

$[1,2,3]$
计数：$1,1,1$
$u = 3$，$k = 0$
得分 = $0 + 2 \times \lceil 3/2 \rceil = 2 \times 2 = 4$

样例 3

$[4,4,4,4]$
计数：颜色 $4$: $4$ 个
$u = 0$，$k = 1$
得分 = $1 + 0 = 1$

---

C++ 代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<int> cnt(n, 0);
        for (int i = 0; i < n; ++i) {
            int x;
            scanf("%d", &x);
            --x; // 颜色值从 0 开始便于计数
            cnt[x]++;
        }

        int uniqueColors = 0, multipleColors = 0;
        for (int i = 0; i < n; ++i) {
            if (cnt[i] == 1) {
                uniqueColors++;
            } else if (cnt[i] > 1) {
                multipleColors++;
            }
        }

        int ans = multipleColors + ((uniqueColors + 1) / 2) * 2;
        printf("%d\n", ans);
    }
    return 0;
}