算法组月赛视频讲解

▶ 点击查看讲解视频

月赛日期

解题思路:

我们想要凑出 202507 那么只需要两个 0，两个 2， 一个 5， 一个 7 即可，所以只需要在遍历的同时使用桶记录每个数出现的次数即可

硬币购物

解题思路:

1. 问题转化：
   对于每种硬币，其能贡献的最大金额为 $C_i = A_i \times B_i$（即使用全部硬币）。问题转化为：从 $N$ 种硬币中选择最少的种类，使得这些种类的总金额之和 $\geq X$。

2. 贪心策略：

   • 将每种硬币的总金额 $C_i$ 按降序排序。
   • 从大到小累加 $C_i$，直到累加和 $\geq X$。
   • 累加过程中计数的种类数即为答案。
   • 若所有种类累加后仍 $< X$，则输出 $-1$.

3. 正确性证明：
   由于每次选择当前剩余硬币中总金额最大的一种，可以最快达到 $X$ 元。这样能保证使用的种类数最小，因为大额种类能更快接近目标。

无限序列

解题思路:

1. 规律发现：

   通过分析序列生成规则，发现序列由两个等差数列交织而成：

   • 奇数项（下标 $2n-1$）：$0, B, 2B, 3B, \ldots$，通项公式为 $(n-1) \times B$

   • 偶数项（下标 $2n$）：$A, A+B, A+2B, A+3B, \ldots$，通项公式为 $A + (n-1) \times B$

2. 问题转化：

   找到一个最小的数字$x$，使得序列中小于等于$x$的至少有$K$个，而$x$显然是有单调性的，$x$越大，序列中小于等于$x$的数字就越多，所以本题可以二分答案。

3. 计算小于等于 $x$ 的元素个数:

   • 奇数项个数：$\lfloor \frac{x}{B} \rfloor + 1$
     • 包含 $0, B, 2B, \ldots$ 直到不超过 $x$ 的所有项
   • 偶数项个数：当 $x \geq A$ 时为 $\lfloor \frac{x-A}{B} \rfloor + 1$，否则为 $0$
     • 包含 $A, A+B, A+2B, \ldots$ 直到不超过 $x$ 的所有项
   • 总个数：上述两部分之和

美丽的矩阵

解题思路: 我们可以观察得出，行列之间的操作不会互相影响，所以可以对行列分别操作。 同时我们可以发现，对于每一个相邻行列之间，若要进行操作，那么一定要保证操作之后不存在 $h_{i - 1, j} = h_{i, j}$ 的情况。 所以当我们发现可以操作时，可以此作为凭证进行 $dp$。 令 $x = 0 or 1， y = 0 or 1 (0 不操作，1 操作)$，代表四种操作情况，那么有 $dp_{i, x}$ 代表第 $i$ 行是否进行操作的最小代价。 $dp_{i, x} = min(dp_{i, x}, dp_{i - 1, y} + (x ? a_{i} : 0))$ 列的操作同理。 最终总代价即为行最小代价 + 列最小代价