其实今天这个标题一开始是我在日记软件里随手起的。补题日记这个系列我写了快两年每次比赛结束之后不管打得怎么样我都会留一篇记录。26-1-12 指的是 2026 年 1 月 12 日也是这个系列的最新一篇。今天有点特殊因为我连续欠了三场比赛的题没补从早上十点坐到晚上十一点总算把债还掉了一大半。这篇文章就把今天最有价值的部分记录下来三道不同考点的题目复盘、一个折磨了我两个小时的 Bug、一次复杂度翻车现场以及我对补题这件事本身的一些新想法。如果你也在搞算法竞赛或者正在为了面试刻意刷题这篇日记里的思路重建过程、复杂度估算方法和调 Bug 过程应该能给你一些参考。1. 为什么补题比刷新题更值钱1.1 比赛后的难受瞬间才是真正的学习信号经常有人问我自己也打比赛也刷题为什么进步这么慢。我一般会反问一句你比赛没做出来的题后来是怎么处理的大部分人的回答分成两类一类是等题解出来看了一眼觉得自己差一点就想到就没管了另一类是太难的放着以后再补然后就再也没有以后了。这两个答案的问题是一样的你只是把题看懂了但你没有把自己的思考过程重新走一遍。我说一个自己的体会。比赛时被某道题卡住的那个瞬间大脑里其实发生了很多事情我试过什么思路、为什么走不通、在哪个地方开始绕圈子、是不是对某个算法有错误的预设。这些信息非常值钱但如果不立刻记录下来隔一天就忘干净了。补题就是把那个瞬间重新捡起来用冷静的状态去审视当时的自己到底缺在哪一步。这比做十道新题更能说明问题因为新题只会暴露这道题我不会而补题能暴露我为什么不会这一类题。1.2 补题的三个层次看懂、会写、能讲我把补题分成三个层次今天的三道题刚好分别对应了这三个层次。第一个层次是看懂。看完题解或者听完别人的讲解点头说哦原来是这样。这个层次最廉价但也是很多人停下来的地方。第二个层次是会写。合上题解自己从头把代码写一遍能过题这就开始有价值了。第三个层次是能讲。隔一天之后不看任何资料能把这道题的思路讲给别人听包括为什么这样设计状态、为什么会想到这个算法、最关键的转化点在哪里。到了这个层次这道题才算真正长在你身上。我今天的补题原则就是每道题至少走到第二层重点题必须走到第三层。你可能觉得这很费时间但事实证明一道真正吃透的题顶得上十道看懂的题。2. 今日三道题复盘从不会到会的完整路径2.1 第一道区间划分类 DP难点在预处理先说我今天补的第一道题一道很典型的区间划分 DP。题目大意是这样给定一个长度为 n 的正整数数组要把数组划分成若干个连续段每一段的代价是该段内最大值和最小值之差的平方求整个数组的最小划分总代价。数据范围是 n ≤ 2000。我当时在比赛里卡住的原因很蠢我一开始就觉得这题应该是 DP状态定义也想出来了设 dp[i] 表示前 i 个元素的最小划分代价转移就是枚举上一段从哪里开始dp[i] min_{0 j i} (dp[j] cost(j 1, i))但没有提前算好 cost 数组的话每次转移都要把区间重新扫一遍找最大值和最小值总的复杂度是 O(n^3)n 2000 的时候大概是 8×10^9 次操作任何评测机都不可能跑完。我当时纠结了很久一直在想怎么优化这个转移过程反而没意识到自己真正缺的是一个 O(n^2) 的预处理。其实只要先花 n^2 的时间把所有区间的最大值、最小值求出来存进两张表里cost 就变成了 O(1) 查询整个 DP 直接降成 O(n^2)。我后来补题的时候把预处理写成了递推式而不是对每个区间重新扫描for (int i 1; i n; i) { mx[i][i] mn[i][i] a[i]; for (int j i 1; j n; j) { mx[i][j] max(mx[i][j - 1], a[j]); mn[i][j] min(mn[i][j - 1], a[j]); } }这里有一个很关键的观察区间 [i, j] 的最大值可以由区间 [i, j-1] 的最大值和 a[j] 推出来。也就是说最大最小值表可以按右端点递推出来不需要在枚举 j 的时候再套一层循环去逐个数比较。这个递推代替重复扫描的思路在很多 O(n^2) 预处理的题里都是核心思想。预处理完DP 本身反而特别简单for (int i 1; i n; i) { dp[i] 1e18; for (int j 0; j i; j) { int w mx[j 1][i] - mn[j 1][i]; dp[i] min(dp[i], dp[j] w * w); } }这道题补完我给自己记了一条经验当 DP 转移里出现某种区间内部信息时先停下来算一下这个信息能不能全部预处理出来。如果能那复杂度通常一下子就降一个量级。很多时候你不是不会 DP而是被重复计算拖死的。2.2 第二道二分答案加贪心思路记住后会有肌肉记忆第二道题是个典型的最小值最大化问题。题目大意一条直线上有若干个补给点需要安排 k 个基站每个基站有一个相同的覆盖半径 R要求所有补给点都被至少一个基站覆盖求最小的 R。这个题我在比赛里是有想法的我知道这种让最大值最小的题基本都靠二分答案。但我栽在了一个贪心细节上我当时是从左往右每遇到一个没被覆盖的点就把基站放在这个点正上方覆盖半径是 R。乍看没问题但实际是错的因为把基站放在当前点正上方向左方向的覆盖能力全部浪费了。正确的贪心是遇到第一个没被覆盖的点 p就把基站放在 p R 的位置这样基站既能覆盖 p又能尽可能多地覆盖右边更远的点向右的覆盖范围最大。补题的时候我发现这个错误其实很典型。很多人二分答案都能想到但 check 函数里的贪心策略想得不够细。check 本身很简单bool check(int R) { int cnt 0; int i 1; while (i m) { cnt; int cover pos[i] R; // 基站放在 pos[i] R while (i m pos[i] cover) i; } return cnt k; }然后二分 R 的范围从 0 到最大坐标差。二分答案的复杂度是 O(log V)每次 check 是 O(m)整体非常快。这道题补完之后我的收获不只是贪心要往右放这一点而是对二分答案有了更系统的认知二分答案的本质是把最优化问题硬生生转化成判定问题一旦转化成功问题难度就大幅下降。以后再看到最小化最大值最大化最小值满足某个条件的极限值这类描述我脑子里第一反应就是二分答案加一个贪心或者 DP 的 check。2.3 第三道分层图最短路状态维度的扩展第三道题让我补得最痛快因为它涉及一个我早就听过但一直没真正用过的技巧分层图最短路。题目大意给一个 n 个点 m 条边的无向图可以最多免费走 k 条边求从 1 号点到 n 号点的最短路径长度。n、m 在 10^5 级别k ≤ 10。正确做法是把原图复制成 k1 层第 i 层表示已经免费使用了 i 条边的状态。每条普通边仍然连接同一层里的两个点边权不变同时从第 i 层的 u 到第 i1 层的 v 连一条边权为 0 的边表示使用一次免费机会经过这条边。最后从第 0 层的 1 号点出发跑一次 Dijkstra答案就是所有层里 n 号点的最短距离。我当时在比赛里没做出来主要是没建立起把状态放进节点里的思维。我一直盯着原图想觉得最多免费 k 条边这个条件没办法在边权上处理。实际上分层图的本质就是用节点维度去承载状态信息把原来一个点拆成多个带状态的点图就变成了普通最短路问题剩下的交给 Dijkstra 就好。补题代码的关键部分大概是这样的思路struct Node { int v, layer, dist; bool operator(const Node other) const { return dist other.dist; } }; // 建图时 // 同层边add(i * (k 1) layer, j * (k 1) layer, w) // 跨层边add(i * (k 1) layer, j * (k 1) layer 1, 0)这里我特别想提醒一句分层图的层数 k 不能太大。这道题 k ≤ 10所以节点数是 n × 11在 10^6 级别Dijkstra 完全扛得住。但如果 k 是 10^5你就得换个思路了那种情况通常会转化为在最短路基础上删掉最大的几条边之类的贪心不是简单分层能解决的。所以分层图是一把很好用的刀但要留意适用范围。三道题补完我最大的感受是这些考点我其实都听说过但真正到了赛场上能不能在正确的时间想到正确的工具靠的不是知道而是练过。补题就是补这个练过。3. 调了两小时的那个 Bug全局变量与递归栈的联动翻车今天原计划补三道题就收工结果第二道题结束后我顺手点开了一道以前比赛的题想看看当时卡住的那题现在会不会做。然后我就掉进了一个持续两个小时的 Bug 深渊。这道题本身不难是个树的遍历加区间统计需要写一个递归函数去统计每棵子树的某种信息。我当时为了图省事把当前子树的最小值和当前子树的最大值设成了两个全局变量。3.1 现象样例全过一提交就错一堆一开始样例全部通过我心里还挺美。结果一发评测WA 了一大片而且错的数据点毫无规律。我第一反应是算法本身不对于是把递归逻辑从头读了一遍没发现问题。又构造了几种边界情况单点、双点、链状树全部能跑对。这就很邪门了逻辑看起来没问题普通数据也对但一上大数据就乱。3.2 定位过程靠打印递归进出栈找真凶我开始在递归函数里加调试输出打算把每次进入子树和离开子树的瞬间都打印出来。跑了一个小数据之后我发现在处理第二棵子树的时候打印出来的当前最大值居然是处理完第一棵子树之后的值而不是回溯完之后该有的值。我瞬间明白了问题就出在那个全局变量身上。我把当前子树最大最小值设计成全局变量的初衷是省事不想在递归函数里多传参。但全局变量在递归里的行为是只要你不显式恢复它就会一直保留最近一次赋值的结果。我的递归逻辑是进入子树前更新 mx子树的子树又更新 mx等这个子树处理完返回我既没有把它还原成父节点该有的值也没有把它保存在局部变量里于是下一棵子树读到的 mx 就是被污染的旧值。在深度大的树上这种污染会一层一层传导最后整个统计结果都是错的。这里给新手一个非常直观的类比全局变量就像一块公共黑板任何在你之后进来的人都会看到你留下的字。递归函数里如果没有在出口把黑板擦干净后进来的分支就会抄到上一份作业的答案。3.3 修复思路与预防写法修复其实很简单递归里需要跟随调用栈变化的信息只能通过参数传递或者用栈结构显式维护。我当时改成在 dfs 函数签名里加两个参数进入子节点时传入新值每一层递归各算各的void dfs(int u, int fa, int cur_mx, int cur_mn) { bool is_leaf true; for (int v : g[u]) { if (v fa) continue; is_leaf false; int new_mx max(cur_mx, val[v]); int new_mn min(cur_mn, val[v]); dfs(v, u, new_mx, new_mn); } // 用 cur_mx, cur_mn 做当前子树的统计 }这个写法的关键是传给子树的不是同一个变量的引用而是经过计算后的新局部变量。这样每一层递归都有自己的临时值不需要回溯恢复这个动作天然不会互相干扰。或者你不想改函数签名就要保证在递归出口处显式恢复全局变量。但我个人强烈建议用参数传值别用全局变量来保存递归过程中的中间状态因为手动恢复的代码很容易写漏尤其在一个函数里有多个 return 分支的时候漏一个就是半夜调 Bug。这个 Bug 虽然浪费了我两个小时但收获也值凡是递归里需要跟着调用栈走的临时信息一律不要用全局变量如果必须用也要在出口处无条件恢复。这个教训我记在补题笔记的第一页。4. 一次复杂度翻车为什么 O(n^2) 能过而我的挂了今天的补题过程里还发生了一次小规模的复杂度翻车事件值得单独拿出来说。4.1 翻车现场同样的复杂度别人的过了我的超时第一道区间 DP 题我最初写的代码在比赛时直接 T 了。我本来以为是自己常数太大赛后去翻同场选手的通过代码发现人家的复杂度也是 O(n^2)但他过了。这一度让我很不理解一样的量级凭什么他能过我不能过后来我把两份代码放在一起对比发现了三个关键差异。第一他的最大值和最小值预计算用的是 int 数组我用的是 long long。n 2000 的时候两个 2000×2000 的 long long 数组大概占 64MB而 int 数组只要 32MB内存访问成本也更高。第二他的 DP 转移内层循环里只做加减和取 min我竟然把 cost 计算拆成了函数调用虽然编译器大概率会内联但代码结构上就比人家多了一层抽象。第三也是最致命的一点他用了快读而我用的是 cin 且没有关同步。当输入量到了几十万级别这个差距就会被放大。4.2 常数优化清单什么值得做什么不值得做这里列一个我在实测中总结的常数优化优先级从上到下性价比依次递减优化手段效果适用场景开 O2 编译优化对循环密集型代码提升明显几乎白拿所有 OI/ACM 环境默认开启日常练习记得开快读 / 关掉 cin 同步数据量在 10^6 以上时收益巨大任何输入量大的题目int 代替 long long多维数组、大循环里收益明显数值范围确定不会爆 int 的地方预计算代替重复扫描直接降一个复杂度量级任何出现重复区间计算的地方减少不必要的函数调用收益看编译器一般不大内层热循环里建议手动展开有一点要说清楚常数优化不能替代算法优化。如果复杂度本身就不对任何常数优化都救不回来。这是我踩过很多次坑之后才真正接受的结论。时间复杂度是大方向常数是细节大方向错了细节再精细也没有意义。4.3 现场口算复杂度的经验公式我平时在比赛里快速估算复杂度靠几个经验值。现代 OJ 上一秒钟大概能跑 10^8 次简单整数运算这个量级上下浮动很大取决于评测机、语言、内存访问模式。保守起见算法整体操作数控制在 10^7 以内最稳。做复杂度估算的时候我会先看数据范围再去匹配算法方向数据范围可接受的复杂度典型算法n ≤ 20O(2^n) / O(n!)状态压缩枚举、状压 DPn ≤ 100O(n^3)基础 DP、Floydn ≤ 2000O(n^2)区间 DP、预处理后 DPn ≤ 10^5O(n log n)排序、二分、线段树、Dijkstran ≤ 10^6 及以上O(n)线性递推、差分、单调队列这个表不是绝对的但它能帮你在开写之前就排除掉错误的算法方向。我当时如果能在动手之前用这个表估一下就不会写出那个 O(n^3) 的代码白白交一发 T。5. 我的补题笔记方法一道题怎样才算吃透这里专门写一下补题笔记的方法毕竟补题日记这个系列的核心就是记录。这套方法是我自己摸索出来的不一定适合所有人但在实践里确实帮我避免了很多次补过等于没补。5.1 一张笔记卡片需要记什么我每补一道题不论难度如何都会在本地维护一个 Markdown 文件按日期排列。每道题固定记这五项题目链接或题号、我的错误点、一句话解题思路、复杂度、可迁移的经验。格式大概是这样的### 2026-01-12 区间划分 DP - 我的错误点只想着优化转移忘了预处理 cost 数组 - 一句话思路dp[i] min(dp[j] cost(j 1, i))cost 预处理后 O(1) 查询 - 复杂度O(n^2) 时间O(n^2) 空间 - 可迁移经验转移中出现区间内部信息时优先考虑全区间预处理我的错误点这一项最重要。因为题解写的是正确做法而你需要记录的是你离正确做法之间隔了什么。只有把错误点写下来下次遇到同类题你才能在关键时刻想起上次我就是在这里翻车的。5.2 隔天重做对抗看懂错觉的有效手段只记笔记其实还不够。我还有个原则叫隔天重做补完一道题第二天早上假装自己从没见过题解重新把这道题做一遍。如果还能独立写出来说明这道题真的补进去了如果写不出来说明昨天的我会了只是假象。这个原则针对的是看懂错觉。很多人补题的时候看完题解觉得每一步都有道理特别通畅但这种通畅恰恰是危险的因为题解替你完成了最难的从 0 到 1的跨越。隔天重做就是强行把从 0 到 1 这个过程还给你自己。我实测下来大概有四分之一到三分之一的题隔天重做的时候会卡住。这说明当时根本没有内化只是短期记忆的流畅而已。5.3 看题解的正确姿势分步看不一次看完还有一件事想特别说就是怎么看题解。我现在的习惯是一道题拿到手先自己想至少两个小时把想到的思路、为什么失败都写在草稿纸上然后才去看题解。看题解也不是从头到尾全部看完而是只看第一段话或者只看题目给出的关键提示然后合上题解继续自己往下想。这样做的道理很简单最困难的一步往往是从题目到思路的那一步如果一次把整个题解看完你就永远错过了自己跨越这一步的机会。这个方法会显著拉长补一道题的时间但拉长的这部分时间恰恰是最有效的。用句圈里常说的话来概括补题不是把题补完是把我为什么想不到这件事想明白。6. 今天补完题之后的几个反思与下一阶段计划一天补了三道题加一道复习坐了一整天腰酸背痛但脑子特别清醒。趁着这个状态我把今天暴露出来的问题整理了一下顺便给自己排了下个阶段的训练方向。第一个问题很明显我对把问题转化成状态维度这类思想还不太敏感。分层图这道题我听过无数次但比赛里还是想不到。这说明听和会之间缺了大量练习。接下来我打算集中补一小段时间的分层图和状态压缩相关的题每次遇到这种题不管会不会做都先在笔记里写清楚这题的状态维度是什么。第二个问题我在递归和回溯类代码上的习惯不好喜欢用全局变量省参数传递结果今天用两个小时 Bug 买了教训。接下来写递归函数之前我会先想清楚哪些信息是跟随调用栈走的这些信息必须走参数不走全局变量。第三个问题其实是好事今天三道题补完之后我明显感觉到自己对二分答案和区间 DP 的熟悉度上了一个台阶。特别是二分答案赛后重新做这道题的过程让我第一次真正理解了最优化转判定这个操作的威力以前我只是会用现在才算是想明白为什么能用。最后分享一个今天的小插曲。下午补完第二道题的时候我突然给自己加了个任务把今天补的每道题都用一句话向完全不懂算法的室友解释这题在干嘛。结果第一道区间 DP我这句话讲了五分钟都没讲明白室友听完更糊涂了。这个经历让我意识到能用一句话说明白这件事本身也是一个标准而且是一个相当高的标准。以后每补完一道题我都打算试着做一次这句话练习讲不明白了说明自己脑子里还有一团浆糊。补题日记不追求产量追求每篇都真正把问题想透。今天这篇写得比平常长因为那个全局变量的 Bug 实在值得记一笔。如果你也在写补题笔记强烈建议把我的错误点那一栏坚持记下去并且严格执行隔天重做。过几个月回头翻你会看到自己是怎么一步步从会看题解变成会做题的。