2025年11月算法好题集锦

发布于 2025-11-01 | 5分钟 | 1318字数

Codeforces：

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

题目链接	难度分	Tag	题解	备注
CF101968B	1700	画图、排序、组合数学		首先需要意识到交出来的区域是一样的，算出这个区域。然后按照这个区域去把点分成四类，只能左上配右下或者右上配左下。
CF105973C	1700	数学、位运算、推式子、组合数		注意到 $C(n, i) = C(n, n - i)$ ，我们如果把待求式列出来的话，可以用这个消掉大部分项，剩下的项是好维护的。
CF106157F	2000	最短路	题解	首先要注意时限为 $3.5s$ ，以及 $n$ 不大。我们可以钦定从起点走到终点的最大值或者最小值中的某个，然后在符合这个约束的图上跑最大值的最小值的最短路。题解给出的是另一种从连通性的角度考虑的做法。
CF105934C	1600	贪心	题解	首先不难发现，目标数组是极大、极小、极大交替，所以其实只有两种情况，即奇数位置极大或者偶数位置极大，可以分别计算操作次数。计算时，假如枚举到当前的 $a[i]$ 应该是极大，但现在不是，我们应该改谁最好呢？由于枚举到了 $a[i]$ ，所以前 $i - 1$ 个肯定是已经合法了，接着我们发现 $a[i + 1]$ 应该是极小，所以 $a[i + 1]$ 越小越好，所以减小 $a[i + 1]$ 比增大 $a[i]$ 更能使得后边的符合题意（贪心）。所以，每遇到一个不符合题意的，就改它的下一个元素即可。
CF106159D	1700	KMP、哈希、差分、测试、教学		操作不会改变模意义下的差分数组，所以本质上是对差分数组做模式匹配。请注意，本题如果要随机数据对拍，如果随机的数组长度过长+值域过大，则大概率是输出 `0 0`，属于无效对拍。
CF2154D	1900	构造		首先要分析每次删的元素的性质，发现为了不暴毙，走奇数次时一定是删走偶数步才能到的点，走偶数步时删走奇数步到的点，这样能保证不会把自己给删了。此外，删除还不能导致自己被困在某个子树里，所以应该从叶子开始删。

其他题目：

题目链接	难度分	Tag	题解	备注
P4823	蓝	贪心、证明、DP、邻项交换法	题解	很不错的一道贪心确定决策顺序+DP求最优解的题。首先应该分析出来什么样的顺序是最优的，假设右两个人 $i$ 和 $j$ 目前高度都够出去，看谁先走能让后边的人够到的高度更高，这样分析即可。分析出顺序后，接下来只要按照这个顺序，看每个人走或者不走时，剩下的人梯的高度（只算肩膀）最高有多高就好了。
P2224	蓝	DP、状态设计	题解	有一个显然的 $dp[i][j][k][l]$ 的四维 DP，但是第 4 维是不必要的，可以合并到前 3 维。但合并到前 3 维之后其实是求前 i 个里面，第一个机器工作 j，第二个机器工作 k 是否可行，这是一个布尔数组的 DP，很浪费，我们可以把一个维变成 DP 的结果。具体来说，我们可以只管第一个机器的工作时间 j，然后状态记最小化第二个机器的工作时间。
P4158	蓝	背包、DP组合	题解	首先要读对题：问的是最多涂对的格子数，并且每个格子只能被涂 1 次，不能重复刷。基本思路就是求出每个木板被涂 `cnt` 次时至多涂对多少，然后每个木板相当于一组互斥物品，一共有 `n` 组物品做互斥背包就好了。对于内层问题，注意到涂色 `cnt` 次本质上就是涂色成了 `cnt` 段，所以只需要考察前 `i` 个格子涂成了 `j` 段的最大收益就好了。
P2279	蓝	树形DP、状态设计	题解	先把题目弱化为只能救火距离不超过 $1$ 的结点，分析明白之后就会做 $2$ 的情况了。本题的状态设计是循序渐进的，先是发现只考虑完全覆盖的情况不够，所以多引入了一个不完全覆盖的状态，然后进一步发现按照覆盖的层数去设计状态。并且本题的状态涉及到了子树内部对外部空间的影响。

看到的有意思的东西：

赞赏