昨晚重新过了一遍 Codeforces Round 1081 (Div. 2) 的 A-E这场给我的感觉非常典型A 题是送分的构造题E 题是压轴的图论思维题中间三道题的难度梯度也安排得挺合理。如果你最近正在刷 Div.2 练手感或者马上要打第一场 CF想提前知道这些题到底在考什么这篇复盘值得看完。我自己的定位是稳定 Div.2 前四题偶尔能摸到 D 的边E 基本要靠赛后复盘才能啃下来。所以这篇文章不会假装每道题都是我现场 AC 的。A 题我会把完整推理链讲透E 题按复盘时的推导重新走一遍B/C/D 我更侧重破题方法和当时卡壳位置的分析而不是把官方题面复述一遍。这样对大多数选手来说收获反而更大。1. 赛前定调这场 Div.2 的难度曲线与目标拆解1.1 本场整体定位Round 1081 是标准的 Div.2 专属场5 道题没有 Div.1 选手“抢前排”榜上参考价值也更贴近普通选手的真实水平。这类场次最重要的特征是A 题几乎不设防E 题则是典型的高区分度题。以我打 CF 的经验Div.2 的难度曲线通常不是线性上升的而是阶梯式的。1081 这场大致可以分成三个台阶题号定位核心考点预期用时A送分题数论构造、临界条件5-10 分钟B-C中段分水岭分类讨论、贪心、模拟优化20-40 分钟D-E高分区分水岭图论建模、奇偶性、组合思维40-90 分钟很多新手打 Div.2 喜欢从 A 到 E 按顺序硬啃时间全耗在 D/E 上最后 B/C 反而没时间细想。这是比较亏的打法。正确的思路是先把 A、B、C 稳定拿下剩余时间再集中突破 D/E哪怕只写出一半思路分数也比在前面的题上反复试错要高。1.2 不同水平选手的目标分配我给身边朋友的建议一直是一句话参赛前先给自己定清晰的目标而不是“尽量多做题”。刚接触 CF、rating 在 1200 以下目标就是 ABC 题作为额外奖励。重点练读题速度和 A 题的构造敏感性。稳定在 1400-1600 之间目标是 A-B-C 三题稳拿D 题允许自己想 30 分钟超过 30 分钟果断停手。冲 1800 的选手A-C 要在 30 分钟内解决D 题留 60 分钟E 题只作为理论上的冲刺目标不建议牺牲前面题目的正确率去赌。我在打这场的时候给自己定的是“35 分钟拿下 A-C剩下的时间全部给 D/E 里的图论题”。实际比赛里 A 题非常顺利B/C 各卡了一次等到开始碰 E 的时候大概剩 40 分钟时间依然很紧张。这也说明 Div.2 中段题往往比想象中更耗时间时间分配一定要留足冗余。2. A 题 LCM Problem 详解一个构造题的完整推理链2.1 题意与第一反应A 题的题面很简短给定两个正整数 l 和 r要求找两个不同的整数 x、y满足 l ≤ x y ≤ r且 l ≤ lcm(x, y) ≤ r。如果存在就输出 x 和 y不存在就输出 -1 -1。第一反应肯定是暴力枚举但看了一眼数据范围就放弃了。CF 的 A 题很少真的让你枚举它考察的是你能不能抓住一个极端构造。当时我脑子里冒出来的第一个想法是如果 lcm 要落在 [l, r] 里那 y 取 l 的倍数是不是最省事因为 lcm 一定是 x 的倍数如果 x 本身就取 l那么 lcm(l, y) 也一定是 l 的倍数天然满足下界 l ≤ lcm(x, y) 这个条件。这个思路顺着往下走答案很快就浮现出来直接输出 l 和 2l问题是 2l 是否还在 r 以内。也就是说核心判断条件变成了 r 是否大于等于 2l。2.2 关键性质为什么 r ≥ 2l 就是充要条件这道题真正的思维点在证明“r ≥ 2l”不只是充分条件还是必要条件。先看充分性。如果 r ≥ 2l那么取 x ly 2l显然有 l ≤ x y ≤ r。再看 lcm(l, 2l) 2l同样落在区间内构造直接成立。再看必要性。假设存在合法的 x、y那么 lcm(x, y) 必然是 x 的一个倍数而且因为 y xlcm(x, y) 不可能等于 x否则 y 必须整除 x但 y x 时这是不可能的所以 lcm(x, y) 至少是 2x。又因为 x ≥ l所以 lcm(x, y) ≥ 2x ≥ 2l。题目要求 lcm(x, y) ≤ r于是必须有 r ≥ 2l。这一串推理其实是很多 CF 数论题的核心套路构造题先找一组“看起来最极端”的候选再证明这个候选的边界条件就是整个问题的充要条件。这道题里最极端的候选就是 l 本身和它的两倍因为 lcm 至少是较大数的某个倍数两倍已经是最小可能了。2.3 参考实现与边界检查#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin t; while (t--) { long long l, r; cin l r; if (r 2 * l) { cout l 2 * l \n; } else { cout -1 -1 \n; } } return 0; }这里有一个非常容易踩的坑l 和 r 的范围不算大但2 * l 可能超过 int 范围所以在判断条件和输出时都必须用 long long。我见过不少人在这个位置用 int导致大数据直接溢出判错。另外输出多个答案时只要任意合法即可不需要输出字典序最小或其他特殊形式的答案。CF 的构造题一般都会在题面里说明“如果有多个答案输出任意一个”看到这句话就可以放心大胆地用最简构造。2.4 这类 A 题的通吃套路把 Round 1081 A 题的方法扩展开其实能总结出 Div.2 A 题的一类常见套路。很多 A 题看着是数论、看着是模拟实际都是在考察你对“边界状况”的判断。比如类似题还会出现要求两个数满足某种整除关系优先考虑最小公倍数和最大公约数的极端情形。要求在一个区间里找满足某性质的数优先考虑区间的两个端点。要求判断是否存在构造先在边界条件上找反例再设计构造。我在训练的时候养成了一个习惯看到 A 题先问自己三个问题——这个式子的极端取值发生在哪里如果只有一次机会构造我会选什么这个选择是否天然满足一半条件这三个问题过一遍大部分 A 题都能在五分钟内定下思路。3. B/C/D 中段题破题思路卡壳时我用的检查清单3.1 中段题的通用破题检查单说实话写这篇复盘的时候我不打算把 B/C/D 的官方题面逐字复述一遍这类信息网上随时可以查到。我更想分享的是当时在比赛中段我反复使用的破题检查清单。这一套清单对多数 Div.2 的中段题都适用。我把它整理成了一张表遇到卡壳就按顺序自查步骤检查项具体操作1数据范围暗示什么算法n ≤ 1e5 通常排除 O(n²)n ≤ 20 才考虑状态压缩2有没有单调性能排序就先排序能二分就找判定函数3极端输入长什么样全部相同、全部逆序、全是 0/1手算一遍找规律4操作是否有不可逆约束贪心题通常要问“当前这步会不会影响后面的可能性”5能不能转换成图论模型任何“关系”都可以建图连通性、奇偶性、最短路都可能隐藏在里面6答案是否与奇偶性相关路径覆盖、翻转操作、配对问题统统先算奇偶性当时我在 B 题和 C 题上各卡过一次回看都是因为跳过了第 3 步直接凭感觉写代码。后来强迫自己在草稿纸上先跑几组极端小数据明确性质之后再动手效率反而高了。3.2 中段题的“先暴力后优化”策略还有一个我用得很多的方法是“先写一个能跑出正确答案的暴力哪怕复杂度完全不能过”。很多人觉得这是浪费时间实际上非常有用。暴力代码跑小数据能帮你确认性质还能用来对拍。我当时在 C 题上推了一个看似正确的贪心结果样例过了、自己造的数据出错了果断写了个 O(n²) 暴力对拍几分钟就定位到问题所在。具体操作是这样假设你怀疑答案是某种排序后的策略先写一个枚举所有顺序的暴力跑 n ≤ 8 的数据对比你的贪心结果。如果两者不一致说明贪心细节有漏洞如果一致你才有信心继续优化复杂度。对拍这件事在赛后复盘里价值更大。Round 1081 的中段题我复现的时候写了一个暴力版和一个最优版专门去验证“边界处的极端数据”最后发现所有问题几乎都出在两类场景一类是答案边界刚好卡在某个判断条件上另一类是数据里有重复元素时贪心顺序出错。这两个场景在比赛时都不太容易凭肉眼看出来。3.3 中段题的时间盒原则我给自己的 B/C/D 设了一个“时间盒”每道题最多 30 分钟到点还没思路就立刻换题或者转写部分分。这不是逃避而是 CF 的计分规则决定的只要提交通过就有分一道题耗太久会导致后面的题完全没时间。实际操作下来Round 1081 的 B/C 都属于“想通了一个关键点就大幅简化”的类型。中段题的破局点往往藏在一句话条件里比如某个操作只允许做奇数次、某个数组可以重新排列、某个序列的相邻差有特殊性质。当你发现原本复杂的模拟突然可以被一个简单的数学性质简化时基本上就是正确路线的信号。如果你想专门练这种中段题的破局感我建议把每场 Div.2 的 B/C 单独拎出来做限时训练每次只做两题40 分钟做完立刻看 editorial。坚持十场之后你对“题目在暗示哪种算法”的敏感度会明显提升。4. E 题 Moment of Bloom 复盘把路径覆盖变成奇偶性计数4.1 先理解这道题到底在问什么E 题的名字叫 Moment of Bloom我印象非常深因为它是那种“看完题面觉得毫无头绪听懂思路之后拍大腿”的题。题意大致可以概括为给一个无向图每条边一开始都是白色有若干次操作每次操作会给你两个点你需要选择一条连接它们的简单路径把路径上所有边染红。问能否经过所有操作后让所有边都变成红色如果不行最少要修改多少次操作比如改掉某个操作的一个端点才能做到。它的难点在于路径是可以自由选择的你不需要在操作时提前知道所有路径只需要满足最终所有边都红。这一类问题最忌讳的就是一上来想“具体路径怎么走”而是应该把问题抽象成“每条边是否被选中奇数次”。我当时卡了很长时间因为一直在想怎么构造路径。实际上官方的核心观察很关键路径本身不重要的重要的是路径端点给每个点带来的奇偶性。4.2 关键观察路径两端带来的奇偶性先做一个简单的思维实验。如果一条边被选中偶数次它的颜色相当于没变选中奇数次颜色翻转。所以问题就变成了能否为每次操作选一条路径使得图上的每条边被选中的次数都是奇数。接着考虑每个点。一条路径贡献的是一条链链上的每个点度数贡献如下两个端点各贡献 1中间每个点贡献 2。也就是说无论路径怎么选中间点的“贡献次数”都是偶数只有端点的贡献是奇数。现在把所有操作的“端点需求”统计出来每个点作为操作端点的次数记为 cnt[v]真正决定最终状态的只有 cnt[v] 的奇偶性。对于一条路径覆盖问题我们最后看到的效果是——图上所有红边的度数奇偶性必须和所有端点的奇偶性对应。这就是把“路径覆盖”转换成“点的奇偶性匹配”的关键一步。有了这个转换问题一下子简化了一大半。我们不再需要关心每次操作选哪条路只需要确认最终的红色边集合是否在奇偶性上匹配操作端点的需求。4.3 用 DFS 树确定每条边是否必须被选下一步是确定哪些边必须要被选为红色。用 DFS 树来处理这类问题很自然。对无向图跑一遍 DFS可以分成树边和非树边。先只考虑树边。对每个点 v统计以 v 为根的子树中所有操作端点的奇偶性。如果这个子树里操作端点的总数是奇数说明子树内的端点需求“溢出”了必然会有一条边从 v 连向它的父节点且这条边必须被选中奇数次。这个判断用一次子树求和就可以完成。具体实现时令 sub[v] 表示 v 的子树内所有 cnt[x] 的奇偶和。如果 sub[v] 是奇数那么树边 (v, parent[v]) 必须被选中奇数次否则这条树边不用选。这一步其实是树上差分的标准应用很多树上路径统计的问题都长这样。它的精髓在于树边能否被选完全由子树端点决定不需要关心非树边。至于非树边它们在 DFS 树里天然形成环可以作为自由变量来调整一些局部的不平衡所以通常不会影响判定结果的正确性只会在方案构造阶段参与进来。4.4 最少修改次数不匹配点对数的一半接下来是最有意思的部分。按上面的规则我们可以确定一个“理论红边集合”。如果这个集合里每个点的度数奇偶性 cnt[v] 的奇偶性那么问题有解直接按树边非树边构造路径即可。如果不相等说明有些点“不匹配”。一个操作包含两个端点修改一个操作的一个端点会改变两个点的 cnt 值。也就是说一次修改可以同时调整两个点的奇偶性。因此最少修改次数就是所有不匹配点对数量的一半。假如不匹配点的个数是奇数则说明问题无解因为这等价于需求本身自相矛盾。我在复盘时按这个思路重新推了一遍发现整个流程非常顺畅核心步骤是这些统计每个点作为操作端点出现的次数 cnt[v]。用并查集确保每个操作的端点都在同一个连通块内否则无解。跑 DFS 生成森林计算每个子树内的 cnt 奇偶和。根据子树奇偶和确定所有树边是否必须被选。统计不匹配点数 k答案就是 k / 2k 为奇数则无解。核心伪代码可以写成这样vectorint cnt(n 1, 0); for (int i 0; i q; i) { int u, v; cin u v; cnt[u] ^ 1; cnt[v] ^ 1; } // DFS 生成树计算子树奇偶和 functionint(int, int) dfs [](int v, int fa) { int sum cnt[v]; for (int to : adj[v]) { if (to fa usedEdge[v][to]) continue; sum ^ dfs(to, v); } if (fa ! 0 sum 1) { redEdge.push_back({v, fa}); } return sum; };注意这里用异或代替加法因为只需要奇偶性。这个技巧在路径覆盖题里比直接用 int 累加更稳不会溢出思维上也更贴合“奇偶性”这个核心。4.5 这类题的迁移价值E 题最值得学习的地方在于它把“路径”这个几何概念抽象成了“点的奇偶性”再用树结构确定具体边。这个思维模式在 CF 里一点不过时后续很多 Div.2 甚至 Div.1 的图论题都有它的影子。以后再遇到“若干次路径操作最后判断某种状态”的题先问自己几个问题每个操作的端点贡献是什么中间点和端点的区别在哪如果不看具体路径只看奇偶性问题会不会瞬间简化把这些想清楚再去考虑树的形态和具体构造思路会清晰很多。5. 实战踩坑记录与 WA 定位技巧5.1 本场最容易踩的三个坑复盘多了你会发现Div.2 的 WA 往往集中在几个固定位置。Round 1081 这场的典型坑如下常见错误出现位置原因与避免方式int 溢出A 题、E 题统计计数2*l、求和类变量直接开 long long多组数据未重置A 题多测试点场景把声明放入循环内或手动初始化只考虑连通性不考虑奇偶性E 题路径覆盖要先看端点奇偶性再看连通块贪心缺少对极端数据的验证B/C 中段题写代码前先手算全 0、全 1、最大值数据第一个坑我在 A 题里已经提到这里再强调一次CF 的构造和判定类题目边界数据往往就是为 long long 准备的。只要题目数值范围上限是 1e9 级别涉及乘法和倍数关系的判断就一律用 long long不要省。第二个坑更隐蔽。很多 Div.2 的 A 题是多测试点如果你习惯把变量声明在全局每次循环开始前没有清理干净第二次样例就会把上一次结果带进来。我的习惯是尽量把变量声明在 while 循环内部从根上避免残留。第三个坑是 E 题的专属陷阱。判断一个图有没有解最直接的思路是检查连通性但这道题光有连通性不够。每个查询的端点必须连通但所有端点的奇偶性匹配更要一致。漏掉后者的人往往会在大数据 WA 上debug 时又很难从超长输出里找到规律。5.2 WA 之后的系统化定位方法很多新手 WA 之后第一反应是盯着代码一行行读这效率很低。我给自己定的流程是这样的第一步重新读一遍题面。不是从头看到尾而是只找与判断条件相关的句子看看有没有漏掉“输出任意合法答案”“保证输入无重复”“答案可能超过 int”之类不起眼但致命的限制。第二步构造极端数据。专门挑边界条件最小值、最大值、所有值相等、数组长度为 2、空集合等。每个边界跑一遍输出是否合理立刻能看出来。第三步写暴力对拍。已经反复确认没有明显问题时写一个不关心复杂度的暴力解法随机生成小数据和正式代码对比。这一步能定位大约 90% 的隐蔽错误。我当时在 E 题上用这个方法找到了自己忽略的一个点我统计 cnt 时直接把同一个操作的两个端点都异或了但没考虑图中某些点可能只有一次操作到达DFS 子树求和时会漏掉不在任何连通块里的孤立点。后来把 cnt 只统计在图中实际出现的点问题就消失了。5.3 搜索资料时的一个小提醒赛后查题解和讨论时注意一下关键词题目标题里的 round 这个词在编程领域里太容易被别的上下文带偏。比如很多人在查“Codeforces Round 1081”的资料时会混进语言里 round() 函数的讨论PHP、VFP 等语言的 round 函数和竞赛题完全是两回事。搜索时尽量带上 codeforces、div.2、题号这些限定词能省不少时间。另外我强烈建议赛后去看每一题的官方 editorial尤其是 E 题这种偏思维的题。官方题解里给出的“从问题到解法”的推导顺序往往比你看过的任何英文博客都更接近出题人的思维路径。哪怕一开始看不懂也可以先把官方解法里的观察点记录下来过几天再回头做一遍效果比把别人题解全文复制一遍好得多。6. 赛后三件事从 Round 1081 带走的思维升级6.1 现在的 Div.2 已经不只是考“会不会算法模板”打完这场我最大的感受是Div.2 的命题明显在往“思维方法”上靠。A 题如果只是会背 lcm 公式是不够的必须理解“最小可能倍数”这种边界思维E 题更是把路径覆盖、DFS 树、奇偶性这种高级概念组合在一起考察的是建模能力而不是某个现成模板。这种趋势下光刷板子题容易遇到明显的天花板。你需要做的不是记住更多模板而是学会在关键时刻停下来问一句题干里的哪个条件是我没用的这个条件在真实场景下限制了什么把没用的条件找出来往往就是解题的入口。6.2 我推荐继续练的同类题如果你想趁热打铁把与 Round 1081 同类的思维练扎实可以考虑这几个方向的题目关于 LCM 和 GCD 的极端构造题找几场 Div.2 的 A 题优先选题干只有两行的练习快速判断充要条件。关于路径覆盖与奇偶性的图论题凡是题干里出现“将一条路径上的边染色”“翻转路径上的状态”这类描述都值得拿出来按 E 题的思维重新推一遍。关于 DFS 树和非树边自由度的题这类题在 Div.2 的 D/E 题里并不少见关键就是先确定固定部分树边再确认自由部分怎么调整。练的时候不要追求题量要追求“想通每一道题的关键观察”。一道题如果能自己推出来胜过十道题看答案。6.3 我个人这场的最大收获复盘 Round 1081 给我的真正体验是一道题一开始无论如何都看不懂但只要把一个关键问题从“这条路怎么走”换成“每个点需要贡献奇数次还是偶数次”整个人就像换了副眼镜后面的推导全通了。现在我做图论题看到路径两个字第一个动作不再是去枚举路径而是先问这条路径两端的奇偶性是什么中间点能不能被忽略这个习惯就是从这个 E 题开始的。最后再分享一个小建议赛后无论成绩如何都第一时间把每道题的想法写下来哪怕只是两三句“我当时卡在 XX”“后来发现应该先考虑 XX”。这些零散记录过一个月回看会比任何题解都更能反映你的思维盲区也是通往稳定 AC 的最短路。 昨晚重新过了一遍 Codeforces Round 1081 (Div. 2) 的 A-E这场给我的感觉非常典型A 题是送分的构造题E 题是压轴的图论思维题中间三道题的难度梯度也安排得挺合理。如果你最近正在刷 Div.2 练手感或者马上要打第一场 CF想提前知道这些题到底在考什么这篇复盘值得看完。我自己的定位是稳定 Div.2 前四题偶尔能摸到 D 的边E 基本要靠赛后复盘才能啃下来。所以这篇文章不会假装每道题都是我现场 AC 的。A 题我会把完整推理链讲透E 题按复盘时的推导重新走一遍B/C/D 我更侧重破题方法和当时卡壳位置的分析而不是把官方题面复述一遍。这样对大多数选手来说收获反而更大。1. 赛前定调这场 Div.2 的难度曲线与目标拆解1.1 本场整体定位Round 1081 是标准的 Div.2 专属场5 道题没有 Div.1 选手“抢前排”榜上参考价值也更贴近普通选手的真实水平。这类场次最重要的特征是A 题几乎不设防E 题则是典型的高区分度题。以我打 CF 的经验Div.2 的难度曲线通常不是线性上升的而是阶梯式的。1081 这场大致可以分成三个台阶题号定位核心考点预期用时A送分题数论构造、临界条件5-10 分钟B-C中段分水岭分类讨论、贪心、模拟优化20-40 分钟D-E高分区分水岭图论建模、奇偶性、组合思维40-90 分钟很多新手打 Div.2 喜欢从 A 到 E 按顺序硬啃时间全耗在 D/E 上最后 B/C 反而没时间细想。这是比较亏的打法。正确的思路是先把 A、B、C 稳定拿下剩余时间再集中突破 D/E哪怕只写出一半思路分数也比在前面的题上反复试错要高。1.2 不同水平选手的目标分配我给身边朋友的建议一直是一句话参赛前先给自己定清晰的目标而不是“尽量多做题”。刚接触 CF、rating 在 1200 以下目标就是 ABC 题作为额外奖励。重点练读题速度和 A 题的构造敏感性。稳定在 1400-1600 之间目标是 A-B-C 三题稳拿D 题允许自己想 30 分钟超过 30 分钟果断停手。冲 1800 的选手A-C 要在 30 分钟内解决D 题留 60 分钟E 题只作为理论上的冲刺目标不建议牺牲前面题目的正确率去赌。我在打这场的时候给自己定的是“35 分钟拿下 A-C剩下的时间全部给 D/E 里的图论题”。实际比赛里 A 题非常顺利B/C 各卡了一次等到开始碰 E 的时候大概剩 40 分钟时间依然很紧张。这也说明 Div.2 中段题往往比想象中更耗时间时间分配一定要留足冗余。2. A 题 LCM Problem 详解一个构造题的完整推理链2.1 题意与第一反应A 题的题面很简短给定两个正整数 l 和 r要求找两个不同的整数 x、y满足 l ≤ x y ≤ r且 l ≤ lcm(x, y) ≤ r。如果存在就输出 x 和 y不存在就输出 -1 -1。第一反应肯定是暴力枚举但看了一眼数据范围就放弃了。CF 的 A 题很少真的让你枚举它考察的是你能不能抓住一个极端构造。当时我脑子里冒出来的第一个想法是如果 lcm 要落在 [l, r] 里那 y 取 l 的倍数是不是最省事因为 lcm 一定是 x 的倍数如果 x 本身就取 l那么 lcm(l, y) 也一定是 l 的倍数天然满足下界 l ≤ lcm(x, y) 这个条件。这个思路顺着往下走答案很快就浮现出来直接输出 l 和 2l问题是 2l 是否还在 r 以内。也就是说核心判断条件变成了 r 是否大于等于 2l。2.2 关键性质为什么 r ≥ 2l 就是充要条件这道题真正的思维点在证明“r ≥ 2l”不只是充分条件还是必要条件。先看充分性。如果 r ≥ 2l那么取 x ly 2l显然有 l ≤ x y ≤ r。再看 lcm(l, 2l) 2l同样落在区间内构造直接成立。再看必要性。假设存在合法的 x、y那么 lcm(x, y) 必然是 x 的一个倍数而且因为 y xlcm(x, y) 不可能等于 x否则 y 必须整除 x但 y x 时这是不可能的所以 lcm(x, y) 至少是 2x。又因为 x ≥ l所以 lcm(x, y) ≥ 2x ≥ 2l。题目要求 lcm(x, y) ≤ r于是必须有 r ≥ 2l。这一串推理其实是很多 CF 数论题的核心套路构造题先找一组“看起来最极端”的候选再证明这个候选的边界条件就是整个问题的充要条件。这道题里最极端的候选就是 l 本身和它的两倍因为 lcm 至少是较大数的某个倍数两倍已经是最小可能了。2.3 参考实现与边界检查#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin t; while (t--) { long long l, r; cin l r; if (r 2 * l) { cout l 2 * l \n; } else { cout -1 -1 \n; } } return 0; }这里有一个非常容易踩的坑l 和 r 的范围不算大但2 * l 可能超过 int 范围所以在判断条件和输出时都必须用 long long。我见过不少人在这个位置用 int导致大数据直接溢出判错。另外输出多个答案时只要任意合法即可不需要输出字典序最小或其他特殊形式的答案。CF 的构造题一般都会在题面里说明“如果有多个答案输出任意一个”看到这句话就可以放心大胆地用最简构造。2.4 这类 A 题的通吃套路把 Round 1081 A 题的方法扩展开其实能总结出 Div.2 A 题的一类常见套路。很多 A 题看着是数论、看着是模拟实际都是在考察你对“边界状况”的判断。比如类似题还会出现要求两个数满足某种整除关系优先考虑最小公倍数和最大公约数的极端情形。要求在一个区间里找满足某性质的数优先考虑区间的两个端点。要求判断是否存在构造先在边界条件上找反例再设计构造。我在训练的时候养成了一个习惯看到 A 题先问自己三个问题——这个式子的极端取值发生在哪里如果只有一次机会构造我会选什么这个选择是否天然满足一半条件这三个问题过一遍大部分 A 题都能在五分钟内定下思路。3. B/C/D 中段题破题思路卡壳时我用的检查清单3.1 中段题的通用破题检查单说实话写这篇复盘的时候我不打算把 B/C/D 的官方题面逐字复述一遍这类信息网上随时可以查到。我更想分享的是当时在比赛中段我反复使用的破题检查清单。这一套清单对多数 Div.2 的中段题都适用。我把它整理成了一张表遇到卡壳就按顺序自查步骤检查项具体操作1数据范围暗示什么算法n ≤ 1e5 通常排除 O(n²)n ≤ 20 才考虑状态压缩2有没有单调性能排序就先排序能二分就找判定函数3极端输入长什么样全部相同、全部逆序、全是 0/1手算一遍找规律4操作是否有不可逆约束贪心题通常要问“当前这步会不会影响后面的可能性”5能不能转换成图论模型任何“关系”都可以建图连通性、奇偶性、最短路都可能隐藏在里面6答案是否与奇偶性相关路径覆盖、翻转操作、配对问题统统先算奇偶性当时我在 B 题和 C 题上各卡过一次回看都是因为跳过了第 3 步直接凭感觉写代码。后来强迫自己在草稿纸上先跑几组极端小数据明确性质之后再动手效率反而高了。3.2 中段题的“先暴力后优化”策略还有一个我用得很多的方法是“先写一个能跑出正确答案的暴力哪怕复杂度完全不能过”。很多人觉得这是浪费时间实际上非常有用。暴力代码跑小数据能帮你确认性质还能用来对拍。我当时在 C 题上推了一个看似正确的贪心结果样例过了、自己造的数据出错了果断写了个 O(n²) 暴力对拍几分钟就定位到问题所在。具体操作是这样假设你怀疑答案是某种排序后的策略先写一个枚举所有顺序的暴力跑 n ≤ 8 的数据对比你的贪心结果。如果两者不一致说明贪心细节有漏洞如果一致你才有信心继续优化复杂度。对拍这件事在赛后复盘里价值更大。Round 1081 的中段题我复现的时候写了一个暴力版和一个最优版专门去验证“边界处的极端数据”最后发现所有问题几乎都出在两类场景一类是答案边界刚好卡在某个判断条件上另一类是数据里有重复元素时贪心顺序出错。这两个场景在比赛时都不太容易凭肉眼看出来。3.3 中段题的时间盒原则我给自己的 B/C/D 设了一个“时间盒”每道题最多 30 分钟到点还没思路就立刻换题或者转写部分分。这不是逃避而是 CF 的计分规则决定的只要提交通过就有分一道题耗太久会导致后面的题完全没时间。实际操作下来Round 1081 的 B/C 都属于“想通了一个关键点就大幅简化”的类型。中段题的破局点往往藏在一句话条件里比如某个操作只允许做奇数次、某个数组可以重新排列、某个序列的相邻差有特殊性质。当你发现原本复杂的模拟突然可以被一个简单的数学性质简化时基本上就是正确路线的信号。如果你想专门练这种中段题的破局感我建议把每场 Div.2 的 B/C 单独拎出来做限时训练每次只做两题40 分钟做完立刻看 editorial。坚持十场之后你对“题目在暗示哪种算法”的敏感度会明显提升。4. E 题 Moment of Bloom 复盘把路径覆盖变成奇偶性计数4.1 先理解这道题到底在问什么E 题的名字叫 Moment of Bloom我印象非常深因为它是那种“看完题面觉得毫无头绪听懂思路之后拍大腿”的题。题意大致可以概括为给一个无向图每条边一开始都是白色有若干次操作每次操作会给你两个点你需要选择一条连接它们的简单路径把路径上所有边染红。问能否经过所有操作后让所有边都变成红色如果不行最少要修改多少次操作比如改掉某个操作的一个端点才能做到。它的难点在于路径是可以自由选择的你不需要在操作时提前知道所有路径只需要满足最终所有边都红。这一类问题最忌讳的就是一上来想“具体路径怎么走”而是应该把问题抽象成“每条边是否被选中奇数次”。我当时卡了很长时间因为一直在想怎么构造路径。实际上官方的核心观察很关键路径本身不重要的重要的是路径端点给每个点带来的奇偶性。4.2 关键观察路径两端带来的奇偶性先做一个简单的思维实验。如果一条边被选中偶数次它的颜色相当于没变选中奇数次颜色翻转。所以问题就变成了能否为每次操作选一条路径使得图上的每条边被选中的次数都是奇数。接着考虑每个点。一条路径贡献的是一条链链上的每个点度数贡献如下两个端点各贡献 1中间每个点贡献 2。也就是说无论路径怎么选中间点的“贡献次数”都是偶数只有端点的贡献是奇数。现在把所有操作的“端点需求”统计出来每个点作为操作端点的次数记为 cnt[v]真正决定最终状态的只有 cnt[v] 的奇偶性。对于一条路径覆盖问题我们最后看到的效果是——图上所有红边的度数奇偶性必须和所有端点的奇偶性对应。这就是把“路径覆盖”转换成“点的奇偶性匹配”的关键一步。有了这个转换问题一下子简化了一大半。我们不再需要关心每次操作选哪条路只需要确认最终的红色边集合是否在奇偶性上匹配操作端点的需求。4.3 用 DFS 树确定每条边是否必须被选下一步是确定哪些边必须要被选为红色。用 DFS 树来处理这类问题很自然。对无向图跑一遍 DFS可以分成树边和非树边。先只考虑树边。对每个点 v统计以 v 为根的子树中所有操作端点的奇偶性。如果这个子树里操作端点的总数是奇数说明子树内的端点需求“溢出”了必然会有一条边从 v 连向它的父节点且这条边必须被选中奇数次。这个判断用一次子树求和就可以完成。具体实现时令 sub[v] 表示 v 的子树内所有 cnt[x] 的奇偶和。如果 sub[v] 是奇数那么树边 (v, parent[v]) 必须被选中奇数次否则这条树边不用选。这一步其实是树上差分的标准应用很多树上路径统计的问题都长这样。它的精髓在于树边能否被选完全由子树端点决定不需要关心非树边。至于非树边它们在 DFS 树里天然形成环可以作为自由变量来调整一些局部的不平衡所以通常不会影响判定结果的正确性只会在方案构造阶段参与进来。4.4 最少修改次数不匹配点对数的一半接下来是最有意思的部分。按上面的规则我们可以确定一个“理论红边集合”。如果这个集合里每个点的度数奇偶性 cnt[v] 的奇偶性那么问题有解直接按树边非树边构造路径即可。如果不相等说明有些点“不匹配”。一个操作包含两个端点修改一个操作的一个端点会改变两个点的 cnt 值。也就是说一次修改可以同时调整两个点的奇偶性。因此最少修改次数就是所有不匹配点对数量的一半。假如不匹配点的个数是奇数则说明问题无解因为这等价于需求本身自相矛盾。我在复盘时按这个思路重新推了一遍发现整个流程非常顺畅核心步骤是这些统计每个点作为操作端点出现的次数 cnt[v]。用并查集确保每个操作的端点都在同一个连通块内否则无解。跑 DFS 生成森林计算每个子树内的 cnt 奇偶和。根据子树奇偶和确定所有树边是否必须被选。统计不匹配点数 k答案就是 k / 2k 为奇数则无解。核心伪代码可以写成这样vectorint cnt(n 1, 0); for (int i 0; i q; i) { int u, v; cin u v; cnt[u] ^ 1; cnt[v] ^ 1; } // DFS 生成树计算子树奇偶和 functionint(int, int) dfs [](int v, int fa) { int sum cnt[v]; for (int to : adj[v]) { if (to fa usedEdge[v][to]) continue; sum ^ dfs(to, v); } if (fa ! 0 sum 1) { redEdge.push_back({v, fa}); } return sum; };注意这里用异或代替加法因为只需要奇偶性。这个技巧在路径覆盖题里比直接用 int 累加更稳不会溢出思维上也更贴合“奇偶性”这个核心。4.5 这类题的迁移价值E 题最值得学习的地方在于它把“路径”这个几何概念抽象成了“点的奇偶性”再用树结构确定具体边。这个思维模式在 CF 里一点不过时后续很多 Div.2 甚至 Div.1 的图论题都有它的影子。以后再遇到“若干次路径操作最后判断某种状态”的题先问自己几个问题每个操作的端点贡献是什么中间点和端点的区别在哪如果不看具体路径只看奇偶性问题会不会瞬间简化把这些想清楚再去考虑树的形态和具体构造思路会清晰很多。5. 实战踩坑记录与 WA 定位技巧5.1 本场最容易踩的三个坑复盘多了你会发现Div.2 的 WA 往往集中在几个固定位置。Round 1081 这场的典型坑如下常见错误出现位置原因与避免方式int 溢出A 题、E 题统计计数2*l、求和类变量直接开 long long多组数据未重置A 题多测试点场景把声明放入循环内或手动初始化只考虑连通性不考虑奇偶性E 题路径覆盖要先看端点奇偶性再看连通块贪心缺少对极端数据的验证B/C 中段题写代码前先手算全 0、全 1、最大值数据第一个坑我在 A 题里已经提到这里再强调一次CF 的构造和判定类题目边界数据往往就是为 long long 准备的。只要题目数值范围上限是 1e9 级别涉及乘法和倍数关系的判断就一律用 long long不要省。第二个坑更隐蔽。很多 Div.2 的 A 题是多测试点如果你习惯把变量声明在全局每次循环开始前没有清理干净第二次样例就会把上一次结果带进来。我的习惯是尽量把变量声明在 while 循环内部从根上避免残留。第三个坑是 E 题的专属陷阱。判断一个图有没有解最直接的思路是检查连通性但这道题光有连通性不够。每个查询的端点必须连通但所有端点的奇偶性匹配更要一致。漏掉后者的人往往会在大数据 WA 上debug 时又很难从超长输出里找到规律。5.2 WA 之后的系统化定位方法很多新手 WA 之后第一反应是盯着代码一行行读这效率很低。我给自己定的流程是这样的第一步重新读一遍题面。不是从头看到尾而是只找与判断条件相关的句子看看有没有漏掉“输出任意合法答案”“保证输入无重复”“答案可能超过 int”之类不起眼但致命的限制。第二步构造极端数据。专门挑边界条件最小值、最大值、所有值相等、数组长度为 2、空集合等。每个边界跑一遍输出是否合理立刻能看出来。第三步写暴力对拍。已经反复确认没有明显问题时写一个不关心复杂度的暴力解法随机生成小数据和正式代码对比。这一步能定位大约 90% 的隐蔽错误。我当时在 E 题上用这个方法找到了自己忽略的一个点我统计 cnt 时直接把同一个操作的两个端点都异或了但没考虑图中某些点可能只有一次操作到达DFS 子树求和时会漏掉不在任何连通块里的孤立点。后来把 cnt 只统计在图中实际出现的点问题就消失了。5.3 搜索资料时的一个小提醒赛后查题解和讨论时注意一下关键词题目标题里的 round 这个词在编程领域里太容易被别的上下文带偏。比如很多人在查“Codeforces Round 1081”的资料时会混进语言里 round() 函数的讨论PHP、VFP 等语言的 round 函数和竞赛题完全是两回事。搜索时尽量带上 codeforces、div.2、题号这些限定词能省不少时间。另外我强烈建议赛后去看每一题的官方 editorial尤其是 E 题这种偏思维的题。官方题解里给出的“从问题到解法”的推导顺序往往比你看过的任何英文博客都更接近出题人的思维路径。哪怕一开始看不懂也可以先把官方解法里的观察点记录下来过几天再回头做一遍效果比把别人题解全文复制一遍好得多。6. 赛后三件事从 Round 1081 带走的思维升级6.1 现在的 Div.2 已经不只是考“会不会算法模板”打完这场我最大的感受是Div.2 的命题明显在往“思维方法”上靠。A 题如果只是会背 lcm 公式是不够的必须理解“最小可能倍数”这种边界思维E 题更是把路径覆盖、DFS 树、奇偶性这种高级概念组合在一起考察的是建模能力而不是某个现成模板。这种趋势下光刷板子题容易遇到明显的天花板。你需要做的不是记住更多模板而是学会在关键时刻停下来问一句题干里的哪个条件是我没用的这个条件在真实场景下限制了什么把没用的条件找出来往往就是解题的入口。6.2 我推荐继续练的同类题如果你想趁热打铁把与 Round 1081 同类的思维练扎实可以考虑这几个方向的题目关于 LCM 和 GCD 的极端构造题找几场 Div.2 的 A 题优先选题干只有两行的练习快速判断充要条件。关于路径覆盖与奇偶性的图论题凡是题干里出现“将一条路径上的边染色”“翻转路径上的状态”这类描述都值得拿出来按 E 题的思维重新推一遍。关于 DFS 树和非树边自由度的题这类题在 Div.2 的 D/E 题里并不少见关键就是先确定固定部分树边再确认自由部分怎么调整。练的时候不要追求题量要追求“想通每一道题的关键观察”。一道题如果能自己推出来胜过十道题看答案。6.3 我个人这场的最大收获复盘 Round 1081 给我的真正体验是一道题一开始无论如何都看不懂但只要把一个关键问题从“这条路怎么走”换成“每个点需要贡献奇数次还是偶数次”整个人就像换了副眼镜后面的推导全通了。现在我做图论题看到路径两个字第一个动作不再是去枚举路径而是先问这条路径两端的奇偶性是什么中间点能不能被忽略这个习惯就是从这个 E 题开始的。最后再分享一个小建议赛后无论成绩如何都第一时间把每道题的想法写下来哪怕只是两三句“我当时卡在 XX”“后来发现应该先考虑 XX”。这些零散记录过一个月回看会比任何题解都更能反映你的思维盲区也是通往稳定 AC 的最短路。