2025年12月算法好题集锦

Codeforces：

gym 中题目难度分是我根据体感估计的。

题目链接	难度分	Tag	备注
GYM105863F	1700	数学、取模、二分	一个数 $x$ 对 $m$ 取模后变小，结果应该至多是 $x$ 的一半，所以真正有用的取模次数是对数级别的。
GYM105863G	1800	数学、数列求和、贡献法	我们考虑第 $i$ 个位置填 $j$ ，且满足 $\min(a_1, ...a_i) = j$ 贡献了多少次，可以发现就是前 $i - 1$ 个必须填不小于 $j$ ，后 $n - i$ 个随便填，第 $i$ 个等于 $j$ 的方案数。对这个东西进行求和，发现只要先枚举 $j$ 再枚举 $i$ 就可以等比数列求和求解了。
CF1912K	1800	状态机DP	满足条件的子序列连续 3 个数中必须有偶数个奇数。我们考虑以第 $i$ 个数结尾的满足条件的子序列个数，则可以枚举上一个结尾 $j$ ，看如何贡献。经过分析，发现我们其实只关心最后 3 个数的奇偶性，将这个信息设计到状态中即可。另外，上面少考虑了从只有 2 个数的序列转移过来的情况，所以还要补充上这种。总的来说需要维护结尾为 1，2，3 的子序列的末尾奇偶性信息。
GYM106260A	1700	期望	有很多切入点，但是能做的切入点是，我们考虑每个点 $u$ 贡献的操作次数的期望。 $u$ 有贡献当且仅当序列中 $u$ 前面没出现自己的祖先。假设 $u$ 的深度是 $d_u$ ，则随机出一个满足上述条件的排列的概率是 $\frac{1}{d_u}$ ，原因是我们只需要考虑从 $1$ 到 $u$ 这条链上的点，每个点排在第一位的概率都是 $\frac{1}{d_u}$ 。其他点怎么排是无所谓的，相当于可以分子分母约掉，所以只要把这些倒数求和就是答案了。
CF105874E	1900	线段树、离线、素数、莫队	大号版的 HH 的项链，我们对询问离线，按照右端点排序，维护每个素因子最后一次出现的位置，并用线段树维护位置上的素数的区间乘积即可解决本题。如果数据范围再小一点，则可以用莫队做，因为端点移动时更新信息是容易的。
GYM105845F	1800	DP、数学、测试	状态容易设，关键是如何高效转移。我们注意到能转移过来的一定是前缀和模 $j$ 同余的，所以不妨开一个二维数组，专门维护模 $j$ 余 $k$ 的那些 $dp$ 值的和，这样就可以 $O(1)$ 转移了。注意，本题空间比较小，无脑开 long long 且不压空间会 MLE，但如果你使用的是 vector 而不是静态数组，则还能侥幸过几个点。
GYM105789K	2000	模拟、贪心、分类讨论、测试、教学	首先应该发现，如果每轮的 $p$ 严格变大的话，至多模拟根号轮就可以，如果不变的话直接计算就可以。对于严格变大的情况，显然是先加后乘能最大化一轮的输出，但最后一轮需要特殊处理。本质上，最后一轮也是用最大的几个加法和最大的几个乘法先强化，然后再攻击。本题 corner case 非常多，比如啥时候无解、会不会爆 long long、最后一轮的处理...如果是正式比赛的话通过率应该惨不忍睹。
GYM105790K	1600	数论、数学	$a^b$ 模 $mod$ ，但 $b$ 是个很大的斐波那契数，怎么办？注意到 $a^{m - 1} \equiv 1 (mod\ m)$ ，所以可以在计算 $b$ 时对 $m - 1$ 取模，用这个取模后的结果 $r$ 求 $a^r$ 。
CF1428E	2200	动态贪心	考虑到代价函数是下凸的，所以假如把某个胡萝卜拆成 $cnt$ 段，那么一定是尽量平分才能让这个胡萝卜的总代价最小。进一步，我们还应该发现，切成 $cnt$ 段肯定比切成 $cnt + 1$ 段代价大，并且，这个代价之差是逐渐变小的。因此，我们可以动态的贪心，维护每个胡萝卜当前段数与再切一段后的代价之差，每次贪心地选最大的那个切就好了。
GYM106270H	1800	数论、反悔贪心	每个数有两种变换方式，各自的代价可以算出来。然后发现这个就类似 CSP-S 的 T1 了，我们可以先大家都无脑选最优，然后按照两种方式的差值排序反悔即可。记得预处理每个数的最小素因数。
GYM105262G	1700	前缀和、哈希、马拉车	用哈希或马拉车求回文半径，然后用加权前缀和算结果就行。注意别推错了式子，哈希要用双哈希（1e12 个区间）。
CF2018B	1900	贪心、区间合并	首先应该注意到，不管选谁为起点，我们每次都是覆盖连续的一段区间。走 k 步则区间长度为 k，并且要把所有 ddl 不超过 k 的都包含进来，所以我们可以预处理所有 ddl 不超过 k 的点的最小左端点和最大右端点。假设不超过 k 的点的范围是 l 到 r，则合法起始点的左端点至多可以是 r - k + 1，右端点至多可以到 l + k - 1。把这些合法起始点的区间交一下就是答案了。如果读错题看成了树上问题，可以出一道固定起始点，判断是否可行的问题，用贪心+倍增搞。

其他题目：

题目链接	难度	Tag	题解	备注
P9753	蓝	括号序列、栈、哈希、DP、测试		首先应该知道可以用类似括号序列栈模拟的方式判断一个子串是否合法。然后，应该意识到，可以枚举开头，然后从这个开头开始用栈模拟，每当栈为空时，说明以这个字符开头的合法子串数量又 + 1 了。进一步，应该意识到，每当遇到一次之前出现过的栈的状态，就说明末端又消掉了一个子串，而这个状态出现的次数就是以当前字符结尾的合法子串个数。另外还有一个 DP 做法。关于测试，随机的字符集太大的话就会和 A 性质差不多了，基本都是相邻的或者没有，所以字符集要小一点去对拍。
ABC312F	绿	贪心、排序		本题有若干种做法，但出发点是一样的，都是先枚举某种物品的个数，然后想办法快速算出其他两种的个数，并且选的时候优先选值更大的。我的做法是枚举有几个需要开罐器的罐头，这样可以直接算出需要拿几个开罐器，这样不需要开罐器的罐头个数也就呼之欲出了。题解区还提供了枚举其他物品的做法。
ABC438F	蓝	贡献法、MEX、分类讨论、LCA	我的题解	把树弱化成子数组，是一个比较好的贡献法题目。之后再考虑树的拓扑上怎么做这个事情。

2025年12月算法好题集锦

感谢您的支持，我会继续努力的!