寒假积分赛一这场打完我盯着屏幕上的排名愣了一会儿五道题里两道签到级别的题我各挂了三次罚时直接把我从中游压到了下游一道 BFS 我把方向数组的dy写成了dx样例过了提交就 WA还有两道题我连题目想问什么都没读明白。这种感觉打过训练赛的人都懂就是那种题不难但我就是没做出来的憋屈。第二天早上八点我坐下来开始补题一直补到第三天晚上才把这五道题全部拿下顺便把两处知识盲区补上了。补题这件事从来不是把题解抄一遍这么简单它是把一场比赛暴露出来的所有漏洞一条一条缝回自己的知识树里。下面这份记录我会把这场积分赛的赛制逻辑、题单分层方法、A 到 G 七道题的真实思路和代码、以及那几天踩过的坑按我复盘的顺序完整拆开讲。适合刚学完语法、想进算法竞赛门的新手也适合已经打过几场、卡在会做但过不了这个阶段的同学。1. 积分赛补题的底层逻辑为什么补比打更重要我第一次参加积分赛的时候想法特别朴素打就完了打完看排名。结果连打三场排名没什么变化因为每场我犯的错都是同一批——读入没处理好、数组开小、边界没判、复杂度算错。真正让我水平往上走的是第四场之后开始认真补题那段时间。所以这一节我想先把为什么要补这件事说透不然补题很容易变成机械抄题解。1.1 积分赛制和普通训练赛到底差在哪积分赛和普通训练赛最大的区别在计分方式。普通训练赛往往只看通过题数积分赛则通常按题号给固定分值或者按通过人数动态给分——越少人过的题分值越高再加上每次错误提交 20 分钟罚时。这套规则会直接改变你的比赛策略。我这场一的分值分布大概是这样的题号考察方向分值场上通过人数我的结果A签到、输入输出100全场几乎全过AC罚时 3 次B贪心、排序200约七成AC罚时 1 次C前缀和、二分300约四成场上来不及DBFS、网格图300约三成WA 两次后放弃E线性 DP、背包400约两成没思路F并查集400约一成半没思路G数论、筛法500个位数没读题这张表是我赛后从榜单上抄下来的它说明一件很重要的事分值和通过人数高度相关而通过人数又和知识点难度高度相关。A 到 C 加起来 600 分全是基础题D 到 G 加起来 1600 分全是进阶题。而我在基础题上因为罚时丢了大概 80 分钟等于说我把本该用来啃 C 题的时间全还给 A 题了。提示赛后抄一份分值 通过人数 我的结果的表比只记我过了几题有用十倍。它能直接告诉你你丢的分是丢在能力上还是丢在纪律上。1.2 补题的三问知识、思路、还是代码补题时我最怕的就是看一遍题解哦原来是这样然后关掉。这种补法一周后就忘干净了。我后来固定用三个问题来分类第一问是知识点不会吗比如 E 题我看到背包两个字就知道要 DP但我当时根本没系统学过 01 背包的状态定义这属于知识空白必须去找资料系统补。第二问是知识点会但想不到吗C 题我会前缀和也会二分但我场上没把正整数数组的前缀和单调递增这个性质和最短子段联系起来。这属于思路缺失补法是归类加模板化。第三问是思路对但写挂了吗A 题和 D 题都属于这一类。A 题我思路完全没错就是多组数据的结束条件写错D 题我思路也对方向数组写反了。这属于工程能力问题补法是练调试、练对拍。这三种问题的补法完全不同。知识空白要花两三小时系统学思路缺失要花二十分钟整理成一句话并背下来代码写挂要花半小时写对拍脚本。把这三类混在一起补就是我前三场原地踏步的原因。1.3 我给自己定的补题优先级有个反直觉的结论先补黄色题最后补红色题。黄色题指的是场上有思路但没出的题红色题是完全没思路的题。很多人喜欢从最难的开始补觉得收获大结果两小时过去还在看题解挫败感拉满第二天就不想补了。我这场黄色题有两道C 和 D红色题三道E、F、G。我的实际安排是第一天把 C、D 补完顺便重写一遍 A、B 确认自己真的会第二天补 E 和 F 的知识点晚上做 G第三天默写所有代码。这个节奏下来每天都有我搞定了的正反馈比死磕一道 500 分题舒服得多。2. 赛前赛后的准备动作环境、题单与分层补题能不能高效很多时候不取决于你聪不聪明而取决于你的环境和流程有没有搭好。我见过太多人补题时把时间花在编译器又报奇怪的错不知道哪个版本的 C 支持这个语法上真正思考算法的时间反而不到一半。这一节说说我的准备动作。2.1 本地环境三行命令打天下我的本地环境很简单就是一个终端加一个编辑器不依赖任何复杂配置。编译命令固定成这一条g -stdc17 -O2 -Wall -Wextra -Wshadow a.cpp -o a ./a这里面每个参数都有用。-stdc17 是因为我习惯用结构化绑定和auto [x, y]很多竞赛环境已经支持-O2 是模拟评测机的优化级别能提前暴露一些因为没优化而超时的写法-Wall -Wextra -Wshadow 是把警告全打开尤其是 -Wshadow变量遮蔽它能抓到局部变量把全局变量盖住这种极其隐蔽的 bug我在 D 题上就吃过这个亏后面的 ./a是省一次回车看着小一天能省几十次操作。代码模板我固定成下面这样比赛和补题都用同一份#include bits/stdc.h using namespace std; int main() { // ios::sync_with_stdio(false); // cin.tie(nullptr); int T; if (scanf(%d, T) ! 1) return 0; while (T--) { // solve } return 0; }注意bits/stdc.h是 GCC 特有的标准 C 里没有这个头文件。如果你本地是 Clang 或者 MSVC编译会直接失败。我本地是 GCC比赛环境也是 GCC所以用得很放心但你要是换环境老老实实把iostreamvectoralgorithm这些写上。2.2 三色标记法把题单切成三块补题前我会先把题单摊开用三种颜色标一遍。这个方法是从别人那里学来的但用久了我发现它的真正价值在于强迫你承认自己哪些题是真不会。颜色判断标准补题动作时间预算绿色场上一次 AC赛后重写一遍不看旧代码15 分钟黄色有思路WA/TLE 或没写完先自己调调不出看题解再默写1 小时红色完全没思路或读不懂题限时 1.5 小时超时看题解隔天默写2 小时对绿色题我的要求是重写一遍而不是看一眼。原因是场上一次 AC 很有可能只是运气好数据弱、边界没测到。重写一遍时我会故意把边界条件都试一遍比如 n1、n0、全相同元素、最大值数据能过才算真的会。红色题的限时 1.5 小时这条规矩我执行得很死。早期我总觉得再想十分钟就出来了结果一道题卡一整个下午题解也没心情看了。后来发现限时到了就看题解然后关掉题解自己重写一遍学习效率比干耗高三倍以上。2.3 复盘记录一行字救回一道题我的复盘记录是这么写的一段一条绝不写废话D题 | 考察BFS网格最短路 | 卡点方向数组 dy 写成了 dx样例只有一格所以没暴露 关键结论dx/dy 成对出现写完立刻打印一次四个方向的目标坐标 复用模板grid_bfs.cpp关键是关键结论这一行。它必须是一句可以直接执行的、下次能救命的话而不是要注意方向数组这种空话。我现在的记录本里全是这种句子比如二分查找左闭右开时hi mid而不是hi mid - 1多组数据的 vis 数组必须在每组开头清空别偷懒用 memset 整个数组。3. 前半段题目拆解签到、贪心、前缀和A、B、C 这三道题是整场的分水岭。A、B 属于必须拿满分的题C 是努力一下能拿的题。我这场就是 A、B 拿了但罚时太重C 没时间做。下面逐题拆。3.1 A 题签到真正的考点是输入输出A 题的题意很朴素多组数据每组第一行一个整数 n第二行 n 个整数输出这组数里最大值和最小值的差。看完题我第一反应是这也太水了然后自信满满提交WA。改了一次WA。第三次还是 WA。三次罚时 60 分钟就这么没了。问题出在两个地方。第一多组数据没有给组数需要读到文件结束我下意识用了for (int i 0; i T; i)T 读出来是 0循环一次都没进。第二n1 时最大值和最小值是同一个数差为 0这个没问题但如果数据范围到了 10 的 9 次方级别n 个数的和虽然用不到但差值还在 int 范围内我保险起见开了 long long。正确的写法是这样#include bits/stdc.h using namespace std; int main() { int n; while (scanf(%d, n) 1) { // 读到 EOF 就停 long long x, mx LLONG_MIN, mn LLONG_MAX; for (int i 0; i n; i) { scanf(%lld, x); if (x mx) mx x; if (x mn) mn x; } printf(%lld\n, mx - mn); } return 0; }while (scanf(...) 1)这个写法比while (~scanf(...))更保险因为返回值是成功读入的变量个数语义清晰。用cin n的话写法是while (cin n)也能自动处理 EOF但一定要关掉同步ios::sync_with_stdio(false)否则大数据量会慢。实操心得签到题的罚时几乎全部来自多组数据的输入格式和边界数据这两件事。赛后我把多组数据三种结束条件整理成了一张小便签贴在显示器边上读到 EOF、给定组数 T、读到 0 0 结束。贴上去之后我再没在签到题上挂过。3.2 B 题贪心为什么按结束时间排序一定选得最多B 题是经典的区间调度给 n 个活动的开始和结束时间问最多能参加几个活动。我场上知道是贪心但排序关键字犹豫了一下最后凭直觉按开始时间排结果只过了部分数据。正确的贪心策略是按结束时间从小到大排序然后依次扫描能接上就选。为什么这样对我用自己的话解释一遍这也正是补题时应该想清楚的地方。假设最优解选了 k 个活动其中第一个是 X而贪心选的是结束最早的 Y。因为 Y 的结束时间不晚于 X所以把 X 换成 Y 之后剩下的活动仍然都能接上解的大小不会变差。这样一步步替换下去贪心解一定不劣于最优解。这个论证方式叫交换论证是贪心题最常用的证明套路值得记下来。按开始时间排序为什么错举个反例就够了活动一是 [1, 100]活动二是 [2, 3]活动三是 [4, 5]。按开始时间排第一个选 [1, 100]后面全接不上答案是 1正确答案是 2。代码#include bits/stdc.h using namespace std; struct Node { int l, r; }; int main() { int n; scanf(%d, n); vectorNode a(n); for (int i 0; i n; i) scanf(%d%d, a[i].l, a[i].r); sort(a.begin(), a.end(), [](const Node x, const Node y) { if (x.r ! y.r) return x.r y.r; // 结束时间优先 return x.l y.l; // 结束时间相同时开始早的优先 }); int cnt 0, last INT_MIN; for (const auto e : a) { if (e.l last) { // 端点相接算不算冲突看题目要求 cnt; last e.r; } } printf(%d\n, cnt); return 0; }这里有个坑我必须说e.l last还是e.l last完全取决于题目对时间点相接的定义。有的题说一个活动结束的瞬间另一个可以开始那就用有的题说必须间隔,那就要加上间隔。我这场是前一种但我在心里过了一遍才敢下笔。3.3 C 题前缀和加二分把平方复杂度压到线性对数C 题是我场上没做完但赛后半小时就补出来的一道。题意是给一个长度为 n 的正整数数组和一个整数 S求和不小于S 的最短连续子段的长度不存在输出 0。n 到了十万级别。看到连续子段的和第一反应是前缀和令pre[i] a[1] a[2] ... a[i]那么子段 [i, j] 的和就是pre[j] - pre[i-1]。如果直接双重循环枚举 i 和 j复杂度是 O(n²)十万的数据量铁定超时。关键性质在这里数组全是正整数所以前缀和是严格单调递增的。这意味着一件事——固定左端点 i随着右端点 j 增大子段和只会变大。那么最小的 j 使得子段和 ≥ S就可以二分查找了。整体复杂度 O(n log n)稳稳过。#include bits/stdc.h using namespace std; int main() { int n; long long S; scanf(%d%lld, n, S); vectorlong long pre(n 1, 0); for (int i 1; i n; i) { long long x; scanf(%lld, x); pre[i] pre[i - 1] x; } int ans n 1; for (int i 1; i n; i) { int lo i, hi n, pos -1; while (lo hi) { int mid lo (hi - lo) / 2; if (pre[mid] - pre[i - 1] S) { pos mid; hi mid - 1; } else lo mid 1; } if (pos ! -1) ans min(ans, pos - i 1); } printf(%d\n, ans n 1 ? 0 : ans); return 0; }提示mid lo (hi - lo) / 2这种写法比(lo hi) / 2安全因为当 lo 和 hi 都接近 int 上限时lo hi会溢出变成负数然后就是死循环或者数组越界。这个细节我在一次 RE 之后才真正记住。其实这题还有更优的写法因为左右端点都只会往右移用**双指针尺取法**可以做到 O(n)。思路是右指针一直往右扩当子段和 ≥ S 时更新答案然后右移左指针缩小子段直到和小于 S 再继续扩右指针。两种写法我都默写过一遍对比起来方案时间复杂度适用条件代码难度前缀和 二分O(n log n)要求前缀和单调元素全正中双指针尺取O(n)同样要求单调性中偏高边界容易错我场上的话会先写二分因为二分更套路化不容易写挂时间充裕再优化成尺取。这种先拿分再优化的顺序在积分赛里尤其重要。4. 中段题目拆解搜索与动态规划D 和 E 是这场从中游往上走的分界线。D 题是搜索思路直观但细节多E 题是 DP思路本身就是门槛。这两道我花了整整一天。4.1 D 题 BFS一个方向数组写错样例就能过D 题是 n 乘 m 的网格0表示能走1表示障碍问从左上角走到右下角的最少步数走不到输出 -1。典型的无权图最短路直接 BFS。我场上写了大概十分钟样例一次过提交 WA。改了一版还是 WA。当时以为是 vis 标记的问题折腾到比赛结束都没看出来。赛后补题时我把代码打印出来逐行对照才发现方向数组写成了这样int dx[4] {-1, 1, 0, 0}; int dy[4] {-1, 1, 0, 0}; // 错误应该是 {0, 0, -1, 1}后果是 BFS 只能沿着对角线方向走上下左右四个方向全废了。样例恰好是个只有一格的网格起点就是终点所以直接输出 0什么问题都看不出来。这就是为什么我现在的记录本上写着样例太小的题必须自己造一组三乘三以上的数据。正确代码#include bits/stdc.h using namespace std; int main() { int n, m; scanf(%d%d, n, m); vectorstring g(n); for (int i 0; i n; i) cin g[i]; if (g[0][0] 1) { puts(-1); return 0; } vectorvectorint dist(n, vectorint(m, -1)); queuepairint,int q; dist[0][0] 0; q.push({0, 0}); int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int k 0; k 4; k) { int nx x dx[k], ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] 1 || dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } printf(%d\n, dist[n - 1][m - 1]); return 0; }这段代码里有三个值得单独拎出来的细节。第一入队时就标记 dist而不是出队时标记。如果在出队时才标记访问同一个格子可能被多次入队队列会膨胀到不能接受的程度时间复杂度从 O(nm) 退化。这一点很多人踩过。第二dist 数组直接兼任 vis 数组初始化为 -1既能表示没访问过又能顺带存距离省一个数组。这是我从模板里固定下来的写法。第三BFS 求出的最短路只在边权全为 1 时成立。如果题目里有传送门这种一步顶三步的设定BFS 就不成立了得换 Dijkstra 或者 0-1 BFS。这个边界意识很重要我在后来的题目里吃过亏。4.2 E 题 DP状态定义比转移方程值钱得多E 题是 01 背包的裸题n 个物品每个有重量和价值背包容量 V每个物品最多拿一次求最大价值。我场上看到就懵了因为我连状态是什么都没概念。补题时我看完资料最大的收获不是那行转移方程而是为什么状态要这么定义。我们定义dp[j]表示容量为 j 的背包能装下的最大价值。这个定义里藏着一个取舍我们只关心容量不关心具体装了哪些物品因为物品的价值只和总重量有关和装了谁无关。如果题目要求输出具体选了哪些物品这个状态就不够了得开两维甚至记录方案。有了状态转移就好推了对第 i 个物品要么不拿dp[j]不变要么拿dp[j] dp[j - w] v。取两者较大值。#include bits/stdc.h using namespace std; int main() { int n, V; scanf(%d%d, n, V); vectorint dp(V 1, 0); for (int i 0; i n; i) { int w, v; scanf(%d%d, w, v); for (int j V; j w; --j) // 关键倒序枚举 dp[j] max(dp[j], dp[j - w] v); } printf(%d\n, dp[V]); return 0; }注意事项一维写法里 j 必须从大到小枚举这不是习惯问题是正确性问题。因为dp[j]依赖的是上一轮还没考虑当前物品的 dp[j - w]。如果 j 从小到大枚举dp[j - w]已经被本轮更新过了等于当前物品被拿了两次答案就变成完全背包了。我为了记住这一点专门写过一个错误版本跑数据看着它输出一个大得离谱的数字从此再没写错过。二维写法的思路更直观dp[i][j]表示前 i 个物品、容量 j 的最大价值转移时从 i-1 层拿数据不存在覆盖问题for (int i 1; i n; i) for (int j 0; j V; j) { dp[i][j] dp[i - 1][j]; if (j w[i]) dp[i][j] max(dp[i][j], dp[i - 1][j - w[i]] v[i]); }我建议新手先写二维版本写熟之后再压缩成一维理解成本会低很多。5. 后半段题目拆解并查集与数论F 和 G 是这场分值最高的两道题。F 题的通过人数有一成半说明它是有套路就能做的题G 题只有个位数通过属于真正的分水岭。5.1 F 题并查集路径压缩和按秩合并F 题是这样n 个人给 m 对认识关系认识具有传递性——A 认识 BB 认识 C那么 A 和 C 也算在一个圈子里。问一共有几个互不相通的圈子以及某些人是否在同一个圈子里。这就是并查集的典型应用。并查集的思路其实特别生活化每个人都有个组长如果两个人的组长是同一个人他们就在一个组。合并两个组的时候让一个组长认另一个组长当上级。最怕的是形成一条长链比如 1 的上级是 22 的上级是 3一直排到 n那查一次要找 n 步。两个优化解决这个问题。路径压缩查询的时候顺手把路上所有节点的上级直接改到根节点上下次再查就是一步。按秩合并合并时把节点少的树挂到节点多的树上防止树长歪。两个优化一起用单次操作的均摊复杂度接近常数可以当成 O(1) 看。struct DSU { vectorint fa, sz; DSU(int n) : fa(n 1), sz(n 1, 1) { iota(fa.begin(), fa.end(), 0); } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); // 路径压缩 } void unite(int a, int b) { a find(a); b find(b); if (a b) return; if (sz[a] sz[b]) swap(a, b); // 小的挂到大的下面 fa[b] a; sz[a] sz[b]; } };统计圈子个数很简单把所有节点遍历一遍find(i) i的节点就是一棵树的根根的个数就是圈子数。int cnt 0; for (int i 1; i n; i) if (find(i) i) cnt; printf(%d\n, cnt);实操心得并查集有一个很隐蔽的坑——初始化必须把每个节点的父节点设成自己同时 size 设成 1。我见过有人只写了fa[i] i却忘了 size按秩合并时把空树挂上去很快就会出现某个节点的 size 是 0导致合并方向全错。另外路径压缩和按秩合并其实只用一个也能保证效率但两个一起用真的能省不少时间。5.2 G 题数论线性筛和质因数分解G 题我场上压根没读赛后看完发现是两个小问拼起来的第一问给定上界 n求 n 以内的质数个数第二问给一个数输出它的质因数分解形式。第一问 n 到了 10 的 7 次方第二问的数到了 10 的 12 次方。第一问的关键在于筛法。最朴素的埃氏筛复杂度是 O(n log log n)10 的 7 次方大概能过但比较勉强。更稳的是线性筛欧拉筛每个合数只被它最小的质因子筛掉一次复杂度严格 O(n)。const int MAXN 1e7 5; vectorint primes; bool notp[MAXN]; void sieve(int n) { for (int i 2; i n; i) { if (!notp[i]) primes.push_back(i); for (int p : primes) { if (1LL * i * p n) break; // 防止溢出用 long long 比较 notp[i * p] true; if (i % p 0) break; // 保证每个合数只被最小质因子筛一次 } } }这行if (i % p 0) break;是线性筛的灵魂。它的意思是当 p 已经能整除 i 时说明 p 是 i 的最小质因子那么 i 乘上更大的质数得到的合数一定已经被更小的质因子筛过了没必要再筛。我第一遍看的时候不理解手动画了 n20 的过程才算清楚。1LL * i * p n这个写法也要注意i 和 p 都是 int乘起来可能溢出加个1LL *强制转成 long long 再比较能避免 10 的 7 次方附近出问题。第二问的分解用试除法就够vectorpairlong long,int factor(long long n) { vectorpairlong long,int res; for (long long p 2; p * p n; p) { if (n % p) continue; int c 0; while (n % p 0) { n / p; c; } res.push_back({p, c}); } if (n 1) res.push_back({n, 1}); // 剩下的大质因子 return res; }复杂度是 O(根号 n)对一个 10 的 12 次方的数来说循环最多跑到 10 的 6 次方次完全够用。注意循环条件p * p n里的 n 是在变化的这正好能把复杂度再压下去一点。还有最后那个if (n 1)千万别漏否则像 2 乘一个大质数这样的输入会少输出一个因子。提示p * p n在 p 接近 long long 上限时会溢出。虽然这题用不到但写法上更稳的是p n / p。我在整理模板时把这条统一改了。6. 常见问题与排查技巧实录补题那三天我在调试上花的时间大概占了四成。这一节把当时遇到的错误和后来的排查方法整理出来这部分内容在题解里基本看不到但实战价值最高。6.1 错误类型定位顺序从 RE 到 WA评测结果就那么几种但每种背后指向的问题范围差别很大。我的排查顺序是这样的结果常见原因第一件事做什么RE数组越界、除零、栈溢出、空指针把数组开大 10 倍试试再检查递归深度TLE复杂度估错、常数太大、死循环打印循环次数确认是否真的进了死循环WA边界没判、溢出、题意理解错造小数据对拍看第一个错在哪MLE数组开太大、递归爆栈把不需要 long long 的改成 intPE行末空格、最后一行换行逐字节对比输出格式RE 我踩过最经典的一次是数组开小了。题目说 n 最大 10 的 5 次方我开了 100005看着够。但题目是多组数据且没给组数我为了省事把数组开在全局只清空一次——结果是累积的后面几组直接越界。数组开在全局时多组数据必须每次重新初始化这是硬规矩。TLE 最常见的不是算法错而是复杂度估错。比如我看到n 个数每次查询区间和就写了个双重循环n 是 10 的 5 次方、查询 10 的 5 次方那就是 10 的 10 次方次运算铁定超时。这种情况必须上前缀和或者树状数组。养成习惯写完代码先在心里算一遍最坏情况的运算次数超过 10 的 8 次方就要警惕。WA 的排查我觉得对拍是最有效的。下一节说。6.2 对拍让程序自己找自己的错对拍的核心思路是写一个肯定正确但很慢的暴力程序写一个随机数据生成器然后跑几百组数据比对我的程序和暴力程序的输出。这招在 D 题上救了我——我造了 100 组 5 乘 5 的随机网格第 3 组就挂了一下子定位到方向数组。三个文件一个脚本// gen.cpp 生成随机数据 #include bits/stdc.h using namespace std; int main() { srand(time(0) ^ (unsigned long long)(new char)); int T 20; printf(%d\n, T); while (T--) { mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n rng() % 5 1, m rng() % 5 1; printf(%d %d\n, n, m); for (int i 0; i n; i) { for (int j 0; j m; j) putchar(rng() % 3 0 ? 1 : 0); putchar(\n); } } return 0; }脚本#!/bin/bash g gen.cpp -O2 -o gen g std.cpp -O2 -o std # 暴力程序 g my.cpp -O2 -o my # 我的程序 for ((i 1; i 500; i)); do ./gen in.txt ./std in.txt out1.txt ./my in.txt out2.txt if ! diff -q out1.txt out2.txt /dev/null; then echo 第 $i 组数据 WA cat in.txt break fi done注意事项生成器的随机范围一定要覆盖边界。我一开始只随机生成了 3 乘 3 的网格跑了两百组全过还以为程序没问题了把范围改成 1 到 5 之后立刻暴露出起始点就是障碍的情况没处理。随机数据的价值不在于多而在于能碰上边界。6.3 高频踩坑速查表下面这张表是我从这场和之前几场比赛中攒下来的基本每次补题都会翻一遍症状最可能的原因处理办法样例过提交 WA样例太小边界没覆盖自己造 n1、全相同、最大值数据多组数据第一组对后面全错全局数组没清空每组开头重置别偷懒 memset 整个数组答案偶尔偏小int 溢出涉及乘法和求和一律 long long大数据超时小数据正常复杂度不够或输入输出慢换算法或关同步 / 用 scanf死循环二分边界写错或循环变量没更新打印循环变量看是否卡在同一个值答案差 1区间开闭、下标从 0 还是 1 开始统一成下标从 1 开始、区间左闭右闭浮点数比较失败精度误差改成整数运算或用 eps 比较这个表里我最想强调的是答案差 1这一类。它几乎全部来自下标约定不统一。我后来强制自己所有涉及区间、前缀和的代码数组下标一律从 1 开始区间一律左闭右闭前缀和数组开 n1。统一之后这类错误基本绝迹。7. 补题之后模板沉淀与下一场目标补完题不等于结束。我见过太多人补完就把代码扔了下次遇到同类型的题从零开始。真正拉开差距的是补题之后的动作——把这道题抽象成一个可复用的模块再给自己定一个可量化的下一场目标。7.1 模板整理的正确姿势我的模板目录是按知识点分的每个文件里放一个可独立编译的小程序关键是在文件顶部加一段注释写清楚三件事适用条件、复杂度、以及什么时候不要用它。第三个尤其重要。比如我的binary_search_shortest_segment.cpp文件里写着适用正整数数组求和不小于 S 的最短连续子段 复杂度O(n log n) 不要用数组含负数时前缀和不单调二分失效必须换单调队列或双指针失效后重推再比如grid_bfs.cpp适用无权网格图最短路四方向或八方向 复杂度O(nm) 不要用边权不为 1或有权重转移时需要 0-1 BFS 或 Dijkstra这样写的价值在于下次遇到新题时我能快速判断这题能不能套模板而不是先套上去再说。前者是效率后者是灾难。另外每个模板我都要求自己默写过一遍。不是复制粘贴是关掉所有参考、从空文件开始敲。默写的时候暴露的问题最多比如我总忘iota的头文件、总把while (lo hi)写成while (lo hi)。这些问题在默写时暴露一次赛场上就能少挂一次。7.2 下一场的可量化目标补完这场之后我给自己下一场定的目标是这样三条第一条签到题100 到 200 分必须一次过罚时为 0。这条是纪律不是能力只要输入输出模板背熟、边界自己造一组数据测过就能做到。第二条中等题300 分档至少拿下一道。这场 C 题没时间做是因为我在 A 题上浪费了 60 分钟。把签到题的罚时压下来中等题的时间自然就有了。第三条比赛结束后 48 小时内必须把黄色题全部补完。我给这条定了执行细节赛后当晚只做一件事把题单按三色标好写下每道题的卡点第二天花两小时补黄色题第三天补红色题超时看题解看完默写。实操心得目标一定要能被打勾。我早期给自己定过下次打得更好这种目标结果毫无约束力。换成签到题零罚时之后我在比赛时会主动在提交前多测一组边界数据这个动作看起来只花二十秒但它救回来的可能是整整一小时。后来那场积分赛二我签到题零罚时C 题在剩余 70 分钟时拿下最终排名比这场往前了二十多位。真正起作用的就是这几条看起来特别琐碎的规矩。8. 我从这场补题里学到的最实在的东西如果只能留下一句话我会留这句比赛暴露的是症状补题才是在治根。A 题挂三次不是运气差是输入输出模板没背熟D 题方向数组写错不是粗心是没养成写完立刻打印验证的习惯E 题没思路不是脑子笨是知识点压根没学过。这三种问题的解法完全不同但它们的共同点是——只要你不去补下一场还会原样出现。我现在补题的流程已经固定下来了抄一张分值通过人数表三色标记题单先补黄色再补红色每道题写下关键结论那一行红色题限时 1.5 小时补完默写模板。这套流程不新鲜但执行下来是真的管用。另一个我觉得被低估的动作是造数据。很多人补题时只在样例上跑一遍就心安了但样例往往小得可怜——D 题那组起点即终点的样例就是最好的反例。宁可多花五分钟手写一组三乘三以上的数据也不要在提交之后盯着 WA 发呆。最后分享一个小技巧是我在补 E 题时摸索出来的当你看不懂一道 DP 题的状态定义时先把二维版本写出来把dp[i][j]的表格手工填前几行看着数字找规律你往往能自己重新发现那个状态定义。这比盯着题解硬啃快得多而且理解得牢。至于后续还能怎么扩展——我打算把筛法、并查集、最短路这几个模板再各自写一道变式题的题解特别是带权并查集和 0-1 BFS这两块目前还是我的薄弱环节下一场大概率还会考到。