2020ICPC南京站结束之后我先把整场比赛在脑子里过了一遍第二天就开始补题。这篇内容既是一次赛后总结也是一份补题笔记。先说背景我们队三个人水平在整个区域赛队伍里算中游偏上网络赛幸运拿到了名额南京站给自己定的目标是摸到银牌最后的结果只差临门一脚。赛后复盘问题主要出在读题速度和一道构造题的判断上。如果你也在准备区域赛或者正准备打自己的第一场ICPC这篇里的现场决策过程和补题方法应该能给你一些参考。1. 赛前准备与赛场上的第一印象1.1 从网络赛到线下赛的状态切换拿到名额之后说实话有一个星期是有点飘的。日常训练以专题为主临近比赛才改成整场模拟。这里有个很实在的建议距离比赛还有一周时晚上不要再死磕新算法应该固定两到三场完整模拟严格按区域赛时间从中午打到下午中场不休息。我们队当时练了四场前三场都在中段时间出现明显断档要么是75分钟之后手速变慢要么是卡题之后焦虑传染到全队第四场才把节奏理顺。真正到了南京站的赛场这种模拟带来的收益比多刷几十道题更大至少你清楚自己在哪个时间点容易出错也能提前安排换题和讨论信号。另一个赛前容易忽略的点是键盘和打印机的节奏。我们平时训练基本不打印代码但区域赛现场打印罚时其实很值得用。南京站前半段我们为了省打印时间连续两道题都在屏幕上肉眼查错结果越查越乱。后来补题复盘时队友专门统计了一下如果卡住超过十分钟就把代码打出来看整体冷静速度会快不少。这可能有点因人而异但建议赛前模拟时把打印流程也加进去不要到了现场才第一次用。1.2 开局一小时签到题没有想象中好签比赛开始后我们按常规分工三人同时读题A题由我来写。题目本身并不难是一个和取模、计数相关的题但现场还是花了接近四十分钟才过。回头看问题出在负数和重复元素两个地方。题面里的整数范围没有保证非负我第一次写直接把元素取模塞进桶里结果负数样例直接让我发懵。后来改成先做 ((x % m) m) % m才把余数统一到 [0, m) 区间。这个四十分钟直接决定了整场的罚时基调。等我们过A的时候榜上已经有几十个队伍过了B或者C我们的罚时一下就落后了。现在反思签到题的坑往往不是在算法上而在细节上数据范围、负数、重复元素、多组数据、输出格式。以后开场前十分钟不急着写代码先把这些边界在草稿纸上列出来比反复提交试错舒服得多。1.3 中期排名与题目分布判断到比赛进行到大约一个半小时我们队才过完第一题排名已经很靠后。此时看榜发现B题的提交数很多、通过率也还行C题只有零星几支队伍在交D题更是几乎没人碰。这里有一个我一直很相信的判断标准如果一道题提交数多而且通过曲线在涨说明它确实是“能写但需要动脑”的题应该优先投入如果提交数很少而且通过的队伍都是榜上最前面那批说明这题要么是硬件题要么是思维量极大的构造题中后期队伍暂时别碰。我们当时判断C是那种“看着能做、实际上很容易把自己绕晕”的构造题于是决定先放一放全队去冲B。这个决定本身没有错但执行时出了问题我们三个人对B题的理解花了太多时间互相确认期间大家都想说话反而拖慢了写代码的进度。现在总结出来的经验是三个人一起看题时最好指定一个人复述题面另外两个人只负责找反例不要三个人同时表达自己的理解否则信息会变得很碎。2. 比赛现场的关键决策复盘2.1 换题比死磕更重要但也要有依据南京站这场我踩过最大的坑就是A题卡住时没有及时换人。当时我已经带着错误思路写了十几分钟队友也觉得“马上就能改对”结果越改越偏。后来我们定了一条队规任何一道题连续讨论超过二十分钟没有形成可写的方案就强制换题或换人重新读。这条规则看起来很简单但在高压下真正做到很难。换题也讲究依据。不是一卡就换而是先判断当前题的通过情况。如果榜上大量队伍已经过了这道题说明思路大概率是通的问题出在某个人身上应该换个队友重读而不是换题如果榜上通过的队伍很少而且我们当前想法明显绕了很久那大概率是方向错了换题才是正解。B题当时属于前者我们换了一个人重读之后很快就找到了正确的建模方向最终顺利AC。2.2 三读之后再动手省下来的都是罚时读题错误是区域赛最亏的失误比不会做还亏。南京站有一道题我第一遍读成了“求满足条件的子序列数量”实际题目要求的是“连续子数组”。一字之差复杂度从O(n)变成了O(2^n)我当时还自信地写了个DFS交上去必然是TLE。最后是队友看样例才拦住我重新读题之后才发现是个简单前缀和。从那以后我们队形成了一套“三读法”第一遍通读只求知道题目在讲什么第二遍看数据范围猜测出题人想考什么算法第三遍确认输入格式、输出格式和取模要求。三遍读题加起来不超过两分钟但能避免半小时的无效代码。尤其是补题阶段我的第一习惯永远是先把题面翻译成一句话写在这一题的题解模板里翻译不出来的题先不碰。2.3 一次错误的复杂度估计这场的D题涉及数据规模在1e6左右的问题我当时第一反应是枚举每个数的因子写一个O(n sqrt(n))的预处理。现场估算的时候我把1e6乘以1000当成了1e7还觉得稳得不行结果代码跑起来才发现时间完全不够。最后这题没能提交赛后补题时改成线性筛几分钟就跑完了。这里想多说一句复杂度估算的事。O(n sqrt(n))在n1e6时大约是1e9次运算而区域赛的时限通常只有2到3秒C也扛不住。类似的错误还有把O(n log n)想成O(n)或者忽略了多组数据会乘上一个case数量。现在补题时我每写完一个算法都会在注释里写一行复杂度估计并且标明最坏数据规模下大概多少次运算超过5e7就默认不安全除非题目时限特别宽松。2.4 最后四十分钟的心态波动临近结束时的表现往往最能反映一个队的真实训练水平。我们队当时剩下一道构造题和一个数学题两个都没有完整思路于是又回到了“哪个都想碰”的状态。最后的四十分钟里我们平均每十分钟切换一次思路代码写了又删删了又写最终一道都没交上去。这个经验特别想说给第一次打区域赛的队伍听最后阶段如果一道题彻底没思路不要去碰第二道更不要两个人同时写不同的题。正确做法是挑一道最可能有进展的题三个人一起找性质和规律。就算最后没有AC也能把完整思路带到补题里对赛后的提升帮助很大。我们那场就是没做到这一点赛后复盘时才发现那道构造题其实已经摸到了正确的门只差临门一脚。3. 补题全记录五道题的五种算法模型补题是区域赛结束后最有价值的部分。我一般不会按题目难度排序去补而是按“当时离AC有多近”排序。下面这几题都是南京站留给我的典型模型每题按题意、思路、坑点来记录。3.1 A题补题余数桶计数注意取模顺序A题题意可以抽象成给定n个整数和一个模数m问有多少对(i, j)满足 i j 且 (a[i] a[j]) % m k。n最大2e5m可以很大直接枚举所有数对是O(n^2)显然不行。补题的标准做法是用桶记录余数出现次数边扫边统计。核心代码如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin n m k; unordered_mapint, long long cnt; long long ans 0; for (int i 0; i n; i) { int x; cin x; int r (x % m m) % m; // 统一到非负余数 int need (k - r m) % m; ans cnt[need]; // 先统计之前出现的 cnt[r]; // 再插入当前数 } cout ans \n; return 0; }这里最关键的细节就是“先查桶再插自己”。如果先插入再查询会把 i 和 j 相等的情况也算进去非常隐蔽。另一个容易错的地方是负数取模C里负数取模结果仍是负数直接拿去做哈希会出问题必须先加m再模m。m很大的时候不能开普通数组用 unordered_map 即可复杂度仍然是O(n)期望。3.2 B题补题删一条边让图变成二分图这道题是我补题过程中收获最大的一题。题意很简洁给定一个无向图问能不能最多删除一条边使得剩下的图是二分图。n和m都在3e5级别需要在线性时间内解决。先回顾一个基础结论一个图是二分图当且仅当它没有奇环。因此我们的目标是找到所有奇环并且找到一条被所有奇环共同覆盖的边删掉它之后图中就不存在奇环了。DFS染色时如果遇到一条非树边且两端颜色相同说明这条非树边对应一个奇环。我们把所有这样的非树边数量记为cnt。如果cnt为0图本来就是二分图直接输出yes。如果cnt等于1直接删除那条非树边即可因为删掉它之后唯一的奇环被破坏。如果cnt大于1问题就变成需要找一条树边它被cnt个奇环全部覆盖。这时用树上差分统计每条树边被多少个奇环覆盖然后选择覆盖次数等于cnt的边再重新跑一次二分图染色确认一遍。这道题涉及的树上差分是在补题时才完全弄懂的。具体来说每遇到一条奇环非树边(u, v)就在差分数组上令cf[u]、cf[v]、cf[lca(u,v)] - 2这样向上累加后某条树边被覆盖的次数就是它子树内的差分和。需要提前预处理LCA这部分我单独写了模板重复练了很多次。坑点主要在两个地方一是图不一定是连通图每个连通块都要独立染色和差分二是判断删边后是否真的没有奇环不能只看覆盖数因为某些偶环被破坏可能会产生新的奇环虽然这种情况在删一条边时不会出现但为了稳妥我补题时还是强制要求重新染色检查了一遍。3.3 C题补题树上背包状态合并的顺序不能乱C题是一道典型的树上背包给定一棵有n个节点的树每个节点有重量和价值要求选出一个包含根节点的连通块使得总重量不超过容量C求最大总价值。n为1000C也是1000。看到这个范围基本可以确定是O(n * C^2)的树上背包或者用子树大小优化后达到接近O(n * C)的实际复杂度。状态定义是dp[u][j]表示在以u为根的子树中选定u这个节点并且从子树里继续选一些节点构成连通块总重量恰好为j时的最大价值。转移时对每个儿子v做背包合并void dfs(int u, int fa) { dp[u][weight[u]] value[u]; for (int v : g[u]) { if (v fa) continue; dfs(v, u); for (int j C; j weight[u]; j--) { for (int k 0; j k C; k) { dp[u][j k] max(dp[u][j k], dp[u][j] dp[v][k]); } } } }补题时我在这里踩了一个很经典的坑dp[u][j]会在枚举儿子的过程中被不断更新所以内层循环的顺序和初始值必须很谨慎。尤其是第二次遍历某个儿子时dp[u]里已经包含了之前儿子的转移结果如果不对dp[v]的合法状态单独做判断很容易把“不选当前儿子”的状态也当成合法状态参与合并导致结果偏大。这题让我重新理解了一个道理树上背包不能只背模板必须想清楚j和k分别代表什么。j是当前u这个连通块中已经合并过的部分k是当前儿子v这一支新加入的部分两者加和不能超过C。子树大小优化也是一种常见手段可以枚举子树大小限制循环上界把常数压下来。3.4 D题补题数学题先写小数据再上公式D题形式很简单给一个n求所有gcd(i, n)的和其中i从1到n。n最大可以到1e12所以不可能遍历i必须从约数入手。补题推导过程是这样的枚举n的约数d那么满足gcd(i, n) d的i有多少个令i d * x则gcd(d*x, n) d等价于gcd(x, n/d) 1。所以满足条件的i数量是phi(n/d)。于是答案就是ans sum_{d|n} d * phi(n/d)枚举约数的复杂度是O(sqrt(n))phi的计算需要先分解质因数整体完全能接受。实现时还要注意几个细节phi初始化为n用质因数分解时每个质因子只除一次枚举因子时用i * i n判断防止溢出乘法用long long如果n特别大还可以考虑__int128。这个题给补题带来的启发是遇到数论题不要一上来就推公式先用小数据手动算一遍比如n6时结果是gcd(1,6)gcd(2,6)gcd(3,6)gcd(4,6)gcd(5,6)gcd(6,6)12321615。然后观察约数结构再去套欧拉函数思路会顺畅很多。直接背公式容易漏掉phi(n/d)中的“除法对应关系”现场推导也比空想更可靠。3.5 E题补题Trie树统计LCP贡献E题是一道字符串题题面给了一批字符串要求计算所有不同字符串对的最长公共前缀长度之和。补题时我们发现这题用Trie树非常自然。把所有字符串插入Trie后每个节点代表一个前缀。如果一个节点被cnt个字符串经过那么以这个前缀为公共前缀的字符串对数就是C(cnt, 2)也就是cnt * (cnt - 1) / 2。一对字符串的最长公共前缀长度是多少它就会在对应深度的节点以及它所有祖先节点处被重复计数所以对每个节点累加C(cnt, 2)正好等于题目要求的答案。实现时需要注意重复字符串的处理。如果原串内部有重复Trie树节点的计数要记录终止节点数量不同终止节点之间如果共享到根的前缀一样要统计。当时我漏了“相同字符串两两之间也应该计入答案”这个点样例刚好没覆盖到交上去才wa。补题时在节点计数里同时维护了经停数量问题就解决了。4. 常见失误与排查技巧实录4.1 样例过了但wa的检查顺序赛后补题时很多题都会出现“本地样例过了提交上去wa”的情况。我总结了一套检查顺序基本能覆盖大多数问题。先看数据范围是否需要开long long尤其是乘法、加法和取模再看有没有多组输入数组或答案是否在每组样例开始前清空然后看下标是否把1-based和0-based混用了接着看边界情况比如n等于0、n等于1、空串、全相同元素。如果这些都查不出来就用小范围数据对拍。写一个只保证正确的暴力程序再写一个随机数据生成器两个程序反复跑一般几十组就能撞出问题。这个事情看起来简单但现场很多选手包括我自己都会为了省事跳过最后花更长时间在肉眼debug上非常不值得。4.2 高效对拍脚本怎么搭对拍脚本我习惯用bash写一套最简单可复用的。先准备三个文件force.cpp是暴力fast.cpp是待验证程序gen.cpp是随机数据生成器。编译好后循环跑数据把两组输出拿到diff里比对。#! /bin/bash for i in $(seq 1 10000); do ./gen in.txt ./force in.txt out_force.txt ./fast in.txt out_fast.txt if diff -q out_force.txt out_fast.txt /dev/null; then continue else echo WA on test $i cat in.txt break fi done这个脚本可以应对绝大部分测题场景。需要注意随机生成器要会构造边界不要一直生成普通数据比如数组长度取到上限元素值包含0、负数、最大值字符串包含空串等。对拍的核心目的不是证明正确而是在最短时间内找出一个反例所以数据越极端越好。4.3 补题时怎么判断自己是不是真懂了每次补完一题我都会问自己三个问题能不能不看题解把核心思路完整讲出来能不能把复杂度推导和每个边界条件都说清楚能不能在规定时间内重新写一遍并通过如果三个问题里有一个答不上来那这题就不算补完。有一个更有效的方法是“讲题给别人听”。补题时拉着队友或A同学把这道题的题意、思路、证明、复杂度讲一遍讲到对方能听懂为止。讲不出来的地方就是自己还没消化的地方再回去看题解。这个方法比反复刷三遍代码更省时间也更能暴露思维漏洞。我自己补B题时就是用这个方法发现漏掉了“多个连通分量”的情况。4.4 赛后为什么要先复盘而不是先补题比赛结束当天晚上我通常只做一件事把整场时间线画出来标记每段卡题的原因和换题决策然后让每个队友写出自己觉得最值得反思的一个点。当天不碰任何题解因为脑子还停留在比赛的惯性思维里容易把补题变成“照着题解写代码”效果很差。第二天开始补题时优先补那些“当时有部分思路但最终没AC”的题因为这些题和你的真实水平最近补起来效率最高。完全没思路的题放到后面随着专题训练再慢慢消化。南京站结束后我们按这个顺序用一周时间补完了所有题比以往比赛后囫囵吞枣式刷题要扎实得多。5. 赛后训练计划与个人体会5.1 区域赛暴露的短板怎么针对训练南京站让我最清楚看到自己的三个短板数论基本功不牢构造题经验不足罚时控制太差。赛后训练计划就围绕这三块展开每周固定分三个专题一天数论公式推导与线性筛、欧拉函数相关一天构造题专项一天规则赛模拟专门练习罚时控制。数论这块我踩过的坑是“只背模板不推过程”。后来强制自己每个公式从最基础的定义开始推一遍比如欧拉函数、莫比乌斯函数、整除分块推多了之后遇到新题也不再发怵。构造题则是纯粹的积累问题没有太多捷径只能靠做题量堆但要注意总结常见手法比如奇偶分类、增量构造、模意义下的构造而不是零散地记题。5.2 阶段赛事的时间线安排从网络赛到区域赛我比较推荐的时间线是这样的网络赛前一个月按专题训练确保板子完整拿到名额后进入两周模拟期每天一场模拟或隔天一场赛前三天停止高强度刷题只复习模板和易错清单。很多人赛前还想做新题结果把状态搞得很疲惫反而影响了现场发挥。南京站让我体会到比赛最后拼的不只是会不会做还有在长时间高压下能不能不出低错。平时训练就要把“过样例就交”的坏习惯改掉提交之前必须检查三件事数组大小、long long、输出格式。这三件小事我在南京站吃了不少亏补题时统计一下如果当时每个都检查到位罚时至少能少二十分钟。5.3 心态管理补不完的题永远存在但要分清优先级补题这一周里我逐渐接受了一个事实区域赛的题是永远补不完的每一场都会留几道需要很厚基础才能看懂的题。这不是坏事反而说明你发现了自己的天花板。重要的是把这些题目按“近期收益”排序而不是按难度排序。我现在的习惯是每次比赛结束后只挑三到五道题作为重点补题对象彻底吃透这几道比把二十道题都看一遍题解然后全部忘记好得多。剩下的题先收藏等后面专题训练到对应知识点时再回来做。南京站的题目风格偏思维补B题和构造题的过程明显比直接刷简单题更有提升因为每一道都在逼我重新梳理基础结论。最后再分享一个小技巧补题时不要只看网上题解的文字描述最好自己用一句话写出“这题的本质是什么”。比如余数桶那题的本质是“前缀信息计数”删边二分图那题的本质是“奇环覆盖与树上差分”Trie那题的本质是“公共前缀的重复贡献”。一个题如果能被一句话讲清楚说明你是真的理解了讲不清楚就先回到题目本身把每个例子手动跑一遍。这个习惯是我从南京站的赛后总结里收获最大的东西。