洛谷刷题全攻略：从红题到黑题的进阶路线与踩坑总结

洛谷刷题这件事，我认真持续了大半年。前前后后AC了两百多道题，TLE和WA的次数已经数不清，中间也经历过“打开题解就能看懂、关上题解就写不出来”的绝望期。这篇《洛谷刷题有感》，我想写的不是某个具体题目的题解，而是把这一段在洛谷刷题过程中反复踩过的坑、最终总结出的方法论、以及很多新人不会注意但特别影响体验的细节，一次性整理出来。

文章覆盖从入门到提高阶段最常见的题型，也包含C++、Java、Python三种语言在洛谷做题时的性能优化习惯。不管你是刚开始接触OJ刷题的初学者，还是刷力扣刷到想换换口味的老手，这篇文章应该都能给你一些参考。

1. 为什么是洛谷：题库、难度梯度与社区生态

先聊一个很多人问过的问题：同样是刷题网站，为什么最后留在洛谷？答案其实很简单——洛谷的题库分层做得太适合成长了。

1.1 红题到黑题：难度梯度本身就是路线图

洛谷题库用颜色标注难度，最低是红题，中间经过橙、黄、绿、蓝，最高到紫和黑。这种颜色分级的价值在于，它天然对应了一条算法学习路线：

• 红题对应“入门”，基本是语法题，用来熟悉输入输出和循环判断；
• 橙题是“普及-”，开始涉及枚举、简单模拟、基础贪心；
• 黄题到绿题是“普及/提高-”，字符串处理、搜索、简单动态规划都在这个区间；
• 蓝题到紫题是“提高+/省选-”，需要组合算法思维，比如图论加DP、数论加优化；
• 黑题通常是非顶级选手不要轻易碰的。

我见过不少新人一上来就找“黑题”“紫题”试水，结果看题解都看不懂，还打击自信。我自己的经验是：按颜色从红到绿循序渐进，每个梯度刷够二十道左右，再往下一层走。洛谷的题单功能就是干这个的，把某一种算法相关的题目串在一起，按难度排好，照着刷就行。

1.2 和力扣、Codeforces的定位差异

热词里出现“leecode必刷基础算法题”和“力扣刷题攻略”，说明很多人是先从力扣入门的。我不是说力扣不好，而是两者的侧重点完全不同。

我的建议是：如果目标是算法竞赛、考研机试、或者想真正搞懂算法原理，洛谷是更合适的主场。如果目标是马上找开发工作，力扣的高频题还是要刷，但可以等洛谷把底层能力打扎实之后再去，事半功倍。两边混着刷也行，但别指望用刷力扣的思路来刷洛谷——很多洛谷题的花样更多，想靠“背套路”过关很难。

1.3 洛谷的“隐藏功能”别浪费

很多人打开洛谷只用了题库和提交，其实还有几个被低估的地方。训练场和题单前面说了，另一个特别重要的是“题目讨论区”。每道题下方都有讨论帖，有人会把题目数据里的坑、特殊样例、注意事项直接标出来。提交以前先扫一眼置顶帖，能避免大量无意义WA。

社区里还藏着一些放松去处，比如洛谷小游戏。刷题刷到脑壳疼的时候，点开玩两把，输多赢少，反而激发了好胜心——继续回来刷题。这种体验挺真实的，也算一种心理调节手段。另外有人说用codebrick之类的第三方工具辅助刷题，我试用过，管理题目的思路不错，但洛谷自带的“个人练习”和“题单”已经够用，数据还不容易丢，我更推荐直接用站内功能。

2. 刷题方法论：从读题到AC的完整链路

刷题刷到后面你会发现，会不会写代码其实不是最难的，最难的是“知道该写什么”。我把一条完整的刷题链路分成四步，哪一步偷懒，后面都要还债。

2.1 数据范围决定算法边界，先算再动手

拿到题目先别着急敲键盘。读题的时候把输入的数据范围圈出来，这个动作能帮你筛掉一大半不合理的算法。

我的习惯是直接做粗估：n小于等于20，大概率可以用爆搜；n到1e5，复杂度基本得压在O(n log n)以内；n到1e9，那几乎只能走数学推导或者O(log n)的算法。看到1e5的数据范围还写O(n²)的循环，那TLE就是命中注定。

