2025年10月算法好题集锦

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}$ 这种极大的数很难直接用除法算排名，所以只能像上面那样搞排名。
CF105582C	1800	DP、二分、多重背包、优化教学		首先容易想到一个裸的 DP 去看凑出质量为 $m$ 的集合至多多少个，但是这个 DP 的状态不太能优化。考虑到答案有单调性，可以二分。二分之后，我们相当于限定了一个集合中每种零件至多用多少个，这样就成了裸的多重背包问题。
CF106125E	1600	随机、乱搞、骗分、教学	题解	练习一下乱搞。
CF106125F	2100	补图、二分图、DP、测试、教学		容易发现 $n$ 比较小的时候才有解，这个时候图非常稠密，接近一个完全图。考虑两个点是否在一个集合是困难的，但是两个点不在同一个集合这个事情似乎是容易做的。考虑补图，补图上的边代表互斥关系，则补图是二分图时必有点没法放到任何一个集合里。另外由于要求两个集合一样大，所以需要 DP 求具体方案。本题可以本地写 spj 测试，数据生成的时候建议生成点数少且边数多的图，或从完全图上删少量的边，纯随机数据测会不可以总司令。
CF703D	2100	离线、树状数组		首先区间异或和是可以前缀异或和求出来的，然后区间中出现偶数次的数是不贡献到区间异或和里的，进而发现区间异或和就是区间中出现奇数次的数的异或和（无需去重）。区间中所有数字去重的异或和，再异或上出现奇数次的数的异或和，就是偶数次的数去重的异或和了。所有数去重的异或和可以类比区间中不同数的个数的做法（HH 的项链）去维护。
CF2001D	1900	线段树、单调栈、树状数组、双指针、测试、教学	题解	本题如果使用一种错误的单调队列写法，本地对拍测试时有可能需要 1 分钟左右才能拍出 bug，这个错误做法提交后也能通过多测的 4 组测试点，算是比较隐蔽的 bug 了。使用线段树实现查询是正确的，但是比较长。小清新做法是使用单调栈，灵神最喜欢的数据结构。
CF104901K	2100	树状数组、中位数贪心、双指针、二分		一段数组每个比上一个大 1，则每个数减掉自己的下标之后应该相等，这是个比较经典的套路。我们相当于想让一段 $a[i] - i$ 相等，这个使用绝对值不等式可知最小操作次数就是改成中位数。求中位数可以树状数组二分去做。如何计算代价呢？只要分别维护比中位数小的数的和，以及更大的数的和就好了。如果外边套二分答案则是双 log，过不去，需要把二分答案改成双指针。
CF106054B	2000	组合数学、隔板法		根据 $b$ 数组，可以求出 $a$ 中相隔 $k$ 项的两个数之间的差的关系，只要确定了前 $k$ 个数，后边的就都确定了，关键是根据这个关系算出来前 $k$ 个数的下界，然后就是隔板法计算了。
CF134B	1900	辗转相除法、数论、教学		考辗转相除法求 gcd 的过程的题目。反着来看，看 $(n, x)$ 如何变成 $(1, 1)$ ，题目所给的这个过程就类似于求 gcd 的过程，能变成 $(1, 1)$ 说明两个数得互素，在求 gcd 的过程中顺便统计一下操作次数就好了。
CF104785K	1700	图论、脑筋急转弯		选一些边，则选择的边构成的集合和剩下的边构成的集合，至少有一个的大小是 $\frac{m}{2}$ ，所以我们可以想办法将边分成这两类，每类内部都无环，则总有一个是符合题意的。
CF2129B	1600	逆序对		首先要知道 $2n - p[i] \ge n$ 。倘若我们按 $p[i]$ 从小到大的顺序去考虑变还是不变，如果不变，则其他所有还没填的 $p[j]$ 变或者不变都一定比 $p[i]$ 大，所以只要考虑左边还没填的贡献答案就好；如果变了，则其他所有还没填的 $p[j]$ 不管变还是不变，都一定比 $2n - p[i]$ 小，所以只要考虑右边的就好了。这样相当于考虑 $p[i]$ 和还没填的数构成的逆序数，把逆序数记到先填的数头上，就不重不漏了，且可以独立考虑，就容易做了。
CF106144F	1600	博弈、测试		根据博弈论最基本的判断先手必胜还是必败的原理，我们可以写一个 DP。这个题数据范围比较大，DP 只能做一小部分，但是能辅助我们检查猜测的结论是否正确，对拍一下就知道了。

其他题目：

题目链接	难度分	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$ 排序，以及如果没有证明出来，有什么骗分的办法，以及如何检测（对拍）。
P8817	蓝	BFS、暴力、测试		本题对拍时测出来设置的无穷大不够大，因为 $k$ 有可能超过 $n$ ，当 $n$ 很小但 $k$ 比较大时，设置最短路为 $n + 1$ 就会有问题。另外本题在做的时候中间一次关键的代码修改导致复杂度变成了 $O(n^3)$ ，需要进一步优化才能通过本题。

看到的有意思的东西：

2025年10月算法好题集锦

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