2312H

览遍千秋 · 2023-12-14 13:28:31 · 题解

Source & Knowledge

2023 年 12 月语言月赛，由洛谷网校入门计划/基础计划提供。

考察数组、排序。

文字题解

用数组 w[i][] 存储第 i 个 Subtask 中包含的所有测试点编号。

输入完毕每个测试点的答案 A_k 后，遍历每个 Subtask，判断其中测试点答案是否相同。

假设第 i 个 Subtask 中全部的测试点答案均相同，记作 Q_i，该 Subtask 得分为 S_i，那么输出 Q_i 可以获得的分数将增加 S_i。

部分分 1

考虑求解最终的答案，需要对 Q_i 统计得分。很容易想到桶思想，用 T[x] 表示输出 x 可以得到的分数。

每找到一个测试点答案均相同的 Subtask，就将 T[Q_i] 增加 S_i，最终统计 T[x] 的最大值即可。

满分解法

注意到 Q_i 可以达到 10^9，桶无法开到这么大。

用一个结构体数组存下每一对 Q_i,S_i，所有 Subtask 扫描完毕后，按照 Q_i 排序，这样就按照 Q_i 将这个结构体数组分成了若干段，分段统计即可。

使用不超出考纲的冒泡排序，时间复杂度为 O(N+k^2)。

部分核心代码

for(int i = 1; i <= k; i++) {
    bool IsAnswerEqual = true;
    for(int j = 2; j <= p[i]; j++) {
        if(A[w[i][j - 1]] != A[w[i][j]]) {
            IsAnswerEqual = false;
        }
    }
    if(IsAnswerEqual) {
        ans[++cnt] = {A[w[i][1]], S[i]};
    }
}