用P1048采药举例，这是一道经典的背包题。数据范围一出来，你就能判断这题要用动态规划而不是搜索。很多新手栽在这里，不是不会背包，而是根本没意识到“这题应该用背包”，这就是数据范围没看透的结果。

2.2 暴力先写对，再谈优化

我好几次陷入同一种困境：一上来就想着最优解，结果最优解没想出来，暴力也没写，白白浪费一个小时。后来我调整策略——先写一个保证正确的暴力版本，哪怕它过不了大数据，至少能验证思路。

暴力版本的价值有三个。第一，它绝对正确（在小数据下），可以用来当对拍的基准；第二，它帮你理清题目逻辑，优化方向往往藏在暴力代码的重复计算里；第三，它能骗到部分分，洛谷很多题的数据是分梯度设置的，不AC也有分，别看不起这点分。

2.3 对拍：本地调试的正确姿势

洛谷允许反复提交，但每次提交都有间隔和记录，不适合用来调试。我的做法是本地写对拍脚本：一个暴力程序，一个优化程序，再加一个生成随机小数据的脚本，不断跑两边的结果，一旦不一致就说明优化程序有bug。

对拍脚本本身不复杂，核心思路就是无限循环生成数据，分别跑两个程序，比对输出。Windows下可以用批处理，Linux或Mac用bash。我自己常用的简化版本思路：

while true; do echo "test case: $i" python3 gen.py > input.txt ./brute < input.txt > ans_brute.txt ./opt < input.txt > ans_opt.txt if ! diff -q ans_brute.txt ans_opt.txt > /dev/null; then echo "WA found at case $i" break fi i=$((i+1)) done

对拍能救命的场景太多了。印象最深的一次是某道搜索题，我用记忆化搜索写的，本地样例全过，提交就WA，最后对拍暴露了状态转移的方向反了。没有对拍的话，我可能得盯代码盯到天亮。

2.4 题解的正确食用方式

不会做的题到底该不该看题解？该看，但要看方法。我的原则是卡题30分钟没思路，就允许自己看题解。

但看题解绝不直接拉到代码区。先看作者的“思路”部分，关掉页面，自己尝试写一遍。写不出来再回来看关键提示，还写不出来才看代码。这个方法听起来麻烦，但比“看完代码默写一遍”有效得多，因为默写代码只是复制粘贴，自己从思路推导代码才是真掌握。

看完题解之后，我会在错题本里写一句“一句话题解”，比如“P1928：括号展开类字符串题，递归或栈处理，注意拼接方向”。这句话能帮助我在一个月后快速回忆起整道题的核心。热词里提到的“P14258题解”这类情况，我反而建议先捂住题解自己做，做完了再去对比别人的写法，收获比直接看大得多。

3. 常见题型的核心解法与踩坑实录

洛谷的题目范围很广，但刷到普及+/提高-这个阶段，你会发现题型其实有规律。我把最常遇到的几类连同踩过的坑一起拆开讲。

3.1 字符串与模拟：读题力就是第一战斗力

字符串题和模拟题看起来没有算法含量，实际上最容易翻车。模拟题的难点在于“状态之间的关联”，你对外层循环、内层状态、边界条件稍不留神就会错位，而且这类题数据一大，调试起来极其痛苦。

P1928外星密码是字符串处理里的经典题，核心是括号展开，可以用栈也可以用递归。我当时的教训是：递归展开时，拼接字符串的次序特别容易反，应该先处理内层再处理外层。用递归写的时候别急着优化，先把“返回展开后的字符串”这个语义写对，再考虑用指针或者索引优化。

字符串匹配和统计类的题，很多都可以用哈希或KMP解决。洛谷的字符串模板题不少，建议把KMP的next数组含义彻底搞懂，别只背模板——面试和机试都喜欢在这上面变个花样。

3.2 搜索与记忆化：状态设计比剪枝更重要

搜索是很多新人的第一道坎。以P7074这类方格取数题为例，看到题目第一反应可能就是DFS。但纯DFS会面临大量重复子问题，所以需要记忆化：把“当前在某个坐标、已经走过的方向”作为状态存进数组，下次再走到同样状态时直接返回结果。

