A. Submission is All You Need —— 详细题解

---

题目重述

你有一个多重集 $S$，包含 $n$ 个非负整数。初始得分为 $0$。可以执行以下两种操作任意次（顺序任意）：

1. 选择当前 $S$ 的一个子集 $S'$，将 $\text{sum}(S')$ 加到得分，然后删除 $S'$
2. 选择当前 $S$ 的一个子集 $S'$，将 $\text{mex}(S')$ 加到得分，然后删除 $S'$

求能获得的最大可能得分。

其中：

• $\text{sum}(T)$ = $T$ 中所有元素的和
• $\text{mex}(T)$ = 不在 $T$ 中的最小非负整数

数据范围：

• $1 \le n \le 50$
• $0 \le S_i \le 50$
• $1 \le t \le 10^3$

---

关键观察

观察 1：数值 $0$ 的特殊性

对于只包含 $0$ 的子集：

• $\text{sum}(\{0\}) = 0$，加 $0$ 分没有意义
• $\text{mex}(\{0\}) = 1$，无论有多少个 $0$，一次操作就能得 $1$ 分

因此，所有 $0$ 应该通过一次 $\text{mex}$ 操作处理，得 $1$ 分。

观察 2：数值 $x > 0$ 的处理

对于只包含 $x$ 的子集（假设 $x \ge 1$）：

• $\text{sum}(\{x\}) = x \ge 1$，得 $x$ 分
• $\text{mex}(\{x\}) = 0$（因为 $0$ 不在集合中），得 $0$ 分

显然，用 $\text{sum}$ 操作更好。

观察 3：组合操作

对于包含多个不同数值的子集：

• 如果包含 $0$，$\text{mex}$ 可能得到 $1$ 或更大的值，但不会超过 $1$（因为 $1$ 通常也存在）
• 实际上，把数值分开处理总是最优的

---

最优策略

1. 处理 $0$：如果存在 $0$，用一次 $\text{mex}$ 操作取走所有 $0$，得 $1$ 分
2. 处理 $x \ge 1$：对每个数值 $x$，用一次 $\text{sum}$ 操作取走所有值为 $x$ 的元素，得 $x \times \text{cnt}[x]$ 分

因此：

$$\text{ans} = [\text{cnt}[0] > 0] + \sum_{x=1}^{50} x \cdot \text{cnt}[x] $$

---

正确性证明

为什么分开处理是最优的？

1. 任何包含 $0$ 和其他数的子集，$\text{mex}$ 至少为 $1$，但最多不会超过 $1$（因为 $1$ 要么存在要么不存在）。而用 $\text{sum}$ 处理其他数能获得更多分。

2. 对于 $x \ge 1$，如果混在一起用 $\text{sum}$，得到的是它们的和，等于分开用 $\text{sum}$ 的和。分开处理不会损失分数。

3. 如果试图用 $\text{mex}$ 处理 $x \ge 1$，只能得到 $0$ 或 $1$ 分，远小于 $x \ge 1$。

4. 因此，最优策略就是：

   • 把所有 $0$ 打包，用一次 $\text{mex}$ 得 $1$ 分
   • 把每个正数分别打包，用 $\text{sum}$ 得自身分数

---

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        vector<int> cnt(51, 0);  // 统计每个数出现次数
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            cnt[x]++;
        }
        
        long long ans = 0;
        
        // 如果有 0，用一次 mex 操作得 1 分
        if (cnt[0] > 0) ans++;
        
        // 处理正数：用 sum 操作
        for (int x = 1; x <= 50; x++) {
            ans += (long long)x * cnt[x];
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}

---

复杂度分析

• 时间复杂度：$O(n + 50)$ 每个测试用例
• 空间复杂度：$O(50)$

---

样例验证

样例 1

n=3, S={0,1,1}
cnt[0]=1 → ans += 1
cnt[1]=2 → ans += 1×2 = 2
总得分 = 3 ✓

样例 2

n=3, S={1,2,3}
cnt[0]=0 → ans += 0
cnt[1]=1 → ans += 1
cnt[2]=1 → ans += 2
cnt[3]=1 → ans += 3
总得分 = 6 ✓

---

总结

要点	说明
核心思想	贪心：$0$ 用 $\text{mex}$，正数用 $\text{sum}$
时间复杂度	$O(n)$ 每个测试用例
难度	*800，约 3.0/10 分