寒假集训第一场积分赛结束的那天晚上我把自己六道题的提交记录从头翻到尾越看越不是滋味三道题赛时过了两道题卡到比赛结束都没交上去还有一道连题意都理解偏了。第二天我把整套题重做了一遍用了整整一个下午加半个晚上这篇就是这次2021寒假积分赛一补题的完整记录。写它的目的很直接——把赛时为什么没做出来这件事拆到能复现、能复用、下次不再踩的程度。不管你是刚学完基础语法、还在为读懂题面发愁的新手还是已经能过签到题、想在积分榜上再往前挪几名的人这篇里的题型拆解、卡点复盘和调试手段都能直接拿去用。补题这件事说白了就是把赛场上暴露出来的知识窟窿一个一个填回去填的过程比再打十场顺风局都值钱。1. 这场积分赛到底考了什么从题型配比说到补题策略1.1 先把六道题的考点摊开来看积分赛的性质决定了它的题目结构难度从签到题往上一路铺前面的题保证大部分人能做出来中间两三道才是真正拉开排名的分水岭最后一两道属于能做出来就进第一梯队的存在。我们这场是六道题、四个半小时我赛后按考点重新归档了一遍大致是这样题号主要考点我这边的赛时状态补题优先级A模拟 边界处理22 分钟 AC但读题读了两遍低重写一遍就走B前缀和 / 差分WA 两次才过中要知道错在哪一行C二分答案有思路判定函数写错没交高DBFS 状态设计赛时用错去重数组TLE高E线性 DP完全没思路高F贪心构造只看了题面视时间先放着从这张表能看出来一个很典型的规律真正拖住我的不是没学过的算法而是学过但用得不对。B 题的前缀和、D 题的 BFS这些都不是新东西问题出在细节——差分的还原方向、BFS 的状态维度。所以补题的重点应该往这类半生不熟的题上倾斜而不是一上来就去啃那道贪心构造。1.2 为什么要花一整个下午补题而不是再刷一套新题这是很多人都会纠结的问题时间有限是做十道新题还是把五道旧题彻底搞懂我的答案很明确——在基础还没打牢的阶段补题的性价比远高于刷新题。原因在于做过和会做之间隔着一条巨大的沟。赛时你做出一道题可能是因为题目刚好长得像你背过的模板可能是样例给得特别友好也可能就是运气好没踩到边界。这种过是不会给你留下任何记忆锚点的下一次换成另一个外壳你还是会卡。而补题不一样补的对象是你自己真实卡住过的地方是已经被验证的薄弱环节每解决一个能力边界就实打实地往里推一格。还有一个更现实的原因积分赛的题目是经过筛选的质量通常比你在题库里随手翻到的题高。同一套题里的题目之间有难度梯度也有出题人的整体设计思路把一套题吃透你等于跟着出题人的思路走了一遍完整的难度爬坡这比自己东一道西一道地乱刷效率高得多。1.3 我给自己定的补题三条线补题也不能漫无目的地补我给自己划了三类处理方式你可以直接照搬赛时完全没思路的题目标是不看题解独立写出 AC 代码。判断标准很硬——关掉题解页面从空文件开始敲一次过。做不到就说明还没懂。赛时写了但 WA / TLE 的题目标是定位到具体哪一行、哪个判断、哪个数组开小了并且能说清楚为什么会错。这类题的收获往往比第一类还大因为错因通常是通用性的换道题还会犯。赛时 AC 但过程磕磕绊绊的题目标是重写一遍把代码压到干净的模板形态。别小看这一步赛时能过但写得一团乱的题下次换个场景大概率会翻车。按这个分类我把 A 归到第三类B、D 归到第二类C、E 归到第一类F 先挂起来等前面的补完再说。这个排序本身就是一种资源分配先补那些投入小、收获大的题把信心和手感先立起来。2. 补题前的准备把我不会拆成能执行的问题清单2.1 赛后一小时内必须做完的三件事补题最容易失效的方式就是比赛结束隔了两三天再回头看。那时候你只记得这题我没做出来但具体卡在哪、当时脑子里闪过什么念头、哪一步开始乱全忘了。所以赛后一小时内趁记忆还在我一般做三件事第一件是把所有提交记录截图或导出存档。不是为了留纪念是为了看时间线——你在这道题上耗了多久、交了几次、每次改动大不大。我第一次 WA 之后隔了 40 分钟才交第二次这 40 分钟在干什么往往就是真正的卡点所在。第二件是边回忆边写卡点笔记写多糙都行关键是趁热。比如 D 题我当时的笔记就一行用了 bool vis[x][y]但钥匙状态没进 vis一直 TLE。这一行字后面帮我省了半小时。第三件是只给题解划边界不马上看内容。我的习惯是先看题解的第一句或者标签比如二分答案或者BFS 状压然后立刻关掉自己先想二十分钟。直接从头读到尾会产生一种我懂了的错觉实际上只是跟着别人的思路跑了一遍。2.2 给每道题打三个标签这是我从一位学长那里学来的方法实测非常好用。每道题打过之后就贴三个标签考点标签这题的核心算法是什么。一题可能有多个比如差分 离散化。卡点标签你具体在哪一步翻的车。越具体越好写判定函数写反了比写二分不熟有用一百倍。手感标签赛时是秒了磕磕绊绊过还是完全没思路。这个标签决定了这道题要不要回炉重写。三个标签里真正有价值的是卡点标签。因为它会形成一个聚焦的清单当你发现判定函数写错这个标签在一两个月里出现了五六次那说明这已经不是偶然失误而是你需要专门花时间攻克的系统性短板。这种模式识别光靠刷题是刷不出来的。2.3 本地环境和调试工具的准备补题最好是本地写完、本地测完再交尤其是需要反复调试的题。我本地的编译习惯是这样的# 开警告、开常用优化能提前发现一堆低级错误 g -stdc17 -O2 -Wall -Wextra -Wshadow -o a a.cpp # 小数据直接用管道喂进去 ./a in.txt # 需要看时间的时候 time ./a in.txt-Wall -Wextra这两个参数强烈建议常开。未初始化变量、有符号无符号比较、变量遮蔽这类问题编译器基本都能帮你指出来。我有一次 WA 就是因为把一个int拿去和size()的返回值直接比较开了警告之后一眼就看到了。除了编译参数补题时我还会准备一个暴力对拍脚本第 4 节会详细写。很多逻辑错误靠肉眼看是看不出来的但只要有对拍通常几十组随机数据就能把问题揪出来。这个投入非常划算写一次脚本能用一整个赛季。提示本地跑数据的时候记得把输入输出重定向的代码在提交前删掉或者用条件编译包起来否则线上判题会直接 WA。3. 核心题型逐个拆解从签到题到卡住的那道 DP3.1 A 题签到读题比算法重要签到题的算法含量通常很低它真正考的是读题的精度。A 题大概是一组数列问有多少对相邻元素的差的绝对值恰好等于某个给定值。算法上就是一次线性扫描但坑在几个地方n 可能等于 1这时答案是 0不能直接访问下标 1、数值可能到 1e9 级别两个数相减不需要开 long long但如果是求和就要考虑、以及相邻对的定义是 i 和 i1不是所有两两组合。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long k; cin n k; vectorlong long a(n); for (auto x : a) cin x; int ans 0; for (int i 0; i 1 n; i) { if (llabs(a[i] - a[i 1]) k) ans; } cout ans \n; return 0; }这段代码没什么技术含量但有两个习惯值得说循环写成i 1 n而不是i n - 1前者在 n 为无符号数时不会出问题比较用llabs而不是abs避免abs作用在 long long 上时被截断成 int。这两个小习惯我在补题时专门重写了一遍就是为了让它们在手上形成肌肉记忆。3.2 B 题前缀和与差分别把两者混着用B 题我赛时 WA 了两次第一次是思路就选错了工具第二次是差分还原的方向写反了。这里必须把前缀和和差分的适用场景掰扯清楚。前缀和解决的是数组不动反复问某一段的和。预处理 O(n)单次查询 O(1)。适用条件很硬数组本身在查询过程中不能改。差分解决的是数组反复被区间修改最后统一问结果。区间加值 O(1)最后一次前缀和还原成原数组 O(n)。反过来如果要求每次修改后立刻查询差分就不行了得用树状数组或者线段树。B 题是典型的多次区间加最后输出整个数组所以标准解法是差分。代码骨架如下int n, m; cin n m; vectorlong long d(n 2, 0); // 多开两位防止越界 while (m--) { int l, r; long long v; cin l r v; d[l] v; d[r 1] - v; } vectorlong long a(n 1); for (int i 1; i n; i) a[i] a[i - 1] d[i];注意差分数组一定要开到 n 2。因为d[r 1]在 r 等于 n 时会访问下标 n 1开 n 1 就差这一位。我赛时的错误是把还原循环写成了从后往前累加。前缀和的还原必须是从前往后因为a[i]依赖a[i - 1]方向反了得到的就是一堆无意义的数。这个错误看起来很蠢但在紧张状态下真的很容易犯。另外一个容易被忽略的点差分数组和原数组的语义是分离的。差分数组里存的是变化量不是最终值。补题的时候我专门在草稿纸上画了一遍还原过程把每个位置的语义标出来之后就再没写反过。3.3 C 题二分答案判定函数才是本体C 题我赛时想对了方向是二分答案但判定函数写错了逻辑一直没交上去。二分答案这类题有个特点外层模板几乎不用动难点全在判定函数。题目大概是这样的给 n 段长度不一的木棍要切成 k 段等长的小段问小段的最大可能长度。单调性很直观——如果长度 L 可行那么所有比 L 小的长度都可 行如果 L 不可行比 L 大的都不可行。于是可以二分答案。bool check(long long L) { if (L 0) return false; long long cnt 0; for (int x : a) cnt x / L; return cnt k; } long long lo 0, hi *max_element(a.begin(), a.end()) 1; while (lo 1 hi) { long long mid lo (hi - lo) / 2; if (check(mid)) lo mid; else hi mid; } cout lo \n;这里有几个我在补题时才真正搞明白的点第一二分开区间写法的边界。我用的是lo 1 hi这种左闭右开的写法lo 始终是可行解hi 始终是不可行解最后答案是 lo。这种写法的好处是不会死循环也不会出现 mid 卡在边界上的问题比while (lo hi)那种写法省心得多。第二上界要取 max 1。如果上界直接取 max当答案恰好等于 max 时hi 本身是可行解就破坏了我们hi 不可行的约定。加一是为了给二分留一个必然不可行的哨兵。第三判定函数里的溢出。cnt用 long long因为 n 可能是 1e5 级别每一段都除出上千段的话int 会溢出。这种题的数据范围一定要在写判定函数之前先看一眼。第四除零保护。当 L 等于 0 时x / L会直接崩掉。虽然二分过程中 lo 从 0 开始mid 一般不会取到 0但加一行判断是零成本的安全网。3.4 D 题搜索状态设计错了BFS 也会超时D 题是这场里我最有收获的一道。题目是网格迷宫里面有若干把钥匙和对应的门问从起点到终点的最短步数。我赛时的第一版代码是这样写的bool vis[N][N]; // 错误示范然后就是无休止的 TLE 和 WA 交替出现。问题出在同一个格子带着不同的钥匙到达后续能走的路是完全不同的。用二维的vis去重会把带着钥匙再次到达这种合法且必要的状态给剪掉于是要么找不到答案要么在某个环里反复绕。正确做法是把钥匙的持有情况压进状态里。钥匙种类一般不超过 10 种用一个整数当位掩码就够了int vis[N][N][1 10]; // -1 表示未访问 struct Node { int x, y, key; }; int bfs() { memset(vis, -1, sizeof(vis)); queueNode q; q.push({sx, sy, 0}); vis[sx][sy][0] 0; while (!q.empty()) { auto [x, y, key] q.front(); q.pop(); int d vis[x][y][key]; if (x tx y ty) return d; for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (nx 0 || ny 0 || nx n || ny m) continue; char c g[nx][ny]; if (c #) continue; int nk key; if (c a c j) nk | (1 (c - a)); if (c A c J !(key (1 (c - A)))) continue; if (vis[nx][ny][nk] -1) { vis[nx][ny][nk] d 1; q.push({nx, ny, nk}); } } } return -1; }补这道题让我总结出几条通用经验BFS 的状态到底是什么必须明确写下来。这题的状态是 (x, y, 已持有的钥匙集合)三维缺一不可。以后遇到带条件的网格题先问自己两个人在同一个格子上什么情况下后续走法不同答案就是状态的额外维度。去重数组的大小要心算一遍。100 × 100 × 1024个 int 大概是 40MB接近但不超常见的 256MB 限制。如果再大一点就得换成short或者别的压缩方式。补题的时候顺手算一下内存是个受益终身的习惯。BFS 的步数记录方式有两种一种是存在 vis 数组里上面这种一种是队列里多带一个距离字段。前者更省空间后者写起来更直观。我更推荐前者因为不容易在多层循环里把距离搞混。3.5 E 题线性 DP转移顺序决定成败E 题我赛时完全没思路补的时候才发现是道很标准的线性 DP。题目大意是从一串数里选出若干个要求不能选相邻的两个求最大和。状态定义是dp[i]表示前 i 个数能取到的最大和转移就两种情况选第 i 个那么第 i-1 个不能选值是dp[i-2] a[i]不选第 i 个值是dp[i-1]。vectorlong long dp(n 1, 0); dp[0] 0; dp[1] max(0LL, a[1]); for (int i 2; i n; i) dp[i] max(dp[i - 1], dp[i - 2] a[i]); cout dp[n] \n;看起来简单但补题时有三个点值得反复确认第一初始化的语义。dp[0]表示前 0 个数和当然是 0dp[1]表示前 1 个数如果这题允许不选任何数那它就是max(0, a[1])。如果题目要求必须选至少一个初始化就得改成a[1]。这一步写错后面全错但样例经常测不出来。第二转移顺序。dp[i]依赖dp[i-1]和dp[i-2]所以必须从小到大推。如果这题的依赖反过来比如依赖 i1就得从大到小。判断依据很简单算 dp[i] 需要的值必须先算好。第三边界与负数。如果数组里全是负数答案是 0一个都不选。这种情况下dp[1] max(0LL, a[1])就派上用场了。很多人写 DP 挂就挂在这些边界上而样例往往给的是正数数组。补完 E 题之后我把这一类选或不选的线性 DP 专门整理成了一个模板包括必须选、可以空、环形、带限制等几种变体。下次再遇到同类题从状态定义到初始化基本可以秒出。4. 卡点复现与调试实录我的 WA 和 TLE 是怎么来的4.1 五类判题结果对应的真实原因补题的过程中我把这场所有错误提交的判题结果和原因整理成了表这张表后来在整个集训期都帮我省了大量时间判题结果常见真实原因快速定位手段WA边界没处理、逻辑分支写反、忘开 long long对拍、造最小数据、手算小样例TLE复杂度算错、去重不到位、常数过大数最坏情况的循环次数、加计数变量RE数组越界、除零、递归爆栈开-fsanitizeaddress编译、检查下标范围MLE数组开太大、递归层数太深手算字节数元素数 × 类型大小PE行末空格、多余换行严格按题面格式输出其中WA 和 TLE 占了绝大多数。有意思的是TLE 里头有相当一部分其实是逻辑错误导致的死循环或重复遍历而不是真的复杂度不够。D 题就是典型算法是对的去重错了于是状态数爆炸。调试的时候我会开一个 sanitizer 版本跑小数据很多越界和未初始化问题会被直接指出来g -stdc17 -g -fsanitizeaddress,undefined -o a_dbg a.cpp ./a_dbg in.txtsanitize版本会慢不少但用来跑小数据足够了。补题阶段用这种方法找出过好几次数组开小了一位的问题这类错误在正常编译下可能只是偶尔 WA查起来非常头疼。4.2 对拍脚本花二十分钟省一整晚对拍是补题最有效的调试手段没有之一。逻辑很朴素写一个一定能过但很慢的暴力解法写一个你的正解随机造数据两份代码跑同样的输入比输出。只要出现不一致立刻把这个数据留下来单独分析。造数据我用 Python因为随机数和字符串处理方便import random n random.randint(1, 8) print(n) print(*[random.randint(-10, 10) for _ in range(n)])对拍的主循环用 shellfor i in $(seq 1 1000); do python3 gen.py in.txt ./brute in.txt out1.txt ./mine in.txt out2.txt if ! diff -q out1.txt out2.txt /dev/null; then echo 差别出现在第 $i 组数据 cat in.txt break fi done这套东西的关键在于数据范围要小。很多人一开始就把 n 开到 10^5结果暴力跑半天出不来对拍就废了。正确做法是把 n 控制在 8 到 30 之间数值范围也压小这样几百组数据几秒钟就能跑完而且小数据更容易暴露边界问题。心得对拍跑出不一致之后别急着改代码先把那份数据手算一遍。很多时候看着数据你就能看出是哪一类的边界没处理而不是只知道我错了。4.3 复杂度估算写代码之前先算一遍赛时因为复杂度算错而 TLE 的情况比因为算法不对而 TLE 的其实更多。我在补题时把常用的数据范围对照表重新背了一遍n 的范围可接受的复杂度典型算法n ≤ 20O(2^n)、O(n!)状压、全排列枚举n ≤ 100O(n^4)四重循环 DPn ≤ 500O(n^3)Floyd、区间 DPn ≤ 5000O(n^2)二维 DP、朴素 LCSn ≤ 1e5O(n log n)排序、二分、树状数组n ≤ 1e6O(n)线性扫描、双指针n ≤ 1e18O(log n)快速幂、矩阵快速幂这张表的好处是读完题先看数据范围基本就能反推出出题人想要的算法。比如看到 n ≤ 20脑子里第一时间就该想到枚举所有子集看到 n ≤ 1e5 又要问区间和那就该想到前缀和或者树状数组。补题的时候我把每道题的 n 范围和自己的复杂度都在笔记里写了一遍这个习惯让我在之后几场里 TLE 的次数明显下降。5. 补完题之后的沉淀模板、错题本和训练节奏5.1 模板库要怎么整理才真的有用很多人都有模板库但大部分模板库是收集来的不是自己写的用的时候根本想不起来或者套上去发现参数不对。我的做法是只把自己在真题里用过、并且调试通过的核心片段收进模板库而且每个模板都附上一份最小可运行示例和一句什么时候用它。比如差分这个模板我的记录是这样的// 适用多次区间加最后统一查询整个数组 // 复杂度每次修改 O(1)还原 O(n) int n, m; vectorlong long d(n 2, 0); // 区间 [l, r] 加 v d[l] v; d[r 1] - v; // 还原 for (int i 1; i n; i) a[i] a[i - 1] d[i];关键是那句适用。模板本身网上一搜一大把真正有价值的是你自己总结出来的适用边界。什么时候用差分、什么时候必须换树状数组这个判断才是能力的体现。5.2 错题本记录格式只写三行我在错题本上给每道题只留三行因为写多了根本不会回头看题目积分赛一D 题 错因BFS 去重数组只用二维钥匙状态没进状态空间导致重复遍历 迁移所有带条件的最短路题先问自己在同一个位置什么情况下后续走法不同注意第三行迁移。这一行才是错题本的灵魂——它逼着你从一道具体题目里抽出通用的教训。D 题之后我再遇到迷宫里有某种收集物的题第一反应就是先看要不要把收集情况压进状态。这种反应速度是靠刷题刷不出来的只能靠错题本一遍遍强化。5.3 下一场之前的训练安排补完这一场之后我给自己排了一个简单的训练节奏每天两道题一道是当天学的新知识点比如树状数组一道是从错题本里挑的旧题重做。这个方法的好处是新知识在学旧的漏洞同时在补两边都不落下。另外每周我会留出半天做整场模拟随便找一套往年的积分赛题严格按比赛时间做不看任何提示。模拟的目的不是分数是练时间分配——哪道题该先做、卡到什么程度该跳、最后二十分钟该检查什么。这一场我 A 题花了 22 分钟其实可以压到 10 分钟多出来的时间够我把 C 题的判定函数重写两遍了。6. 常见问题速查与个人避坑清单6.1 补题过程中反复出现的问题速查下面这些是我在这次补题里真实踩过、以及在后来的训练里被反复验证过的问题整理成表方便随时翻现象大概率原因处理方式样例过了交上去 WA边界没覆盖n1 或全负数的数据没测手动补造极端数据至少测三组本地过线上 TLE编译优化等级不同、常数太大本地加-O2检查是否有隐藏的 O(n) 操作二分死循环循环条件写成lo hi但更新没移动边界改用lo 1 hi的写法BFS 跑得异常慢状态没去重或入队时没标记入队时立刻标记不要等出队输出答案偏小中间结果溢出、用了 int求和、乘积、差值统一用 long long递归程序崩溃递归深度超过栈限制改成迭代或者把递归改成显式栈6.2 几条我自己踩出来的经验第一条读题的时候把数据范围圈出来。我以前觉得这一步多余直到 C 题因为没看范围把 cnt 写成 int 溢出了。现在我的习惯是读题时直接拿笔在范围下面划线写代码之前先确认一遍每个变量的类型够不够。第二条别在赛时现写复杂结构。这次 B 题我本来想用树状数组结果赛时手写树状数组写错了 lowbit反而耽误时间。后来反思B 题根本不需要树状数组差分就够了。能用简单工具解决的就别上复杂工具这句话现在被我贴在显示器边上。第三条提交之前先跑一遍最极端的数据。比如 n1、全部相等、全部为负、全是边界值。这三四组数据加起来花不了一分钟但能拦住很大一部分 WA。我这场 B 题的第二次 WA 就是因为没测 n1。第四条卡题超过 25 分钟就跳。这一场我在 C 题上耗了将近五十分钟最后没交上去而 D 题其实只要多想十分钟就能意识到状态维度的问题。时间分配的错误比单道题不会做要严重得多因为它是一连串的连锁反应。第五条补题补的是思路不是代码。我见过不少人补题就是照着题解把代码抄一遍然后提交看到 AC 就结束了。这样补十道和一道没补是一样的。真正的补法是看完思路之后关掉题解自己从空白文件写起写不出来再回去看反复几次直到能独立写出来。这个过程的痛苦程度基本就等于你真正学到的东西的多少。补完这一场之后我把六道题重新过了一遍其中三道重写了代码两道重新整理了模板一道先挂着等把贪心专题过完再说。下一场积分赛之前我打算先把这套题里的 DP 和搜索再各找五道同类题练手看看状态定义和去重这两件事是不是真的变成条件反射了。这套流程跑下来虽然慢但每道题的收获都落到了实处比盲目刷题踏实得多。