上周日的 Codeforces 训练场打到一半我差点把键盘推出去。卡在 E 题上快四十分钟眼看着排名一直往下掉最后二十分钟又灰头土脸地回头写 F2手都在抖。最后虽然只过了四题但事后我花了两个多小时复盘发现这一场暴露的问题比之前顺风顺水连过六七题的那几场还要多。先说结论Codeforces 训练复盘这件事如果你只是把题解看一遍、然后再补一遍代码那基本等于白练。真正的复盘应该从时间线开始把每一道题的思考过程、卡点、WA 原因、复杂度估算失误全部摊开最好还能产出一份属于自己的“错误模式清单”。这篇文章我就以刚打完的这场 Div1Div2 为例把复盘方法、两道重点题目的完整推导以及踩过的坑全部写出来。希望能给同样在刷 CF 的朋友一点参考尤其是那些和我一样卡在 1600~1900 分段、感觉怎么打都上不去的同学。1. 本场训练复盘的整体思路1.1 为什么选这场、赛前定的目标这场是常规的 Div1Div2 组合场时长 2 小时 15 分钟。我赛前的目标很实际不追求 AK只求稳定过掉 Div2 的 A、B、C然后给 D 或者 E 留出至少四十分钟的完整时间。因为之前连续几场都是前面顺、后面崩要么在 D 题死磕四十分钟没出来要么一看 E 题就脑子空白所以这场我把精力分配当成头等大事来练。这里先说一个小技巧赛前给自己定目标不是让你给自己设上限而是让你有一个“止损”的参照系。比如我给自己定的规则是——如果 E 题想超过二十分钟还没有明确思路就必须先退回到 D 题或者回去检查已经交掉的题目是否有潜在漏洞。后面你会发现这条规则直接救了我一场。1.2 复盘方法时间轴、罚时和情绪记录赛后复盘我习惯用时间轴而不是按题号来记录。每道题从打开到 AC中间经历了哪些过程全部写下来。比如我会记打开题目时间、当时 rating 感觉、第一反应想用什么算法什么时候开始写代码、什么时候第一次提交第一次 WA 是因为什么这中间花了多长时间排查卡题时情绪变化有没有“明明思路对但代码写不出来”的烦躁感这个方法听起来简单但绝大多数人赛后复盘根本不会去回看自己下笔时想了什么。我见过太多人复盘时只写“这道题解法是 XX”然后草草收尾。等到下一场遇到类似问题照样犯同样的错。我这场的时间线大致是A 题 6 分钟B 题 13 分钟C 题 29 分钟然后跳了 D先开 E 题。E 题想了很久才找到方向总共花了 37 分钟 AC。回头再看 D 时已经有点焦虑草草写了个假贪心 WA 了一发剩下十分钟左右去碰 F2显然没写出来。这个时间线本身就说明问题D 题我是被“怕时间不够”的心态搞崩的并不是题目真的难得做不出。2. E. Moment of Bloom——一道图论构造题的完整复盘2.1 读题后的第一直觉树上路径与奇偶性先说题目大意给一棵 n 个点的树以及 q 个点对 (u_i, v_i)要求对每个点对选一条连接这两点的简单路径问是否存在一种选择方案使得每条边最终被覆盖的次数满足给定的奇偶条件如果有则输出方案。我第一次读完题的第一反应是“这题怕是跟树链剖分或者 LCA 有关”因为树上路径问题就那么几个套路。但仔细再读发现它并不要求最短路径只要求“选一条简单路径即可”而且约束的是边被覆盖的奇偶性。这其实是在暗示问题可以转化为一组路径集合是否能够拼出某个“边奇偶状态”。这里给刚开始刷 CF 树题的朋友一个经验看到“每条边被覆盖奇数次/偶数次”这种条件第一件事想到树差分看到“构造一组路径满足所有端点是给定点对”这种条件第一件事想到欧拉回路/欧拉路径。把这两个点联系起来这道题的方向基本就锁定了。2.2 卡点从“必要”推到“充分”但我在赛场上卡住的点恰恰是充分性。我很快想到如果存在一种方案那么把每条路径看成“在两端点之间连一条虚拟边”最终所有被选中的边的覆盖奇偶性其实只取决于端点的度数奇偶性。因为树上的边差分等价于端点权值的变化。具体来说一条路径 u-v 会给路径上的每一条边各贡献一次覆盖而这种贡献又等同于在两个端点上分别加 1在点差分意义下。于是问题变成了给定每个点要被加上多少次“端点标记”是否存在一组配对方案使得这些配对所对应的路径叠加后恰好满足边覆盖的奇偶需求。这里最容易被忽略的是——树上的路径并不是任意两条都能任意组合出任意边奇偶状态的因为树的每条边会把树切成两部分路径端点的配对模式必须保证跨越每条边的次数奇偶性正确。我当时在这里卡了挺久一直纠结“怎么判断一对端点的路径选择是否互相干扰”。其实后来才意识到对于树这种无环结构判断可以简化成把所有需要覆盖奇数次奇偶状态的边拿出来这些边会形成若干个连通块。对于一个连通块如果它的顶点都是给定端点并且奇偶度数条件满足那么就可以在这个连通块内构造欧拉回路再把欧拉回路切成 q 段每段对应一个点对。2.3 从树差分到欧拉路径构造最终赛场上我采用的构造思路是这样先把所有边按需求标成“需要被覆盖奇数次”的边和“偶数次”的边。因为偶数次是默认状态只需要关心奇数次边。把这些奇数次边形成的连通块抠出来。对每个连通块统计每个块内被作为端点使用的点的奇偶性。如果存在某个连通块内部端点的奇偶度数无法形成偶数个奇点那就无解。构造时把所有需要覆盖的边看成一张图。因为每个点对相当于连接两个端点的“需求边”我们可以在这些需求边和原树边组成的辅助图上跑欧拉回路然后把回路按需求边切开得到每条路径的走法。这个构造的过程有点像拼图先验证拼图碎片能不能拼成一个封闭环再用一个环把所有碎片串起来。写代码的时候主要用了两个数据结构邻接表存树以及一个并查集用来合并奇数次边形成的连通块。2.4 代码实现与提交记录实现上有几个细节特别容易出错我摔了一跤才注意到端点配对不能只看单个点必须看奇数次边连通块的整体奇偶性。我第一次交 WA 就是因为只检查了全局奇点数量为偶数没有按连通块分开检查。欧拉回路构造时如果直接用树边去递归可能在退栈时把顺序搞反。建议先把需要覆盖的边建立临时邻接表再跑一遍标准欧拉回路模板。最后切分路径时要保证每段路径的起点和终点正好是第 i 个点对不能把回路顺序打乱。第一次提交在 pretests 挂了一发报错是 WA on test 3我当时还很纳闷。后来本地跑了几组手造数据才发现是并查集合并时漏掉了一种“孤立奇点”的情况。改完之后 37 分钟 AC比预期慢了不少但至少把分保住了。3. F2. Korney Korneevich and XOR (hard version)——DP 优化的实战复盘3.1 从 easy 版本说起O(n*m) 的暴力 DPF2 这道题我是在比赛结束前十分钟才开始看的自然没写出来。赛后补题时先把 easy 版本做了一遍才理解整个题目的结构。题意大致是给一个长度为 n、值域不超过 m 的数组 a要求找出所有可能的异或值这些异或值来自某个“严格递减子序列”。也就是说我们可以选择若干位置 p1 p2 ... pk要求 a[p1] a[p2] ... a[pk]然后把这些位置的数全部异或起来问能得到哪些值。easy 版本的做法很直接定义 dp[x] 表示“凑出异或值 x 的严格递减子序列中最后一个元素的最小可能值”。为什么要最小因为递减序列要求后面接的新元素必须比上一个元素小所以最后一个元素越小越容易被更小的元素接上。初始时 dp[0] INF表示空序列其他 dp[x] 设为 -1 表示不可达。从左往右扫描数组对于当前位置值 v遍历所有可能的异或状态 x如果 dp[x] v那么说明存在一个以 dp[x] 为末尾的合法序列且末尾元素大于 v所以可以把这个序列接上 v形成新的异或值 x ^ v其末尾元素变成 v。于是执行 dp[x ^ v] min(dp[x ^ v], v)。这个转移的复杂度是 O(n * m)easy 版本 n 和 m 都小能直接跑过。核心代码大致长这样const int INF 1e9; vectorint dp(1 12, INF); dp[0] INF; // 空序列末尾可以看成无限大 for (int v : a) { for (int x 0; x (1 12); x) { if (dp[x] v) { int nx x ^ v; dp[nx] min(dp[nx], v); } } }顺带一提dp[0] INF 这个初始化特别关键。没有它空序列永远没法“接上”第一个元素整个 DP 就废了。3.2 hard 版本的瓶颈n 拉到 1e6 后怎么办到了 hard 版本m 仍然是 2^12 4096 级别但 n 可以到 1e6。这时候直接 O(n * m) 就是 4e9 次操作稳 TLE。我的第一反应是找冗余每次扫描数组时我们其实把 v 相同的多个位置重复扫描了很多次但 dp 数组更新到最后同一个 v 带来的转移增量并没有想象中那么大。这里我走了不少弯路。我一开始想的是“每个值 v 在数组中只需要处理最后一次出现的位置”后来发现这个思路有问题。因为 DP 是全局的同一个值 v 在不同位置出现对后续转移的影响并不完全一样——它出现的位置决定了它能“接在哪些更小的值前面”。如果只保留最后一个位置可能丢掉一些中间位置带来的合法组合。后来我换了一个角度既然 m 最大只有 4096真正值得花力气的地方不是 n而是 m^2。如果能把对每个数组元素的转移变成对所有可能的状态集合做一次性更新那复杂度就能控制在 4096^2 / 64 这种量级用 bitset 跑位运算非常快。3.3 用值域 bitset 做整体转移的尝试我赛后补题试着写了一个基于 bitset 的版本思路是维护一个数组 best[x] dp[x]然后对每个出现过的值 v找出所有满足 best[x] v 的 x把它们看成一个集合 S_v再整体更新 S_v 异或 v 后的状态。具体做法是用一个长度为 m 的 bitset cur第 i 位表示“当前是否能凑出异或值 i”。初始时 cur 只有第 0 位是 1。然后从大到小枚举值 v对每个 v我们把 cur 中所有满足 best[x] v 的 x 取出来整体左移/异或 v再并入 cur。因为位运算一次能处理 64 个状态所以总的位运算次数大概是 m^2 / 64完全能跑。但这个做法有一个实现上的坑best[x] 会不断更新变小导致“满足 best[x] v”的集合 S_v 不是在某一时刻固定的而是随着遍历不断变化的。如果每来一个 v 都重新扫描所有 x 去判断就退化回 O(m^2) 了。我最后是用了一个 vector 桶把当前 best[x] 等于某个阈值的 x 收集起来在最佳时机统一处理才把这个问题绕过去。3.4 优化后的复杂度与最终代码形态优化后的复杂度大约是 O(n m^2 / 64 m * k)其中 k 是每个状态可能被更新的次数实际运行下来非常快。核心代码框架大概是const int M 1 12; vectorint dp(M, INF); vectorvectorint bucket(M); dp[0] INF; // 初始化桶把初始可达状态按“当前末尾值”分组 bucket[INF % M].push_back(0); for (int v : a) { // 只处理当前 v 可能带来的增量更新 for (int x : bucket[v]) { // 这里 x 满足 dp[x] v int nx x ^ v; if (dp[nx] v) { dp[nx] v; bucket[v].push_back(nx); // 注意这个写法实际需要防重复 } } }这只是一个示意真正的实现还需要处理重复入桶、负 INF 等问题。我最终在本地测试 1e6 的随机数据耗时在可接受范围内但比赛时如果让我现场写我大概率还是会翻车。这个题给我最大的收获是遇到“n 很大但值域很小”的 DP与其硬刚 n不如把状态按值域分桶把复杂度从 n * m 压到 m^2 级别。4. 本场时间分配与卡题心态复盘4.1 时间线复盘表赛后我把自己这场的时间线整理成了下面这个表时间事件花费备注0:00-0:06A 题 AC6 分钟签到题直接模拟0:06-0:19B 题 AC13 分钟中间 WA 了一发手速太慢0:19-0:48C 题 AC29 分钟思路对但 debug 浪费了时间0:48-1:25E 题 AC37 分钟第一发 WA第二发 AC1:25-2:00D 题 WA35 分钟假贪心赛后发现漏了一种情况2:00-2:15F2 看了一眼15 分钟只够写个暴力验证思路这个表一拉出来问题就一目了然了我在 E 题上花了 37 分钟虽然最后 AC 了但这挤占了 D 题的时间。如果按照赛前计划D 题应该有至少四十分钟的完整时间而不是最后三十分钟慌慌张张地去写。4.2 判断继续磕还是先跳的四个标准这件事我复盘时总结出四个判断标准现在每次比赛都会用第一如果当前题已经写出代码但连续两次提交 WA 且无法快速定位 bug说明思路可能不完整或者实现有隐藏问题这时应该退回去重新审视推导而不是在现有代码上打补丁。第二如果一道题想了十五分钟没有任何实质性的算法方向那就直接标记为“需要看题解”先跳去做其他题。第三如果剩余时间不足二十分钟不要开一道没有任何把握的新题应该回去检查已经提交的题是否真的有潜在问题。第四如果比赛中出现“我明明会做但代码写不出来”的烦躁情绪说明当前状态已经不适合高强度的思考及时休息二三十秒再继续。这四条听上去很简单但真正打比赛时很容易被“这道题我再想想就能出来”的错觉拖着走。我这场 D 题就是栽在这里。4.3 补题安排的策略赛后补题我一般遵循“12隔天复习”的节奏当天先把做出来的题复盘一遍再把没做出来的题中我觉得最该学的两道比如本场的 D 和 F2补完。隔天再重做一遍 D 题确认不是背答案而是真的把思路走通了。补题有一点特别重要不要只补难题。很多人赛后只看 F2 这种压轴题反而把 D 题的简单错误放过去了。可实际上限制你上分的往往是 D 题这种中等难度题的稳定性而不是 F2 能不能做出来。所以我建议复盘优先级应该是本场实际上可做出但没做出的题 本场做出来但过程很挣扎的题 真正的压轴难题。5. 错题与坑点记录从罚时里捡回来的经验5.1 本场低级错误速查表复盘时我把整场所有 WA、TLE 和潜在风险统一整理成了一个表这类表在下次比赛前翻一遍特别有用错误类型具体问题出现题目以后怎么避免WAB 题多组数据没清空数组B每组数据前重新初始化不能只开一次WAE 题连通块内奇点判断漏了孤立点E每次合并并查集后统计 size 为 1 但又被标记的点WAD 题贪心排序规则写错D先手推两个反例再写 sort 比较函数TLEF2 暴力 DP 没优化F2值域小、数组大时第一时间想 bitset 或分桶心态D 题写挂后情绪急躁D卡题超过 15 分钟先撤退这里我想重点说一下 B 题那个低级错误。其实不是我不会做而是比赛刚开始还没进入状态读题时把数组大小看错了开了两倍空间却没在循环里重新 memset。这种错误在压力大的时候特别容易犯所以我现在养成了一个习惯所有多组数据题一律用局部变量并在每一组开头 clear而不是依赖全局变量清零。5.2 我整理的个人代码检查清单复盘完之后我给自己定了一份提交前的检查清单现在已经打印出来贴在显示器旁边多组数据是否清空所有容器数组开的是否足够大n 的最大值是否考虑过 1 或 5有没有特殊输入需要输出 “-1” 而不是 “0”排序比较函数是否严格弱序有没有可能 a b 且 b aDFS 递归深度是否会爆栈大 n 时是否需要改成迭代或加栈使用 long long 的地方是否全部用上位运算优先级有没有被括号包住数据范围是否可能溢出 int这份清单大概有十几项。每次提交前过一遍几秒钟的事但能省掉很多无谓的罚时。比如本场 D 题如果用这个清单检查至少能发现 sort 比较函数里我漏掉了相等情况下的处理。5.3 赛前热身与固定开场流程最后分享一个我坚持了挺久的习惯每次比赛前 15 分钟我不会刷手机或者看群里的讨论而是先做两道简单的模板题比如快速幂、最短路、并查集这种把手热起来。也不做多两道就够。目的是让手指和思维进入“竞赛节奏”避免像本场 B 题那样开场就出现低级的清空失误。开场之后的固定流程也很简单按顺序读完 A、B、C 三题每题快速判断难度和算法方向如果某题看完第一眼没有思路就立刻跳到下一题。这样做的原因是Div2 的前三题有时候难度顺序并不是单调递增的偶尔会出现 C 比 D 还简单的情况。先整体扫一遍能避免在一个偏难的 B 题上浪费时间。我个人体会最深的一点是题目难度排序不代表最优做题顺序你真正需要的是“先做自己有把握的题再做需要思考的题”。这场的 F2 我在最后十几分钟才打开本来就已经做不出来但如果我能早一点意识到 D 题那个贪心是错的把时间省下来去认真推导 F2 的转移优化也许赛后能少一点遗憾。Codeforces 训练复盘这件事说到底不是为了让你“证明自己那一场有多厉害”而是为了让你在下一场开打之前把该踩的坑都提前踩掉。如果你也打算开始认真复盘建议就从今天这场开始把时间线拉出来把每道题的错误模式写下来它对你的帮助会比多刷三套题还大。