题目概述

有 $N$ 名参赛者，$M$ 道题目，每道题最高 $K$ 分。已知所有参赛者的真实分数矩阵 $a_{i,j}$。

我们需要公布一部分分数，使得：

• 根据已公布的分数，可以唯一确定最终排名
• 要最小化公布的分数数量 $S$

排名规则：总分高的排名高，总分相同时编号小的排名高。

---

问题分析

核心挑战

如果我们隐藏太多分数，可能无法确定某些参赛者之间的相对排名。比如：

• 参赛者 $x$ 的真实总分高于 $y$
• 但如果我们隐藏了 $x$ 的一些低分和 $y$ 的一些高分，可能让人误以为 $y$ 的总分可能高于 $x$

问题转化

这实际上是一个约束满足问题：

• 对于任意相邻排名的参赛者 $(i, i+1)$，我们必须公布足够多的分数
• 确保：即使给未公布的分数赋最有利于 $i+1$ 的值，$i+1$ 的总分也不可能超过 $i$

---

算法思路

关键观察

1. 相邻排名是关键：如果所有相邻排名的参赛者之间的顺序都能确定，那么整个排名就确定了
2. 最坏情况分析：对于相邻的参赛者 $p$ 和 $q$（$p$ 排名高于 $q$），考虑：
   • $p$ 的未公布分数都取最小值 0
   • $q$ 的未公布分数都取最大值 $K$
   • 即使在这种情况下，$p$ 的总分仍要高于 $q$

动态规划解法

预处理

1. 计算每个参赛者的真实总分 $A[i]$
2. 按排名规则排序：总分高的在前，总分相同时编号小的在前
3. 记排序后的序列为 $id[1], id[2], \dots, id[n]$

状态设计

设 $f[i][j]$ 表示处理完前 $i$ 个参赛者，且第 $i$ 个参赛者的"调整后总分"为 $j$ 时，前 $i$ 个参赛者中最多可以隐藏的分数数量。

这里"调整后总分"是一个虚拟概念，用于处理排名约束。

状态转移

对于相邻的参赛者 $id[i-1]$ 和 $id[i]$：

• 我们需要确保 $id[i-1]$ 的排名高于 $id[i]$
• 考虑 $id[i]$ 中隐藏 $c$ 个分数的情况
• 这些隐藏的分数在最坏情况下可以给 $id[i]$ 带来最多 $K \times c$ 的额外分数
• 但同时，$id[i-1]$ 的隐藏分数会使其分数减少（最多减少其隐藏分数的总和）

通过背包DP计算所有可能的隐藏方案，找到最优解。

---

算法详解

核心代码解析

排序和初始化

std::iota(id + 1, id + n + 1, 1);
std::sort(id + 1, id + n + 1, [](int i, int j) {
    return A[i] == A[j] ? i > j : A[i] < A[j];
});

按排名从低到高排序，便于处理相邻约束。

动态规划主体

for (int i = 1; i <= n; i++) {
    memcpy(g, f, sizeof f);  // g = f[i-1]
    memset(f, ~0x3f, sizeof f);  // f[i]初始化为负无穷
    
    int op = (i > 1 && id[i] > id[i - 1]);  // 是否需要严格大于
    int lim = A[id[i]] - A[id[i - 1]] - op;  // 允许的最大分数差

背包计算可能的状态

// 使用bitset优化背包
for (int j = 1; j <= m; j++)
    for (int s = lim; s >= a[id[i]][j]; s--)
        vis[s] |= vis[s - a[id[i]][j]] << 1;

这里 vis[s] 是一个bitset，vis[s][c] = 1 表示存在一种隐藏 $c$ 个分数的方式，使得 $id[i]$ 的可见分数和为 $s$。

状态转移

for (int c = 0; c <= m; c++)
    for (int s = A[id[i]] - op, t = -1; s >= A[id[i - 1]]; s--) {
        if (vis[A[id[i]] - s - op].test(c))
            t = A[id[i]] - s - op;
        
        if (t != -1)
            Fmax(f[A[id[i]] + (K * c - t)], g[s] + c);
    }

这里在寻找最优的隐藏方案，使得排名约束得到满足。

---

正确性分析

为什么这样能保证唯一排名？

算法确保对于每对相邻排名的参赛者：

• 即使给未公布分数赋最极端的值（有利于排名低的参赛者）
• 排名高的参赛者的可能最低总分仍然高于排名低的参赛者的可能最高总分

这就保证了排名的唯一确定性。

复杂度分析

• 排序：$O(N \log N)$
• 动态规划：$O(N \cdot M \cdot (MK))$，其中 $MK \leq 10000$
• 使用bitset优化后实际运行效率较高
• 对于 $N \leq 20000, M \leq 100, K \leq 100$ 是可接受的

---

样例解析

样例1

输入：4 6 7
输出：20

需要公布20个分数。算法通过动态规划找到最优的隐藏方案，确保排名唯一性。

样例2

输入：2 1 1
输出：1

只需要公布1个分数。如果公布参赛者1的分数为1，那么无论参赛者2的分数是多少（0或1），参赛者1都排名更高。

样例3

输入：2 2 7
输出：2

需要公布2个分数。如果只公布1个，可能无法确定排名。

---

算法亮点

1. 问题转化：将排名唯一性问题转化为相邻排名的约束问题
2. 最坏情况分析：考虑未公布分数的极端取值
3. 动态规划：使用DP寻找最优的分数公布方案
4. bitset优化：高效处理背包问题
5. 虚拟分数：通过调整后总分统一处理各种情况

---

总结

这道题的核心在于理解排名唯一性的充分必要条件，即每对相邻排名的参赛者之间必须有足够的"安全边际"。

算法通过动态规划系统地探索所有可能的分数公布方案，找到满足约束且公布分数最少的最优解。这种"约束满足 + 动态规划"的思路，在解决需要保证某种全局性质的优化问题时非常有效。