2025年10月算法好题集锦

发布于 2025-10-02 | 13分钟 | 3381字数

Codeforces：

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

题目链接	难度分	Tag	题解	学到的东西
CF1142B	2000	倍增、破环为链	---	这是在一个结构上倍增跳步的问题，需要预处理跳若干步之后跳到了哪里。另外本题可以离线做，也可以在线做
CF1848F	2400	倍增、打表		$a[i] = a[i]\ \oplus\ a[i + 1]$ 这个条件在很多题中会遇到，如果所有数一起做的话，做 $2^j$ 轮之后会变成 $a[i] = a[i]\ \oplus\ a[i + 2^j]$ 。这个规律可以通过打表找出来。
CF1515E	2200	DP、组合数学		需要敏锐地发现可以按照自动打开的灯分段，然后分别计算每段自己的方案数以及和前面的段组合的方案数，这两个方案数的计算都是组合数学的典型模型。
CF104679F	1700	位运算、构造		被我忽略的一个关键点在于，假如目前选的数异或出来是某个 `val`，则其和目标值 `target` 之间仅差一步就可以转化过去。异或的这个特点在其他题里也会遇到，经常用于前面若干个随便选，只用最后一个来调整结果。
CF104679E	1600	数论		又是一道数论与图论结合的题目，值得注意的点在于本题输入一个数输出一个数，并且有很显然的暴力做法，所以完全可以本地对拍过之后再提交。本题恰好在 $n$ 比较小的时候比较特殊，对拍能找到问题。
CF104822I	1900	数论		首先要把 $(a + b)$ 整除 $ab$ 转化为 $(a + b)$ 整除 $a^2$ ，这样转化的目的是有一边固定下来了。后边涉及到素因数分解之后反求出约数，这个只需要设一个约数集合 $S = \{1\}$ ，然后枚举素因数及其次数，和 $S$ 中已有的乘起来，每完成一个素因数的计算就把新得到的因数加到 $S$ 中。这样复杂度是不高的，因为约数个数本身也就小几百个，而我们每次计算必然会增加一个新的之前没得到的约数。
CF104328D	1800	数论、树形DP		本质上是求树的满足一定性质的直径，可以枚举直径的最高点，然后枚举直径中应该包含的素因子是谁，去做 DP 即可。这里需要注意一个数的素因子种类数并不多，常见的数据范围内也就 $10$ 个左右。还需要注意一个点就是快速素因数分解的复杂度是 $O(\log M)$ ，也是比较快的，因此这个题才可以这样做。
CF104380F	1600	构造、贪心、堆		首先要敏锐的观察到，往 deque 中插数据时，最后一个数要么在做最左边，要么在最右边，所以做不到无脑把最大的那些数放到想要的位置。然后会想到假如钦定不要某个后缀被选了，能否让剩下的前缀取到理论上的最大值，发现只要枚举后缀，然后看前缀往左还是往右放就好了。
CF105485I	1800	数论、线段树		当 $\gcd = 0$ 时，答案应该输出 $n$ ，这个点被我疏忽了，之后通过对拍和猜测这两种方式分别找到了 bug。
CF103855D	1800	分类讨论、贪心		最开始想了一个错误的贪心，但还好写之前就自己构造数据 hack 了自己。然后发现其实本质上就是拿 0 和 3 以及拿 1 和 2 这两类情况，只要分类讨论就好了，这时又想了一个错误的贪心（1 拿最大的），但也反应过来不对了，发现还是得枚举 1 到底拿谁。还是要多造数据去验证想法的正确性。
CF102409J	1600	枚举、贪心、证明		可以想到多种枚举方式。枚举第一个分割点后贪心正确性存疑，枚举第二个点后左右评分容易证明正确性。另外可以快速写一个对拍验证正确性。
CF102419D	1800	二分图判定、测试、教学		一道用于说明随机数据测试并非万能的好题！由于这道题目的特殊性，我们可以本地验证答案是否正确，就容易想到随机生成数据去测，测完再提交。但一方面，这个题多一个 `log` 是过不去的，本地小数据测不出来（TLE）；另一方面，本题的值域严格卡到了 `1 << 20`，如果只开 `1e6` 是过不了的（RE）。
CF691E	1900	矩阵快速幂、DP、教学		入门题，以后讲课可以扔到例题里。
CF1117D	2100	矩阵快速幂、DP、教学		更入门的矩阵快速幂。注意计算方案数的题目要同时看一下 DP 和组合数学方法，都去试一试。组合数学方法不好算时，说不定 DP 能快速幂优化解决。
CF104848M	1900+	柯西不等式、最短路、教学	题解	可以弱化成链上的问题，用来吸引学数学竞赛的人来搞 OI。
CF105408G	1500	数论、教学、测试		本题是一个很好的说明随机数据可能测不全的例子，因为想随机出两两 GCD 一样的数组，在 $n$ 稍微大一点或者值域稍微大一点时很困难。另外，本题在 YES 的情况时，时间复杂度会卡满，本地随机测试几乎测不到这种情况，这时需要先生成一个 gcd，然后选一堆素数和其相乘，就可以构造出一个 YES 的情况。实测某些看似能过的做法会在 YES 的时候 TLE 掉。
CF103886G	1800	分治、构造		按二进制位分治。如果把奇数放左边，偶数放右边，则不可能存在题中所说的跨左右两段的三元组，从而只需要分别考虑左右两边，递归下去，只要再按照更高的二进制位进行分类即可。
CF105335I	2000	康托展开、树状数组二分、教学	题解	首先要知道咋算一个排列的排名，然后需要把后边那个 $\frac{n!}{2}$ 合并到前面的项中，从而也转化成“每个数在后缀中排名多少”这个信息，只要有了这个信息，使用一个有序结构从左到右搞一搞就可以构造出排列了。注意， $\frac{n!}{2}$ 这种极大的数很难直接用除法算排名，所以只能像上面那样搞排名。

