CF 1052 div2 A、B题题解

talent_wei · 2025-10-20 19:04:13 · 题解

为什么把 AB 题放在一起说？后面会提到。

首先先看 A 题。

题意简述：给定一个长度为 n 的序列 a，其中 1 \le a_i \le n，定义一个序列是平衡的，当且仅当这个序列中出现的所有元素的数量相同。求 a 的最长平衡子序列。n \le 100 。

题解：首先我们发现一个性质：如果我们已经钦定了值为多少的元素会被选，那么我们一定是取这些值的出现个数的最小值那个作为任意一个的出现次数。换一种想法，如果我们已经知道了我们每一个值都会取 k 个相应元素，那么我们肯定会尽可能多的选上所有出现次数 >= k 的所有元素。

通过上面的性质分析，容易发现我们取的 k 一定是所有出现值的出现次数中的一个。当我们确定 k 的时候我们可以简单算出答案。

具体实现：我们对于所有的值做一个桶，然后进行从小到大排序。排序之后对于每一个下标 x，我们的每一个值出现次数是 a_x 的最优答案就是 (n - i + 1) \times a_x。

时间复杂度： O(n \log n)

提交记录 - CF2146A

回头看一下这个题的思想：我们为什么可以做出来？根本原因是这个题的性质很强。我们可以轻松知道怎样是最优的。所以我们可以通过简单枚举进行计算。

然后是 B 题。

题意简述： 给你 n 个集合 S_1, S_2, \ldots, S_n，其中每个集合里的元素是 1 到 m 之间的整数。

你需要选择一些集合（可以一个都不选，也可以全选），使得从 1 到 m 的每个整数至少在一个被选中的集合中出现。

请判断是否有至少三种不同的方式选择集合，使上述条件成立。

• 所有测试用例中 \sum n 不超过 5 \cdot 10^4；
• 所有测试用例中 \sum m 不超过 10^5；
• 所有测试用例中 \sum L 不超过 2 \cdot 10^5。

题解：题目要求我们判断是否有 3 种方式选择集合，所以不妨先考虑是不是存在一种方式选择集合。容易发现我们所有的集合全都选上是更容易满足题目要求的。所以我们先判断是不是所有的集合并起来是集合 1-m。

然后我们考虑其他两种情况。首先，n \ge 2，所以两外两种情况一定是删除一个集合（因为删除两个就不如分别删除这两个）。所以我们可以枚举所有的集合，看一看哪些可以被删除。判断的依据很简单：如果存在一个 x，使得 x 只在集合 i 中出现，那么集合 i 不能被删除，否则可以。

提交记录 - CF2146B

这个题为什么可以这样做：因为我们对于 "至少 3 个" 的限制做了很好的转化。说白了也是题目的性质很强，我们知道怎么是最优的。所以可以轻松判断。

这两个题的共性也就出来了：都是题目描述 / 性质很强，并且容易构造最优化方案。