2025年9月算法好题集锦

发布于 2025-09-01 | 标签: 好题集锦、算法 | 5分钟 | 1308字数

Codeforces：

*表示对 gym 中题目难度的估计。

题目链接	难度分	Tag	题解	学到的东西
CF1900D	2000	数论、容斥	---	学习去掉倍数的重复情况
CF141D	2300	DP、最短路	---	从要求的结果来看，这是一个求最短路的问题，但又可以用DP去做。真正操作起来，发现真用DP做起来转移比较麻烦（涉及到往回走），所以可以考虑直接建图跑最短路算法
CF164A	1700	两遍DFS	---	图论题容易想当然，在可能有环的图上执行一个算法时，需要多造一些包含环的样例，并模拟一些不同的DFS顺序
CF102861I	1800	树形DP、乘法逆元、前后缀分解	---	正确做法是前后缀分解去维护子树的乘积，如果用乘法逆元的话，可能会遇到dp值为0的问题。我们脑子里仍然要把乘法逆元认为是除法，这样就不会忘记0没有逆元这个事实
CF105862H	1800	期望、贡献法	---	首先要发现每个数的贡献次数是一样的，只需要算某一个数的贡献次数，然后在求贡献次数时，可以考虑枚举 step，看有多少个合法的 current，current 的数量其实就是形成的循环中的位置个数（关键转化），所以变成了求每次走 step 步形成的环有多大
CF2148F	1800	贪心、根号结论	官方题解	对于一个数 $n$ ，将其拆成若干个正整数相加的形式，则在一个拆分中至多能拆出 $O(\sqrt{n})$ 种不同的数。使用这个结论可以知道复杂度是对的
CF105387G	1800	DP、前缀和、取模易错点		题目中涉及到取模后做减法，所以最后计算出的结果有可能是负数，需要调整成正数后输出
CF104777N	1800	字典树		首先要能分析出来前缀异或和互不相同才可能有解，然后注意到由于已经互不相同了，所以不管怎么异或都是互不相同，所以选定一个数之后我们关键是验证其能不能让最大值恰好为 n - 1，这就需要 01 Trie 来做了
CF2149E	1600	双指针、前缀和思想		这题是个前缀和套娃题，首先我们应该知道，假如不限制长度的话，我们会用双指针求不超过 k 种数的区间数，进一步，限制长度的话，如果只是限制上限，那么这个事情也是简单的，进而我们发现可以用前缀和的思想把下限的情况也解决了；然后考虑恰好 k 种，其实就是不超过 k 种减去不超过 k - 1 种的区间数
CF1487E	2000	枚举，mex		有多个变量互相牵制且都需要枚举，需要考虑枚举哪个，才能让另外的可以少枚举或者预处理即可得到结果
CF100488I	1600	并查集、补图		首先发现这道题是说的当且仅当，也就是说不相邻的点必须有相同颜色，所以容易想到补图中同一个连通块里的点的颜色必须相同，然后用原图的边检查是否冲突即可
CF100488K	1800	反悔贪心		首先不难分析出来，前 $i$ 个里面至多拿 $\frac{i + 1}{2}$ 个，考虑前 $i$ 个里自己能拿多少钱的，要么发现自己能多拿一个，要么发现需要和之前某个最便宜的换，换总是不会违反拿的个数约束的
CF865D	2400	反悔贪心		反悔贪心问题中，我们想的贪心可以傻瓜得不行，因为关键在于怎么反悔，只要保证反悔之后是最优的就好了

AtCoder：

其他题目：

题目链接	难度	Tag	题解	学到的东西
洛谷P5676	绿	强连通分量	---	边界情况判错了，当本题的有趣度是自己的兴奋度的倍数时，可以循环做本题，而不是相等，如果判错了会丢掉 40 分！另外如果没有样例提示能单点成环也算的话，可能会直接得 0 分！
牛客周赛108F	2000分	位运算、SOSDP、超集枚举	---	一个新知识点，要求某个数所有超集的某个值，无需枚举其所有超集，只需要枚举比其多一个set位的集合即可
洛谷P4832	绿	带偏移量的DP、滚动数组	---	复习了一下这两个东西，有段时间没遇到了
牛客周赛109F	1800分	推式子、离散化、树状数组、离线	---	利用条件，发现要求的是 $y_i \le \min(x_i + k_1, -x_i + k_2)$ 的 $i$ 的个数，不难想到讨论两个东西在什么情况下最小，然后就可以把 $\min$ 去掉求解了

看到的有意思的东西：

赞赏

本文作者： WanderOvO
本文链接： https://BUAA-Wander.github.io/post/2025-09-good-problems/
版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

# 好题集锦 # 算法

2025年10月算法好题集锦上一篇

CSP-S知识点备忘录下一篇