在洛谷刷题这件事我一直觉得“题单”是被严重低估的功能。很多人进了洛谷第一件事是从“题库”里随机挑题或者照着某个大佬的提交记录一路点下去刷到哪算哪结果刷了两三个月感觉什么都会一点又什么都拿不出手。题单的存在本质上就是帮你把“不知道下一步该做哪道题”这个问题解决掉。这篇东西不讲虚的我会从题单的选法、刷法、复盘方法到具体题目的拆解、常见故障排查把我在洛谷刷题这些年踩过的坑和总结出来的方法一次讲清楚。适合准备参加 CSP/NOIP 的中学生、刚入门算法的大学生以及所有想系统刷题却不知道从哪下手的人。题单不是“题目列表”它是一套经过设计的学习路径。官方题单也好用户自己整理的题单也好背后都有一个共同逻辑把知识点按依赖关系排好把题目按难度梯度排好让你在每一个阶段只面对一个主要矛盾。这篇文章我会以动态规划题单为主线结合几个具体题目编号把“拿到一道题怎么想、想不出来怎么办、过了样例为什么还 WA、只拿 80 分怎么排查”这一整条链路讲透。1. 题单是什么以及为什么它比“乱刷题”更值得投入很多人的第一个问题是洛谷题库里几千道题我为什么要跟题单走这个问题我当年也问过后来想明白了一个道理刷题这件事难点从来不是“题量不够”而是“反馈不闭环”。散着刷题你每做完一道题学到的东西是孤立的你不知道这道题属于哪个知识族也不知道它前面应该有什么铺垫、后面应该接什么题目。题单解决的就是这件事——它把知识组织和题目之间的关系显式化让你在刷题的过程中反复看到同一个知识点的不同变体。1.1 题单不是“题目列表”是“按依赖关系排好的学习路径”我在带新人刷题的时候常用一个比喻散着刷题就像在迷宫里走路每一道题是一扇门你永远不知道自己打开下一扇门会到哪跟着题单刷就像手里拿了一张迷宫的地图你知道自己现在在哪个区域下一段路应该通向哪里。洛谷的官方题单会把“普及组入门”“提高组专题”“省选与 NOI”分得很清楚每个大专题下面又按难度分成若干道题从签到题到压轴题循序渐进。比如动态规划这一个大项官方题单不会一开始就让你做斜率优化而是先让你用线性 DP 练手再到背包问题、区间 DP、树形 DP、状态压缩最后才碰优化类技巧。这背后的逻辑是DP 的核心能力是“状态设计”而状态设计需要大量低难度题目来培养直觉。如果你一上来就做省选题很容易被复杂状态直接劝退从简单题起步你能在“每次只增加一个新变量”的节奏里慢慢理解“为什么状态要这样设”。1.2 选对题单比刷完题单更重要洛谷上的题单很多用户自己建的题单质量参差不齐。我的建议是优先看三个来源第一是洛谷官方题单它是按比赛大纲整理的覆盖面最全第二是“题单广场”里点赞数高、且最近有人更新维护的题单第三是你在网上搜到的名校集训队公开题单这些通常有详细的难度标注和知识点标签。选好题单之后最好再花十分钟看一下题单里的题目列表感受一下梯度是否平滑。如果前几道题你是秒杀的中间题目做起来有点卡最后几道题要花很久那这就算一个合格的题单。2. 刷题单之前先想清楚这三件事目标、周期、复盘机制我见过太多人把题单当成“任务清单”每天刷三题打个卡刷完一遍发现自己还是不会做题。问题出在哪出在他们没有为目标做设计。刷题单不是一个“量”的问题而是一个“质”的问题。在按下“开始刷题”按钮之前我建议你先花半天时间想清楚三件事。2.1 定目标你这一轮刷题单要解决什么问题先问自己你刷这个题单是为了准备某一场具体的比赛还是为了补某个薄弱知识点还是单纯想保持手感目标不同刷法完全不同。如果是备赛你的目标应该是对着比赛大纲逐点排查题单里没覆盖的知识点要自己补充如果是补薄弱项那应该“只刷薄弱点相关的题”而不是从头到尾每个题都做如果是保持手感那重点是每天固定时间刷固定数量的题保持思维的连续性。我自己的习惯是每个刷题阶段开始前会在笔记本上写一句话“这一个月我要通过以下题目练会区间 DP 的环形处理。”这个目标越具体越好。等到阶段结束你回头能清楚地回答“我有没有达成目标”而不是“我刷了三十道题”。2.2 定周期不要追求“一个月刷完”要追求“每道题都消化”很多人犯的错误是把题单当成“网课进度条”恨不得一周肝完。这完全没有必要。一个知识点的吸收是需要间隔的。你今天做一道 DP 题卡壳两小时看了题解觉得自己懂了——但三天后让你重新做一遍你还能做出来吗大多数人的答案是“不能”。所以我的建议是一个专题题单按两周到一个月来规划是比较合理的节奏每天投入一到两小时做一道题或者隔天做一道题留出足够的时间给“二次刷题”——也就是把之前卡壳的题重新做一遍。2.3 定复盘机制题单刷完不复盘等于白刷复盘这个词被说烂了但在刷题这件事上复盘的具体做法其实很明确给每道题做一个标记A 表示完全独立做出来B 表示看了一点提示后做出来C 表示看了题解才做出来。然后每周把 C 类题重新做一遍直到它变成 A 类为止。这不是多此一举心理学上的“提取练习”效应告诉我们你越是费力地回忆一个解法你对它的记忆就越牢固。你重做一遍 C 类题花的二十分钟比新刷一道题的价值高得多。3. 按知识点拆解动态规划题单的核心环节到底该怎么啃动态规划是洛谷题单里最庞大的一个专题也是让最多人卡壳的专题。很多人一看到“DP”两个字就头疼其实 DP 题是有套路的套路就四步状态设计、转移方程、边界条件、复杂度估算。下面我按这个顺序结合题单里的常见题目来拆解。3.1 状态设计先回答“我需要知道什么信息”拿到一道 DP 题先别急着写代码问自己一个问题如果我只知道一个量这个量应该是什么才能唯一确定后续的最优选择这个量就是状态。拿动态规划题单里经典的背包类问题来说你在考虑第 i 个物品装不装的时候你只需要知道当前背包剩余容量就能决定装不装所以状态是“前 i 个物品、容量为 j 时的最大价值”。而到了区间 DP比如石子合并你切割一堆石头的时候你需要知道“这一段区间合并的最小代价”因为你切割的左右两侧是独立的子区间所以状态是“区间 [i, j]”。题单里有些题比如 P3193 这种偏推导风格的题状态设计往往是整道题最核心的难点。这种题不会直接告诉你“我们有 N 个物品放进容量为 V 的背包”而是把模型藏在一个场景故事里你要做的工作就是把场景翻译成状态。我的习惯是先把题目里的所有变量列出来然后逐个问自己“这个变量会不会影响最优决策”影响的变量很可能就要进状态。3.2 转移方程和边界条件从哪里来到哪里去状态设计好了转移方程其实是在回答“当前状态可以由哪些更小的状态推导出来”。这个“更小”可以是序列下标更小、背包容量更小、区间长度更短或者集合元素更少。比如背包问题的“选或不选”两种决策就是两个来源区间 DP 的“枚举分割点”就是 k 个来源。边界条件则要特别注意很多题目的 WA 都出在边界。一个常见的错误是初始化 dp[0] 0但没考虑 dp[0] 在后续转移中出现负数下标的情况另一个常见错误是用 memset 把整个 dp 数组初始化成 0x3f但有些状态本来就是合法的 0结果被覆盖成了无穷大导致转移结果不对。边界条件的检查方法是把题目的最小数据手算一遍看你的状态和方程是否与手算结果一致这个过程看起来很笨但对 DP 题来说是最有效的检验方式。3.3 复杂度估算你的 O(n³) 在大数据下会怎么样状态设计和转移方程写出来之后一定要做复杂度估算。算法题的数据范围决定了你要去哪一层复杂度n ≤ 20 可以考虑状态压缩枚举n ≤ 100 基本可以接受 O(n³)n ≤ 1000 要控制在 O(n²)n ≤ 1e5 就要往 O(n log n) 甚至 O(n) 想。这一步想得越早越不会白写代码。洛谷评测是会反馈每个测试点的情况的而且分数是逐测试点累加的。如果你的程序在小数据上能过、大数据上超时你会看到一部分测试点 TLE一部分 AC最后拿一个中间分数——这就是网上很多人问“为什么我只拿 XX 分”最常见的原因。4. 核心实操以“实时中位数”类型题为例看一道题怎么由读题到 AC上面讲的是方法论下面我用一个具体的题来串一遍完整流程。这类题在洛谷题单里反复出现比如不少人问过的 P7072。这个题属于“边插入边查询排名”的经典模型非常适合用来展示如何从题意里提炼出数据结构需求如何选择适当的实现方式以及如何在边界条件上翻车。4.1 题意与切入角度这道题的大意是随着比赛进行不断有选手成绩出来你要实时计算当前已经出成绩的选手中排名第 k 高的分数是多少其中 k 由当前人数和百分比 w 计算而来。如果你去暴力做每来一个成绩就把当前成绩数组重新排序再取第 k 个复杂度是 O(n² log n)在 n 比较大的时候直接 TLE。这道题需要换一个思路。你仔细看成绩的取值范围它是固定且有限的一般不会超过 600 分。这个范围小到我们可以用一个计数数组来“模拟有序结构”。当一个新的成绩 x 进来我们只需要让 cnt[x]要查第 k 高的分数就从分数上限往下累加 cnt直到累加人数达到 k。这样每次插入和查询都是 O(600) 级别的常数时间总复杂度 O(600n)。如果有人问为什么不用堆其实堆也能做维护一个小顶堆但每轮要删掉多余的低分节点逻辑稍微绕一点而计数数组在这个题目上是更直接的“降维打击”。4.2 核心实现下面这个实现思路可以直接套到类似“分数范围小 实时排名”的题目上#include bits/stdc.h using namespace std; int n, w, x; int cnt[605]; int main() { scanf(%d%d, n, w); for (int i 1; i n; i) { scanf(%d, x); cnt[x]; int k max(1, i * w / 100); // 获奖人数 int sum 0; for (int score 600; score 0; score--) { sum cnt[score]; if (sum k) { printf(%d , score); break; } } } return 0; }这个代码有三个关键点。第一获奖人数的计算公式max(1, i * w / 100)注意 i * w 要先乘再除如果先除后乘会损失精度导致人数偏小同时人数至少为 1这是题目明确约定的。第二分数上限是 600要从 600 往下扫到第一个“累积人数大于等于 k”的分数因为分数越高排名越靠前。第三cnt 数组不需要清空因为人数的累加本身就是持续的。4.3 这道题的坑点这个题看起来简单但实际提交时很多人翻车。踩得最多的坑就是公式写成了i / 100 * w当 i 小于 100 时这个表达式结果直接是 0然后取 max 之后变成 1好像没问题但当 i 稍大一些比如 i 150正确结果应该是 150 的 60% 即 90你写错了顺序可能得到 90 还是 90不一定——用整数除法150 / 100是 11 * 60是 60直接少了 30 个人。这就直接导致输出的分数线偏高。这种 bug 在样例或者小数据上未必能暴露因为当人数很少时前几名和正确排名可能分数一样但到后面的测试点就会连续 WA。所以有人问“为什么只拿了 80 分”我第一反应就是让他看整数除法顺序。另一个坑是如果你不用计数数组而用优先队列堆要特别注意堆的大小变化。每轮插入 x 后堆里可能有多于 k 个元素你要把最小值不断弹出直到堆大小等于 k。很多人没想清楚这个维护过程导致输出的是堆顶最小值而不是第 k 高结果 WA 得莫名其妙。这种结构选型的问题恰恰是题单训练的价值所在你在题单里见过类似题下次就会先判断“分数范围小用桶数据量大用小顶堆”而不是凭感觉硬写。5. 80分、超时、对拍洛谷刷题高频故障排查实录刷题单刷到中后期你一定会遇到一种情况自己感觉思路完全正确提交上去却只有 80 分甚至更低。然后打开评测详情看到一堆 WA 或者 TLE 的测试点直接懵了。这一节我把最常见的故障原因和排查手段完整整理出来都是我实际踩过、实际帮别人排查过的。5.1 “为什么我只拿 80 分”的五个典型原因第一个原因是边界条件没处理好。比如数组下标从 1 开始还是从 0 开始循环里是否越界dp 数组的初值是否覆盖了合法状态。很多题目的极端数据恰恰是 n1 或 n最大值你不会在样例里看到这些情况但评测数据里有。第二个原因是整数溢出。int 上限约 2.1e9如果你计算规模达到 1e9 以上中间变量可能溢出老老实实用 long long不要心疼那一点内存。第三个原因是浮点精度问题特别是几何题和概率 DP 题尽量全部使用整数运算或者 double 的 eps 判断避免严密相等比较。第四个原因是多组数据的初始化问题上一次数据的残留值污染了这一次的结果。第五个原因是最容易被忽视的算法复杂度不够优秀大数据点 TLE。关于“只拿 80 分”的排查步骤我建议按这个顺序先看评测详情里是哪些测试点挂了如果挂的是最后几个大数据点多半是 TLE去优化复杂度如果挂的是中间或前面的点多半是 WA去检查边界和初始化如果所有点都 A 了但总分不对检查是不是有多组数据忘记换行输出。这套流程能解决 90% 的“分数莫名其妙”问题。5.2 对拍用暴力程序验证正解的唯一可靠方法如果你改了很多遍还是不知道错在哪那就需要对拍。对拍是竞赛圈非常传统但极其有效的 debug 方法写一个保证正确的暴力程序复杂度无所谓数据小就行再写一个随机数据生成器把两个程序跑同一个数据的结果对比一旦结果不一致就说明你找到了让自己 WA 的数据。下面这个伪代码逻辑是所有对拍脚本的核心# 假设 sol 是你要测试的正解brute 是暴力程序gen 是数据生成器 while true; do ./gen input.txt ./sol input.txt sol.out ./brute input.txt brute.out if diff sol.out brute.out; then echo AC else echo WA break fi done对拍有几个细节要注意。第一随机数据生成器要能生成边界数据比如 n1、n最大值、所有数相同这些恰好是 bug 最常出现的地方第二暴力程序一定要保证正确宁可写得慢也不要写成另一个有同样 bug 的“暴力”第三每次对拍失败后保留那个 input.txt它就是你调试的救命稻草。我个人的习惯是所有 WA 超过三次的题直接进入对拍流程不要干瞪眼瞎猜。5.3 洛谷评测状态的含义与应对策略洛谷的评测状态很多新手看得一头雾水这里给个速查表状态含义常见应对策略ACAccepted全部数据通过可以进入下一题但复盘标记同样要做WAWrong Answer答案错误按 5.1 的顺序排查边界、类型、初始化TLETime Limit Exceeded超时优化复杂度或换算法 / 换数据结构MLEMemory Limit Exceeded内存超限压缩数组维度、改用滚动数组、减少无用的二维开太大RERuntime Error运行时错误检查数组越界、递归栈深度常见于深搜爆栈CECompile Error编译错误看编译信息多半是头文件或语法问题UKEUnknown Error未知错误偶发系统问题直接重测一次这几种状态里最值得专门说的是 RE。很多 RE 其实是数组开小了洛谷会给你一个 Stack overflow 或者 Segmentation fault 的反馈。我见过一个同学做树剖题链式前向星边数组只开了 n 个结果存反边的时候越界拖延了一天没排查出来。遇到 RE 先去把数组大小乘个 2 甚至乘 4 再说。刷题单这几年我的真实体会说句实在话题单本身不神奇它只是把信息组织好了真正的功夫在于你怎么用它。我刷完一份动态规划题单之后不是立刻开下一份而是把里面标记为 B 和 C 的题目又刷了一遍才敢说自己入门了。后来带别人刷题我也一直强调这个做法但真正照做的人不多。最后再分享一个小技巧洛谷用户自建的题单往往比官方题单更“新鲜”会收录一些新出的比赛题甚至 B 开头的基础题很适合在官方题单刷累的时候换换脑子。你要是能找到一份按难度、按知识点双重标注的题单那就是宝刷一份顶三份。希望这篇东西能帮你在洛谷题单这条路上少走一点弯路。