洛谷刷题这件事我认真持续了大半年。前前后后AC了两百多道题TLE和WA的次数已经数不清中间也经历过“打开题解就能看懂、关上题解就写不出来”的绝望期。这篇《洛谷刷题有感》我想写的不是某个具体题目的题解而是把这一段在洛谷刷题过程中反复踩过的坑、最终总结出的方法论、以及很多新人不会注意但特别影响体验的细节一次性整理出来。文章覆盖从入门到提高阶段最常见的题型也包含C、Java、Python三种语言在洛谷做题时的性能优化习惯。不管你是刚开始接触OJ刷题的初学者还是刷力扣刷到想换换口味的老手这篇文章应该都能给你一些参考。1. 为什么是洛谷题库、难度梯度与社区生态先聊一个很多人问过的问题同样是刷题网站为什么最后留在洛谷答案其实很简单——洛谷的题库分层做得太适合成长了。1.1 红题到黑题难度梯度本身就是路线图洛谷题库用颜色标注难度最低是红题中间经过橙、黄、绿、蓝最高到紫和黑。这种颜色分级的价值在于它天然对应了一条算法学习路线红题对应“入门”基本是语法题用来熟悉输入输出和循环判断橙题是“普及-”开始涉及枚举、简单模拟、基础贪心黄题到绿题是“普及/提高-”字符串处理、搜索、简单动态规划都在这个区间蓝题到紫题是“提高/省选-”需要组合算法思维比如图论加DP、数论加优化黑题通常是非顶级选手不要轻易碰的。我见过不少新人一上来就找“黑题”“紫题”试水结果看题解都看不懂还打击自信。我自己的经验是按颜色从红到绿循序渐进每个梯度刷够二十道左右再往下一层走。洛谷的题单功能就是干这个的把某一种算法相关的题目串在一起按难度排好照着刷就行。1.2 和力扣、Codeforces的定位差异热词里出现“leecode必刷基础算法题”和“力扣刷题攻略”说明很多人是先从力扣入门的。我不是说力扣不好而是两者的侧重点完全不同。维度洛谷力扣Codeforces定位竞赛综合社区面试题库在线比赛平台题目风格背景故事多、数据范围大经典套路、偏数据结构思维题、构造题多难度曲线红到黑全覆盖简单到困难但整体偏面试难度分级靠比赛分组社区生态题解、讨论、训练场完善题解质量参差题解以英文为主适合场景系统学算法、准备竞赛找工作刷题练思维速度我的建议是如果目标是算法竞赛、考研机试、或者想真正搞懂算法原理洛谷是更合适的主场。如果目标是马上找开发工作力扣的高频题还是要刷但可以等洛谷把底层能力打扎实之后再去事半功倍。两边混着刷也行但别指望用刷力扣的思路来刷洛谷——很多洛谷题的花样更多想靠“背套路”过关很难。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$((i1)) 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的逆元。明白这些之后即使忘了模板也能现场推。见到1e97之类的模数涉及乘法就要取模加减法取模前要处理负数——先加模数再取模。这些细节没人提醒的话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 JavaScanner是你最大的敌人在洛谷用Java刷题最经典的悲剧就是Scanner读入TLE。Java的Scanner性能极差处理10万级别输入就吃力了。正确姿势是BufferedReader加StringTokenizerimport 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而不是CPythonPyPy对循环的优化能快好几倍这是无数人用血泪试出来的。第二读入不要用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 洛谷评测结果含义速查缩写含义我的处理方式AC通过进入下一题WA答案错误检查边界、long long、负数TLE超时检查复杂度、I/O方式、死循环MLE超内存压缩数组、滚动数组RE运行时错误数组越界、除零、递归爆栈CE编译失败看编译信息检查类名/头文件UKE评测机异常重新提交一次5.2 高频WA原因排查表症状排查方向小数据过大数据错是否有int溢出、数组越界样例过提交WA有没有多组数据没重置全局状态边界情况错输入为0、1、负数、最大值时验证过吗字符串题WA换行符、空格、空串、大小写敏感图论题WA重边、自环、负权、未连通5.3 三个亲历问题复盘第一个RE案例某次递归深度不够导致栈溢出本地测试数据小没暴露提交到大数据就崩了。排查时发现递归函数里有个大数组作为局部变量每层栈都复制一份直接压爆栈。改成全局变量或者传入引用问题消失。第二个WA案例一道多组输入的题目我忘了在每组数据开始前重置访问标记数组。第一组跑完标记全是true第二组所有答案都是错的。从此之后所有多组数据题的第一行代码都是“重置状态”。第三个TLE案例循环内部每次都复制整个vector用来做临时快排。数据量小的时候看不出来数据量一上来就超时。后来改成直接在原数组上排序并且用索引代替拷贝时间降了一个数量级。性能优化往往不是魔法就是减少重复劳动。说到排查工具本地用调试器逐行看当然可以但对竞赛题来说效率太低。我更推荐用输出中间变量的方式做“人肉单步调试”配合对拍脚本定位差异点比纯看代码猜要快很多。5.4 几句真心话刷到三百多道题之后我最大的变化反而不是在算法层面——看到数据范围就条件反射地估算复杂度看到字符串先考虑边界条件看到图先画个样例跑一遍。这些习惯不是在某一本教材里学到的就是一道题一道题喂出来的。现在网上能搜到不少“洛谷300题精析”“XX必刷题单”之类的资源下载过几份发现内容大同小异本质还是前人刷题记录的整理。与其迷信别人的清单不如把自己做过的题号、错题原因、一句话思路记下来形成自己的私人题单。哪怕只有五十道题那也是实打实长在自己身上的东西。往后不管是继续在洛谷往上打还是回头去刷力扣这些底层能力都会一直在。