其他题目：

题目链接	难度分	Tag	题解	学到的东西
P12247	上位绿	扫描线、堆、DP	P12247	一道很综合的题目，首先要想到在时间轴上去 DP，写出朴素的转移方程，然后发现需要一个查询最大值的结构，且需要排除过期元素，用扫描线的思想+懒删除实现过期删除，也可以使用 `multiset` 直接实现随机删除和查询最大值，常数可能会大一点。
T673603	上位绿	逆序对、树状数组、贡献法	题解+std	邻项交换次数和逆序对关联很大，所以首先要想到这个事情。第二个事情，重排得到山脉数组可以看成是从小到大考虑所有数，每次塞到左边或者右边。第三个事情，由于交换次数就是求逆序对，所以我们考虑每个数字头上有多少次交换（即多少逆序数），为了不重不漏可以钦定把贡献记到小的数头上。
P7113	黄	拓扑排序、`__int128_t`		学一下怎么用 `__int128_t`，本题不用这个过不了（怪题），以及手写分数结构体及其操作。并且需要注意 `__int128_t` 需要模拟逐位输出，不要在关闭流同步时混用输出方式。
P2536	绿	DP		注意 DP 初始化，本题中所有的 `dp[i][0]` 和 `dp[0][j]` 都需要初始化。写 DP 时要检查每个值的前序值是否真的都算过/初始化过了。
P4768	紫	kruskal重构树、倍增、最短路、强制在线		学习了kruskal重构树的模板以及应用，并深深体会到了强制在线对题目难度的巨大影响。以及，多组数据一定要检查是不是清空了！这个题涉及到的数据很多，做的时候多测没有完全清空，使用 `memset` 二分清空才发现到底是哪个东西忘了清了。
T673604	蓝	分治、按位贪心、Trie	题解+std	题目给出了正着构造的规则，但要求倒退回去有多少可能的来源，这需要我们先分析正着构造的性质。
P4059	上位绿	DP、转化、初始化		首先这个题目要注意到连续空格的贡献是一次函数，倘若只是正比例函数那么相当于每个空格贡献是常数，一次函数的话只是第一次比较特殊，后边的贡献都一样。第二个要注意的点在于初始化，本题的初始化比较麻烦，需要分析好。
ABC180E	绿	状压DP、证明		本题值得学习的点在于证明每个点只需要走恰好一次，证明的关键是发现两点之间的距离函数满足三角形不等式，所以任何重复访问都是不优的。
P4926	蓝	差分约束		建模细节非常多的一个题。首先二分答案是显然的；然后需要把乘法约束取对数变成加法约束，才能转化成差分约束，这样会导致二分上界受到第一种承诺的约束；接着，初值点需要使用超级源点建立等式约束，没给初值的点也需要加入单向 0 边保证能遍历到，这样才能把所有约束都考虑进来。
T676142	绿	DP、组合数学、测试		赛时对拍都过了，思路也很流畅，最后挂了 30 分，原因是有个地方取模没取上，而对拍只拍了小数据，还是赖自己没有仔细检查溢出的情况（取模也是一种溢出），太可惜了。
P1939	绿	矩阵快速幂		其实是一个模板题，但是这里我才算是第一次知道咋写转移矩阵。我们注意到递推公式里包含 3 个数，于是我们考虑怎么从 $(a_{i - 3}, a_{i - 2}, a_{i - 1})$ 转移到 $(a_{i - 2}, a_{i - 1}, a_i)$ ，考虑给第一个列向量左乘一个矩阵得到第二个向量，那么根据待定系数法 + 对应项相等，就知道了这个转移矩阵的具体值。
P10499	蓝	高斯消元		主要是问题建模。我们考虑对于第 $i$ 个开关，主动按哪些开关时会让这个开关的状态也变化。这样的话，假如我们知道每个开关到底按没按，只需要把这两个东西做一个对应位置的与操作，再把与的结果异或起来（类似内积先乘后加），就是最终经过这些操作后到底改没改变这个开关的状态了。
T676143	蓝	ST表、括号序列、哈希、二分		积累了两个技巧：第一个是左右括号数量相等的括号序列仅通过循环移位就可以使之合法，第二个是比较一个字符串的两个子串的字典序，可以用哈希+二分求出这两个子串第一个不一样的位置，然后比较这个位置的字符，这样无需暴力比较了。
P9043	绿	复杂键哈希、双指针、分类讨论、推式子		一种和两种字符的情况有很多办法可以做，关键是如何解决三种字符的情况。三个相等其实可以转化成两对两个相等，例如 $cnt[r][a] - cnt[l][a] = cnt[r][b] - cnt[l][b]$ , $cnt[r][b] - cnt[l][b] = cnt[r][c] - cnt[l][c]$ ，变形成 $cnt[r][a] - cnt[r][b] = cnt[l][a] - cnt[l][b]$ ，然后发现可以维护 $(cnt[a] - cnt[b], cnt[b] - cnt[c])$ 的二元组的个数就好了，只要两个二元组相等，就说明这个串是可以的。
P8806	绿	DP、贪心、证明、骗分、教学		证明为什么按照 $w + v$ 排序，以及如果没有证明出来，有什么骗分的办法，以及如何检测（对拍）。

看到的有意思的东西：

赞赏