洛谷刷题指南：题单选择、动态规划刷法与故障排查

在洛谷刷题这件事，我一直觉得“题单”是被严重低估的功能。很多人进了洛谷，第一件事是从“题库”里随机挑题，或者照着某个大佬的提交记录一路点下去，刷到哪算哪，结果刷了两三个月，感觉什么都会一点，又什么都拿不出手。题单的存在，本质上就是帮你把“不知道下一步该做哪道题”这个问题解决掉。这篇东西不讲虚的，我会从题单的选法、刷法、复盘方法，到具体题目的拆解、常见故障排查，把我在洛谷刷题这些年踩过的坑和总结出来的方法一次讲清楚。适合准备参加 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是 1，1 * 60是 60，直接少了 30 个人。这就直接导致输出的分数线偏高。这种 bug 在样例或者小数据上未必能暴露，因为当人数很少时，前几名和正确排名可能分数一样；但到后面的测试点就会连续 WA。所以有人问“为什么只拿了 80 分”，我第一反应就是让他看整数除法顺序。

另一个坑是，如果你不用计数数组而用优先队列（堆），要特别注意堆的大小变化。每轮插入 x 后，堆里可能有多于 k 个元素，你要把最小值不断弹出，直到堆大小等于 k。很多人没想清楚这个维护过程，导致输出的是堆顶最小值而不是第 k 高，结果 WA 得莫名其妙。这种结构选型的问题，恰恰是题单训练的价值所在：你在题单里见过类似题，下次就会先判断“分数范围小用桶，数据量大用小顶堆”，而不是凭感觉硬写。

5. 80分、超时、对拍：洛谷刷题高频故障排查实录

刷题单刷到中后期，你一定会遇到一种情况：自己感觉思路完全正确，提交上去却只有 80 分，甚至更低。然后打开评测详情，看到一堆 WA 或者 TLE 的测试点，直接懵了。这一节我把最常见的故障原因和排查手段完整整理出来，都是我实际踩过、实际帮别人排查过的。

5.1 “为什么我只拿 80 分？”的五个典型原因

第一个原因是边界条件没处理好。比如数组下标从 1 开始还是从 0 开始，循环里是否越界，dp 数组的初值是否覆盖了合法状态。很多题目的极端数据恰恰是 n=1 或 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

对拍有几个细节要注意。第一，随机数据生成器要能生成边界数据，比如 n=1、n=最大值、所有数相同，这些恰好是 bug 最常出现的地方；第二，暴力程序一定要保证正确，宁可写得慢，也不要写成另一个有同样 bug 的“暴力”；第三，每次对拍失败后，保留那个 input.txt，它就是你调试的救命稻草。我个人的习惯是，所有 WA 超过三次的题，直接进入对拍流程，不要干瞪眼瞎猜。

5.3 洛谷评测状态的含义与应对策略

洛谷的评测状态，很多新手看得一头雾水，这里给个速查表：

这几种状态里，最值得专门说的是 RE。很多 RE 其实是数组开小了，洛谷会给你一个 Stack overflow 或者 Segmentation fault 的反馈。我见过一个同学做树剖题，链式前向星边数组只开了 n 个，结果存反边的时候越界，拖延了一天没排查出来。遇到 RE 先去把数组大小乘个 2 甚至乘 4 再说。

刷题单这几年，我的真实体会

说句实在话，题单本身不神奇，它只是把信息组织好了，真正的功夫在于你怎么用它。我刷完一份动态规划题单之后，不是立刻开下一份，而是把里面标记为 B 和 C 的题目又刷了一遍，才敢说自己入门了。后来带别人刷题，我也一直强调这个做法，但真正照做的人不多。最后再分享一个小技巧：洛谷用户自建的题单往往比官方题单更“新鲜”，会收录一些新出的比赛题，甚至 B 开头的基础题，很适合在官方题单刷累的时候换换脑子。你要是能找到一份按难度、按知识点双重标注的题单，那就是宝，刷一份顶三份。希望这篇东西能帮你在洛谷题单这条路上少走一点弯路。