这里容易踩的坑是状态设计不完整。如果漏掉一个维度，比如只存坐标不存方向，结果就会错乱。判断状态是否完整有个笨办法：把递归函数的每个参数都想一想，问一句“这个参数会影响返回值吗？”会，就必须进缓存维度。

剪枝分为可行性和最优性两类。可行性剪枝是“这条路继续走也到不了终点”，最优性剪枝是“当前代价已经超过已知最优解”。剪枝不会改变结果的正确性，但能极大缩短时间，尤其是埃及分数这类经典搜索题，没有剪枝基本跑不出结果。

3.3 动态规划：转移方程不是拍脑袋

动态规划是洛谷题库的中坚力量。很多人觉得难，是因为试图“一步到位”地理解转移方程。我的经验是，拿到一道DP题，先尝试用递归暴力描述问题，再找重复子问题，最后把递归改成填表，这样推导出的转移方程才靠谱。

以P1048采药为例，它是0/1背包。定义dp[j]为容量为j时能获得的最大价值，转移就是“不取当前物品”和“取当前物品”两者取最大。滚动数组优化的时候，内层循环必须倒序遍历，否则同一个物品会被重复选取。这个“为什么倒序”的问题，我在实战中至少给三个人讲过：正序会让新值覆盖老值，导致一件物品用多次；倒序才能保证每件物品只决策一次。

DP的初始化也经常坑人。dp[0]该赋什么值？哪些状态是“不可能”的？以路径计数为例，边界上一开始就要赋1，否则整条链都是0。记住：初始化不是复制题解里的代码，而是从状态定义推导出来的。

3.4 数学与数论：刷题不上强度，永远不知道自己怕数学

数论题在洛谷占比不低。质数筛、最大公约数、快速幂、乘法逆元，这些属于基本功。热词里有“洛谷埃及分数”，这是迭代加深搜索与剪枝结合的经典，另一个角度也说明数学结论和搜索是分不开的。

我做这类题最大的心得是：不要试图记住所有定理，而要把“为什么”搞清楚。快速幂为什么能省时间？因为它把指数按二进制拆分，把乘法次数从b次压到log b次。逆元为什么用费马小定理？因为模数是质数时，a^(mod-2)就是a的逆元。明白这些之后，即使忘了模板也能现场推。

见到1e9+7之类的模数，涉及乘法就要取模，加减法取模前要处理负数——先加模数再取模。这些细节没人提醒的话，WA都不知道错哪。

3.5 贪心与图论：证明比结果重要

贪心算法看起来就是“每次选最优的”，但为什么是对的？很多题要证明局部最优能推出全局最优，常用的方法是排序不等式和交换论证。洛谷P1248这类排序优化题，本质就是贪心排序，核心在比较函数怎么写。比较函数一旦写错，样例能过，大数据必WA。

图论这一块，最短路、并查集、最小生成树是高频基础。Dijkstra优先队列版本要背熟，Kruskal排序加并查集的逻辑要刻进脑子里。坑点主要在细节：有重边时取最小边权，无向图加边要加两次，自环直接忽略。负权图不能用Dijkstra，老老实实SPFA或者Bellman-Ford，这是很多模板题故意埋的雷。

4. 代码细节与性能优化：洛谷最容易卡人的几个坑

很多时候你的算法没问题，但就是不AC，原因在于代码层面的性能黑洞。这个章节专门讲不同语言在洛谷做题时最容易踩的坑。

4.1 C++：关掉流同步，学会快读

洛谷的C++用户最多，踩坑案例也最多。首先第一行习惯性加上：

ios::sync_with_stdio(false); cin.tie(nullptr);

不加这两句，同样的算法cin比scanf慢一个量级，碰上大数据就直接TLE。如果你还想再稳一点，直接手写快读函数：

inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } return x * f; }

快读函数的原理是绕开标准输入流，用getchar逐字符解析整数，这在输入量达到百万级别时优势非常明显。但注意，用了快读就不要再混用cin，两套输入体系混用会有奇奇怪怪的bug。

