★ FEATURED ARTICLE 昨晚熬夜打了 Codeforces Round 1082 (Div. 2)打完之后的几个小时里我一直在想为什么我明明知道这是一场 Div. 2还是会在第三题上浪费掉接近三十分钟我的思路模板是不是已经过时了作为常年混迹于 Div. 2 的选手我太熟悉这种“前半段手速起飞、后半段大脑宕机”的节奏了。这次我决定不把比赛结果简单地丢进 rating 波动里而是认真做一次复盘顺便把赛前准备、赛中决策、赛后补题的完整过程记录下来。这篇文章不是官方题解也不涉及具体的 AC 代码逐行解释而是我从 Round 1082 这场比赛里提炼出的一套“Div. 2 生存方法论”。如果你也卡在 1400 上下或者第一次准备认真打 CF这些经验应该能帮你少走一些弯路。1. 赛前准备我在 Round 1082 开赛前 15 分钟做的事很多选手觉得 Div. 2 的比赛拼的是临场状态赛前准备随便看看就行。我之前也这么想直到有一次比赛刚开始就发现自己常用的模板文件没有更新后来不得不在前十五分钟一边敲代码一边骂自己。从那以后我养成了固定的赛前 15 分钟流程这次 Round 1082 同样受益于此。1.1 模板库不应该是临时回忆录先说模板。打 CF 最忌讳的是在比赛里手写基础数据结构比如快速读入、gcd、组合数、并查集。你可以说你记性好但比赛中每一秒都有价值尤其是 Div. 2 的前两题拼的就是从读题到提交之间的时间差。我的模板文件经过很多次比赛删改现在已经精简到一页以内包括bits/stdc.h、快读函数、常用常量和几个不太容易出错的算法框架。这次 Round 1082 的第一道题我用模板里的快读模板直接跑通省下的时间让我能提前几分钟进到第三题。别小看这几分钟后面我正是靠着这些“余量”才没有在第三题上彻底崩盘。1.2 本场的 A、B 题我为什么敢在 5 分钟内交开赛后我习惯先把所有题目的题面扫一遍不细读只看长度和数据范围。Round 1082 的 A、B 题看起来就是标准的“签到题”和“简单思维题”所以我给自己定了一个激进的目标前十五分钟至少 AC 两题如果 A 题顺利B 题最多多花五分钟。A 题我用了三分钟读完并且构造出思路五分钟内提交状态很好。B 题是一个典型的“找规律 边界判断”题目我没有一开始就写模拟而是先手推了几个样例确认模式后直接写代码。说实话Div. 2 的前两题很多时候不需要深入算法只要你不被样例牵着走、能把边界条件捋清楚AC 速度自然就上来了。1.3 从第一题结果反推本场难度曲线还有个习惯是我 AC 完 A 题后会看一眼榜上的过题人数分布。如果 A 题通过人数掉得很快说明这场比赛整体偏难后续题目要更保守地分配时间如果 A 题红红火火一大片那说明前面是白给题重心要提前放在第三、第四题上。这次 Round 1082 的 A 题通过率非常高我心里立刻有数真正的分水岭在第三题和第四题。所以我并没有因为前两题顺利就开始飘反而在第三题上多留了一个心眼。可现实是该卡还是卡了。2. T3 卡了我三十分钟贪心思路从“直觉”到“证明”每一场 Div. 2 都会有一道题让我意识到“会做”和“敢做”是两回事。Round 1082 的第三题对我来说就是这样一道题。它表面上是一道区间操作问题但实际上考的是贪心策略的正确性。我最初的想法看似合理却在样例构造的反例面前不堪一击。2.1 我最初的错误策略从右往左无脑处理题目大概是给你一个序列每次可以选取一段区间做某种统一变化问最少操作次数。这种题我第一反应是从右往左扫描遇到需要改的就顺手把前缀或后缀一起改掉。这在很多类似题里是标准解法但这次不行因为我漏掉了一个关键性质——区间变化并不是单调的某些情况下先改左边反而会改变右边的状态。我当时写了两版代码第一版跑样例没问题一提交就 WA。然后我陷入了最常见的误区开始打印中间变量到处怀疑是不是取模错了、数组开小了。浪费了大约十分钟后我强迫自己停手重新在纸上画小规模例子才意识到贪心顺序错了。2.2 反例与重新读题为什么“直觉”会骗人我构造了一个只有三个元素的例子其中最优操作是先修改中间位置再去处理两边而我“从右往左”的做法则需要多一次操作。这个反例点醒了我贪心的顺序不是由“下标从左到右”决定的而是由“依赖关系”决定的。谁先被修改不会影响谁的可用状态谁就应该排在后面。重新读题后我发现题目里其实有一句话强调了“每次操作会影响相邻关系”我之前完全没往心里去。这也是我想提醒大家的WA 之后先别急着改代码重新读题把每一个条件写在纸上尤其是那些看起来像废话的限定词往往就是隐藏的贪心排序依据。2.3 正确的贪心排序依据按影响范围排序后来我采用的方法是把所有待处理区间按“起始位置”排序然后维护当前已经覆盖到的右端点。每一步选择覆盖范围最靠前的、又不会破坏已处理部分的区间。这个思路本质上是经典区间调度问题但在这种包装下很难一眼看出来。实际写代码的时候我还是踩了一个细节坑排序时如果左端点相同必须按右端点降序否则贪心会多算次数。这个“二级排序规则”是我在本地写了三四个测试用例之后才确定的。这类题目最考验的不是你会不会某个算法而是你能不能从混乱的条件里找到那个唯一的“最小操作方式”。3. T4 的图论转化把等式关系变成边四十分钟的止损之后我来到第四题。这道题给我的感觉是题目描述非常抽象需要把数学关系翻译成图结构。Div. 2 的第四题经常出现这种“图论建模”题难点不在跑算法而在把题目翻译成“图”的那一下。3.1 题面中“相邻”背后的图结构第四题的输入给了一些点之间的关系比如某些点必须相同、某些点必须不同。我第一眼觉得是并查集但仔细一看“不同”的关系不能简单合并于是想到是不是要建图。我尝试把每个“必须不同”的关系看成一条边然后发现这其实是判二分图的性质如果一个图是二分图那么可以把点分成两个集合使得每条边的两个端点颜色不同。这个转化一旦完成剩下的就是非常标准的二分图染色检测。我曾经以为图论题都需要建出显式的图后来才意识到更多时候题目不会直接说“图”而是把边隐藏在“互相制约”的关系里。找出这个制约关系比套模板重要得多。3.2 孤立点与连通分量的边界处理建图之后我以为会很顺利结果又栽在了一个边界处理上图中存在孤立点。孤立点意味着这个点没有任何“不同”关系它可以任意归属到两个集合之一不影响结果。我在第一次提交时忽略了孤立点导致在染色循环里只遍历了从 1 号点出发的连通分量其他孤立点完全没有被访问最终输出了一个错误答案。修这个 bug 的办法其实很简单对整个图做循环对每个尚未染色的点都跑一次 BFS/DFS。这个操作是图论题里的基本功但越紧张越容易忘。我后来对比过别人的代码发现很多人会用for (int i 1; i n; i) if (!color[i]) dfs(i)这行代码看起来不起眼却是 AC 的关键。3.3 实现里的邻接表 vs 邻接矩阵这道题的数据范围比较大我一开始犹豫要不要用邻接矩阵觉得好写。后来算了算内存顶多两万多个点邻接矩阵直接爆掉于是老老实实用邻接表。写的时候用了 vector 的重复push_back效率足够提交也从 TLE 变成了 AC。通过这题我得到一个经验在 Div. 2 的图论题里千万不要因为数据范围看起来不大就贪图邻接矩阵的写法。邻接表多写两行却能避免后续无谓的调试。而且这道题还提醒我图可能不连通这是很多题目里最容易忽略的初始条件。4. 赛后补题这道题教会我的两个底层模型比赛结束后我没有立刻去看题解而是先把没 AC 的题目重新当新题做了一遍。Round 1082 的后面几道题里我意识到有两类模型反复出现几乎可以作为 Div. 2 中高难度题的通用钥匙。4.1 差分与前缀和的配合有一道题需要处理区间批量加值最终询问某个全局最小值。我第一次尝试用线段树做虽然能过但是代码又长又容易写错。赛后我尝试用差分数组只需要在区间起点和终点做标记再前缀和一次整个问题就变成一个线性扫描。这个优化让我重新理解了“数据结构”和“数学技巧”的边界当区间操作是静态的、不需要在线修改时差分永远比线段树更适合。我用了一个很简单的例子帮助自己理解如果把数组想象成一条路面差分数组记录的是“海拔变化点”前缀和则是把每个点的累积高度算出来。这种类比虽然不够严谨但对竞赛里的快速建模非常有用。4.2 二分答案的判定函数设计另一道题求“最大化最小值”或者“最小化最大值”这种带有明显单调性的问题最稳的做法就是二分答案。很多选手看到这种题会试图直接构造结果越构造越复杂。其实二分答案的核心是写一个判定函数check(x)它回答“当答案不超过 x 时是否可行”。我在补题时把判定函数单独抽出来写了至少三个版本每一版都试着打破它最终发现判定函数比主逻辑重要得多。你宁可总体多跑几轮二分也不要让判定函数里藏着一个贪心错误否则最后答案会非常稳定地错误。4.3 重新造样例的能力补题到最后我发现自己最缺的不是算法而是“造样例”的能力。官方题解只给出了结论但没告诉你它是怎么从一堆失败尝试里跳出来的。为了验证自己的理解我开始自己造随机数据然后用暴力方法对拍。对拍脚本写了几十行却让我对题目边界条件有了比看十篇题解更深的记忆。这个方法特别适合 Div. 2 选手当你看完题解以为自己会做了立刻合上题解重新实现一遍再对拍。如果对拍出了问题说明你根本没懂如果一次通过说明这道题真正变成了你的东西。5. 提交与 Hack 阶段那些不写进题解的细节Div. 2 比赛过程中有一个很容易被忽视的环节提交策略和 Hack 观察。不只是提交代码那一刻而是提交前、提交后、以及看别人被 Hack 后你学到的东西。5.1 我为什么在提交前强制检查 long long这次 Round 1082 我在前几题里都没有用到超过 int 的数据但做第四题时我和数据范围较劲了好一会儿。我总结出一个强制检查清单任何涉及乘法、累加、数组索引变量的题目先看数据范围是否能被 int 安全容纳如果不能就统一开long long。不要相信临场判断直接用一个宏定义或者using ll long long来写省得后面把int悄悄混进去。很多选手觉得 long long 会拖慢速度实际上现在的评测环境里这根本不是什么问题。因为漏开 long long 而 WA在 Div. 2 中后期几乎人人都会遇到至少一次这次我也差点中招。5.2 看 Hack 数据比看题解更有收获在比赛进入 Hack 阶段之后我喜欢去翻别人的 Hack 提交。那些极端的边界数据往往是一场比赛最有价值的教材。比如有人用n 1去测图论题有人用全相同字母去测字符串题还有人用最大最小值去测二分边界。通过观察这些 Hack我能看出出题人到底在哪些地方埋了坑。Round 1082 的 Hack 阶段里我看到不少选手因为孤立点、空区间、重复元素这类问题被叉。这不代表他们算法不熟练而是说明比赛的隐藏条件往往藏在“极简输入”中。把这个经验内化之后我以后写题会主动在草稿纸上列出 n 1、全相等、递增、递减、重复元素这些边界状况。5.3 赛时正确率与 Penalty 的取舍还有一个细节是关于罚时。Div. 2 的排名不仅看 AC 题数还看总罚时。很多选手为了冲题数在思路上没完全确认就提交结果 WA 了一次又一次。正确的做法是前两题可以稍微激进一些因为题目简单、WA 成本低但从第三题开始多花三分钟自测边界远比多一次罚时划算。我在这次比赛中给自己定了一条规矩每道题的代码写完提交前必须构造一个“最不像样例”的数据手动跑一遍。以前我觉得这样做浪费时间但只要每年能多避免一次 WA投入回报就是正的。6. 下一场之前我会坚持的三件小事赛后我翻了很多过去的代码和笔记发现能够稳定提升 Div. 2 成绩的往往是那些笨办法。Round 1082 让我再次确认了这一点所以我会把这三件小事执行到下一次比赛。6.1 维护“错题特征”表我准备给自己的 CF 备赛建一个表格每一行记录一道错题的特征包括题目类型、我采用的错误策略、正确模型、边界条件。这个表不为别人只为让我在下一次看到同类特征时能快速调用正确思路。Round 1082 的第三题和第四题都会记录进去尤其是“区间操作右端点降序”和“孤立点图染色”这两个点。6.2 每周至少两次 Virtual Participation实话说正式比赛的紧张感和平时随便做题完全不一样。以前我训练时习惯慢慢想但在 CF 里时间压力本身就是一种难度来源。为了提高我开始每周做至少两次 Virtual Participation要求自己像正式比赛一样设置倒计时、不允许中途查题解。这次 Round 1082 的中后段处理能力明显比上一次稳定我想归功于这种训练。6.3 用注释式解法写复盘笔记最后一件小事是我不再只是把 AC 代码保存下来而是必须用文字把每一题的推导过程写清楚。这种“注释式解法”不需要很长核心是回答两个问题为什么我想到了这个算法如果重新做一次哪一步可以更快很多题当时看题解秒懂过一周就完全忘记。只有写下来才能把“瞬时记忆”变成“长期理解”。我在整理 Round 1082 的复盘笔记时发现自己的很多 WA 都源于“连自己为什么要这么写”都没想清楚就开始敲键盘。下一场我会把速度放慢一点点先想清楚十步再一次性把代码写到通过。打 CF 从来不是比谁敲键盘快比的是谁能在更短时间里绕过所有错误分支。
阅读完成 · 觉得有帮助？
