自动搬运

查看原文

来自洛谷，原作者为

	览遍千秋 将伤与泪汇成力化作拳

搬运于2025-08-24 21:15:52，当前版本为作者最后更新于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]};
	}
}

视频题解