2025年11月算法好题集锦

发布于 2025-11-01 | 10分钟 | 2621字数

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	构造		首先要分析每次删的元素的性质，发现为了不暴毙，走奇数次时一定是删走偶数步才能到的点，走偶数步时删走奇数步到的点，这样能保证不会把自己给删了。此外，删除还不能导致自己被困在某个子树里，所以应该从叶子开始删。
CF106177F	1800	前缀和、哈希表、两数之和		两数之和复杂版。首先应该把 $f$ 运算分析好，然后再分析题目中的那个式子何时成立，我们先对这个式子按照奇数个数到底是奇数个还是偶数个进行讨论并展开，分析之后发现数组长度 $m$ 应该满足 $m = 4k+1$ 的形式，并且发现题目其实就是想让这种长度的数组里奇数和偶数的个数刚好差 $1$ 。我们标记奇数为 $1$ ，偶数为 $-1$ ，则区间和为 $1$ 或者 $-1$ 是符合题意的。我们根据下标模 $4$ 的结果，维护 $4$ 个哈希表用来维护前缀和出现的次数，就可以做了。
CF104671F	1700	位运算		我们发现 $k$ 是预先给出来的，并且只关心与和是否等于 $k$ ，所以我们其实只会选那些 $a[i] \and k=k$ 的数，并且最好是把区间里的这种数全都选了最有希望。其他数可以设为二进制全 $1$ ，表示选了也没用。这样就是做区间 $and$ 的查询就好了。
CF106188C	1700	DP、正难则反、教学		显然是需要用 DP 计数。我们关心的是最长的边是谁，然后需要看 $k - 1$ 条更短的边有多少种加起来严格大于最长边的方案。这样做的话，边长之和至多要开到 $1e6$ ，再加上前两维就炸了。但是单条边长度只有 $1e4$ ，所以我们其实可以计数加起来小于等于最长边的方案，相当于计数不行的，最后从所有方案 $C(n, k)$ 中减掉就行了。
CF106189J	1700	区间DP、DP方案		首先要意识到，假如我们已经钦定删掉了某些元素，则剩下的元素的配对有点类似于剥洋葱或括号匹配，加上数据范围不大，所以启发我们使用区间DP。由于要记录方案，所以可以每个 $dp[i][j]$ 额外记录 $from[i][j]$ ，其中 $from[i][j]$ 是 DP 区间划分的中间点，最后使用一个 DFS 去把方案求出来即可。
CF1996G	2200	线段树、异或哈希		如果任意断掉一条边，原图就变成了树，仍然是联通的，此时任意两点的路径唯一。因此，可以考虑枚举先断掉哪条边，然后计算此时要建多少条边。我们破环为链，枚举连续的 n 个点，就是相当于在枚举断开的边。对于每个约束，会经历从 $(a,b)$ 到 $(b,a+n)$ 最后到 $(a+n,b+n)$ 这三个阶段，我们使用线段树维护这个区间加，然后查询区间中未被覆盖的个数就好了，类似扫描线。线段树里维护 min 以及 min 的个数就可以维护这个信息。
CF105698G	1800	线段树、二分、mex		首先，我们应该知道，假如没有操作的左端点是 i，则查询 i 位置结果一定是 1。进一步，我们发现其实查询 i 的结果时，就是看从 i 开始往左看，看是否存在一个操作，左端点是我们正在枚举的位置，且右端点大于等于 i。其实，对于相同的 l，我们关心的是最大的 r，所以我们需要维护左端点为 l 时最大的 r。这样的话，我们相当于看每个位置最大的 l 是否大于等于 i，进一步，其实就是看一段区间里最大 r 的最小值是否大于等于 i。
CF104936E	1800	字典树、双指针、前缀和		首先应该想到，求恰好等于 k 的个数有点麻烦，但是求小于等于 k 的个数是简单的，所以可以先用前缀和转化一下。接下来，我们考虑计数右端点为 $r$ 时，有多少左端点是符合题意的。注意到右端点固定时，左端点越小，区间里的最小异或对就越小，所以符合题意的左端点一定是一个前缀。我们在考虑右端点 $r$ 时，右端点为 $r - 1$ 时的左端点已经算出来了，这个左端点只可能向右移动，至于移动多少，取决于 $a[r]$ 和哪个数异或之后 $\le k$ ，所以只要区间里能有和 $a[r]$ 异或后 $\le k$ 的数，左端点就可以右移。使用字典树求区间的最小异或值即可。

其他题目：

题目链接	难度分	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$ 的情况了。本题的状态设计是循序渐进的，先是发现只考虑完全覆盖的情况不够，所以多引入了一个不完全覆盖的状态，然后进一步发现按照覆盖的层数去设计状态。并且本题的状态涉及到了子树内部对外部空间的影响。
P1930	蓝	分层图最短路、BFS、	题解	每个格子，要么是被单独走到的，要么是被国王骑士绑定走到的，这两种走到存在区别，所以可以拆成两个点。层内都是长度为 1 的边，层间是国王走到这个点的距离作为边权。

看到的有意思的东西：

赞赏