另外，看到数据范围可能出现1e9级别，先用long long思考一遍。int最大值21亿出头，两个1e9相乘直接溢出，别等WA了才想起改类型。数组能开全局就开全局，函数里开大数组会导致栈溢出，这是RE而不是WA，排查起来更迷惑。

4.2 Java：Scanner是你最大的敌人

在洛谷用Java刷题，最经典的悲剧就是Scanner读入，TLE。Java的Scanner性能极差，处理10万级别输入就吃力了。正确姿势是BufferedReader加StringTokenizer：

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); // 后续读入同理 } }

如果对性能还有更高要求，可以用StreamTokenizer，它是C的scanf在Java里的亲戚，速度更快。另外洛谷Java提交，主类必须叫Main，否则编译器直接CE。数据结构方面，能用基本数组就别用ArrayList，频繁拆箱装箱在1e5以上的循环里会明显拖慢速度。

4.3 Python：用PyPy，一次读完所有输入

Python在洛谷能做，但要注意三个点。第一，提交语言选择PyPy3而不是CPython，PyPy对循环的优化能快好几倍，这是无数人用血泪试出来的。第二，读入不要用input()循环，用sys.stdin.buffer.read()一次性读：

import sys data = sys.stdin.buffer.read().split()

一次性读入后按顺序消费，在数据量大时能省掉大量IO时间。第三，递归深度默认只有1000，遇到DFS深了就报递归错误，开局设置一下：

sys.setrecursionlimit(1 << 25)

Python适合字符串处理、数学推导、纯思维题；纯数据结构的大模拟题，比如手写平衡树、大常数线段树，Python会比较吃亏。判断一道题适不适合Python写，就看数据范围大不大、常数额外高不高。

4.4 内存估算与MLE

内存超限比运行超时更隐蔽，因为本地跑得好好的，提交就报MLE。记住基本内存单位：int占4字节，long long占8字节，一维数组大小乘以元素大小就是内存开销。洛谷常见内存限制是128MB或256MB。

举例，开一个int数组，长度2千万，内存就是2000万乘以4字节等于80MB，再加上其他变量就逼近128MB了。这时候要么改用short，要么改用滚动数组，要么换成vector按需申请。我习惯写代码前先估算一下“这个数组最多能开多大”，把内存问题消灭在编译之前。

5. 常见问题与排查技巧速查

最后这部分我最想写给新人：当你提交之后跳出一个“红色结果”，你应该按什么顺序排查。

5.1 洛谷评测结果含义速查

5.2 高频WA原因排查表

5.3 三个亲历问题复盘

第一个RE案例：某次递归深度不够导致栈溢出，本地测试数据小没暴露，提交到大数据就崩了。排查时发现递归函数里有个大数组作为局部变量，每层栈都复制一份，直接压爆栈。改成全局变量或者传入引用，问题消失。

第二个WA案例：一道多组输入的题目，我忘了在每组数据开始前重置访问标记数组。第一组跑完标记全是true，第二组所有答案都是错的。从此之后，所有多组数据题的第一行代码都是“重置状态”。

第三个TLE案例：循环内部每次都复制整个vector，用来做临时快排。数据量小的时候看不出来，数据量一上来就超时。后来改成直接在原数组上排序，并且用索引代替拷贝，时间降了一个数量级。性能优化往往不是魔法，就是减少重复劳动。

说到排查工具，本地用调试器逐行看当然可以，但对竞赛题来说效率太低。我更推荐用输出中间变量的方式做“人肉单步调试”，配合对拍脚本定位差异点，比纯看代码猜要快很多。

5.4 几句真心话

刷到三百多道题之后，我最大的变化反而不是在算法层面——看到数据范围就条件反射地估算复杂度，看到字符串先考虑边界条件，看到图先画个样例跑一遍。这些习惯不是在某一本教材里学到的，就是一道题一道题喂出来的。

现在网上能搜到不少“洛谷300题精析”“XX必刷题单”之类的资源，下载过几份，发现内容大同小异，本质还是前人刷题记录的整理。与其迷信别人的清单，不如把自己做过的题号、错题原因、一句话思路记下来，形成自己的私人题单。哪怕只有五十道题，那也是实打实长在自己身上的东西。往后不管是继续在洛谷往上打，还是回头去刷力扣，这些底层能力都会一直在。