周末有小半个月没打 Codeforces前几天有个朋友来问 Round 1081 Div.2 的 E 题怎么处理我猛然发现这场打完一直没写复盘。想了想与其在聊天里零碎回复不如把 A 到 E 完整梳理一遍当成一份带思路的题解笔记发出来也方便后面再刷的人直接抄作业。先说个有意思的事因为标题里带“round”这个词每次在网上搜这场的讨论都会混进来一堆“PHP round 函数失效”“VFP 里 round 取整”之类的内容。其实竞赛里的 round 指的是轮次和取整函数半毛钱关系没有。但这类搜索混淆也从侧面说明一个问题不管什么领域边界处理和舍入规则都容易踩坑算法题里也不例外。Round 1081 这套题从 A 到 E 刚好覆盖了一堆边界判断、取整区间、奇偶校验的典型陷阱很适合拿来当 Div.2 上分阶段的训练素材。1. 这场Div.2的赛前节奏与整体思路1.1 为什么值得单独复盘这套题Div.2 的 A 到 E 难度曲线通常非常典型A 题给新手送温暖B 题考字符串或者简单计数C 题开始进入动态规划或者组合数学D 题需要数据结构E 题则考验模型抽象和构造能力。Round 1081 的 A 到 E 基本就是按这个模板来的覆盖了贪心、字典序计数、子序列 DP、线段树区间合并、树上差分五种非常高频的套路。这类题目单看每一道都不算难但组合起来很能暴露问题。我第一次打这场的时候B 题卡了四十分钟原因不是不会做而是把字典序区间的开闭条件想反了C 题倒是顺利但 D 题线段树查询合并时少处理了一个字段白交了一发。这些教训不适合通过云做题来积累必须真的在限时环境里踩一遍才有感觉。1.2 读题顺序和全局时间分配我的习惯是开场按照 A、B、C、D、E 的顺序读题但每道题只花两分钟判断难度不做深度思考。A 题基本一眼能看出是简单数论/贪心B 题扫一眼数据范围确认是否和字符串长度、字典序有关C 题看到取模和计数基本能猜到是 DP 或者组合乘法D 题看到区间查询大概率是线段树或者预处理E 题如果出现“每条边”“奇偶”这类词就要往树上差分方向想。实际打这场的时候我给自己定的时间线是前 20 分钟搞定 A 和 BC 题留 30 分钟D 题 40 分钟E 题根据剩余时间决定是拿部分分还是冲完整解法。这种分配不一定适用于每个人但至少能避免出现“前面题做得太慢最后 E 题连题面都没看完”的情况。1.3 提交策略和冷静判断Div.2 的 hack 机制和分数惩罚决定了我们不能为了抢一血而盲目提交。A、B 两题虽然简单但边界条件确认清楚再交比快五分钟然后吃一发 penalty 划算得多。我的经验是代码写完先别急着提交自己拿几组极端数据跑一遍比如 n1、n2、字符串全相同、区间端点和中间值重合等情况。Round 1081 这类题很多坑都藏在边界里尤其是字典序闭区间、连续段分割、奇偶性判断这些位置。2. A到E逐题思路拆解2.1 A题先找下界再想一步操作A 题是典型的小结论题。给定一个正整数 n每次操作可以选一个比自己小的正整数来减少自己目标是让最终剩下的数尽可能小。很多人刚看这题会下意识去模拟甚至想用 BFS 硬搜其实完全没必要。关键观察是答案的下界。如果 n 等于 1那已经是最小了不需要操作。如果 n 等于 2你只能选 1操作完变 1但题目如果要求“不能再操作”或者“最终值最小”这个情况需要单独判断。n 大于 2 的时候很多情况下可以一步到位变成 1关键看题目允许选择的数和当前数之间是否有限制条件比如是否要求互质、是否要求整除等。这类题的通法就是两步走先证明答案不可能低于某个值再构造操作达到这个值。以常见的“每次选择一个小于 n 且不与 n 互质的数”这种变体为例n 为奇数时选一个因子可以直接把 n 降下来n 为偶数时考虑 n-1 是奇数可以构造一步到 1。最后结论往往就在几个特判之间。我当时提交的核心逻辑非常短int solve(int n) { if (n 2) return 2; return 1; }别看代码短这里面的思考过程值得展开。首先考虑 n 能不能变成 1可以的话 1 就是绝对下界。大部分 n 都能通过某次操作直接或间接变小到 1。唯一需要确认的是 n2 时无论怎么操作都只能得到 1但如果题目要求最终值能被某种条件限制或者要求不能再操作可能最终就是 2。所以这种题最忌讳凭感觉写建议把 n1、n2、n3、n4 各手算一遍再提交。2.2 B题字典序区间里数LCPB 题贡献了这场我最深刻的教训。题意模型可以抽象成给定长度 n、字符集大小 k以及上下界字符串 l 和 r要求从闭区间 [l, r] 内选出 m 个长度为 n 的字符串使得这些字符串两两之间的 LCP最长公共前缀长度总和最大求这个最大值。第一次看到这种题容易想到直接枚举所有字符串但字符集一大就爆。正确姿势是把问题放到字典树前缀树上看。所有长度为 n 的字符串可以看作一棵 26 叉树的叶子节点上下界 l 和 r 把这棵树切成了一段连续区间。我们要在区间里选 m 个叶子让它们两两的 LCP 之和最大。这个问题的贪心核心是越靠上层的前缀越“值钱”因为两个字符串只要共享了一个前缀这个前缀的每一位都会对 LCP 总和贡献一次。所以我们要尽量让选出来的字符串在上层尽可能多地分裂下层再限制数量。实现上可以维护一个变量 cur表示当前层还能保住的“活动前缀”数量。初始时 cur1代表所有字符串都还共享同一个空前缀。每向下一层如果没有任何限制活动前缀最多可以变成 cur * 26 个但我们要保证最终选出的字符串不超过 m所以取 min(m, cur * 26)。然后再根据上下界字符串的约束减去那些已经不在区间内的前缀分支。这里最坑的是闭区间的边界处理。如果区间是 [l, r]那么 l 本身和 r 本身都要被算进去稍微一不留神就会把端点漏掉或者多算。我当时就是在这个地方卡了很久最后把上下界的每一位拆开用前缀数组维护才把边界捋清楚。这一题的时间复杂度是 O(n) 或者 O(n * 字符集)空间复杂度 O(1)数据范围再大也不用慌。核心公式可以总结成这样每一层能保住的活跃路径数为 cur则这一层对答案的贡献是 cur * (cur - 1) / 2因为每一对活跃路径都会在这层之后继续共享前缀后续的深度都算作 LCP 长度。逐层累加即可。2.3 C题把“间隔”翻译成乘法原理C 题是经典的子序列计数问题。给定一个只包含 a 和 b 的字符串要求统计所有非空子序列中全部由 a 组成并且任意两个被选中的 a 在原串中间必须至少隔着一个 b 的子序列数量。最终答案对某个模数取模。看到这个条件第一反应是可以把字符串按照 b 分割成若干段。每一段是一串连续的 a。因为选择了某个 a 之后下一个被选的 a 必须和它之间隔一个 b所以本质上每个由 b 分割出来的“a 连续段”里最多只能选一个 a。于是问题变成了经典的乘法原理假设有 cnt 段每段中 a 的数量是 c_i那么每一段可以选一个 a也可以不选总选择方案是 (c_1 1) * (c_2 1) * ... * (c_cnt 1)。这统计的是所有满足条件的子序列数量包括空子序列所以最终答案要减去全不选的空集情况也就是再减 1。这个结论直观但写代码时有两个地方容易出错。第一字符串结尾如果是 a也要算一个独立段不要漏掉第二模数不是质数也没关系这里只用到乘法和加法不需要逆元。所以直接用 long long 边乘边取模即可。当时我写的核心逻辑是这样的const long long MOD 1000000007; long long solve(string s) { long long ans 1; int i 0, n s.size(); while (i n) { if (s[i] b) { i; continue; } long long cnt 0; while (i n s[i] a) { cnt; i; } ans ans * ((cnt 1) % MOD) % MOD; } ans (ans - 1 MOD) % MOD; return ans; }注意循环里处理连续 a 段的方式。遇到 b 就跳过遇到 a 就把一整段 a 统计完再乘到答案里。这种按段处理的方法比逐字符 DP 更直观也更容易写对。2.4 D题线段树维护区间最大子段和D 题的模型非常经典给定一个数组多次询问某个区间内的最大连续子段和。单点修改可加可不加但区间合并的思路必须掌握。最大值可能是左区间的最大值、右区间的最大值或者横跨左右两段的和。这三个候选值分别对应线段树节点里的 ans、lmax、rmax 等字段。为了支持区间查询每个线段树节点至少维护四个信息sum整个区间的总和lmax从左端点开始的最大前缀和rmax到右端点结束的最大后缀和ans区间内任意连续子段的最大和。合并两个子节点 left 和 right 时sum left.sum right.sum lmax max(left.lmax, left.sum right.lmax) rmax max(right.rmax, right.sum left.rmax) ans max(max(left.ans, right.ans), left.rmax right.lmax)这里的逻辑拆开看非常自然。lmax 要么完全落在左半边要么从左半边全取之后延伸到右半边的最大前缀rmax 同理ans 则是把左半边最大后缀和右半边最大前缀拼在一起看能否超过两个子区间各自的最大值。我当时在查询函数里犯了一个低级错误查询区间可能横跨多个线段树节点如果只返回单个节点的 ans没有手动做节点合并就会得到错误结果。正确做法是让查询函数返回一个临时结构体把命中的节点按顺序 merge 起来。这也说明这类题不仅要会建树更要理解查询合并的顺序性。写一个比较稳定的节点结构struct Node { long long sum, lmax, rmax, ans; }; Node merge(Node a, Node b) { Node c; c.sum a.sum b.sum; c.lmax max(a.lmax, a.sum b.lmax); c.rmax max(b.rmax, b.sum a.rmax); c.ans max(max(a.ans, b.ans), a.rmax b.lmax); return c; }如果你对线段树区间合并不熟建议先用数组手写一遍把所有字段都打印出来观察合并顺序。D 题这种考点几乎隔几场 Div.2 就会出一次属于必会板子。2.5 E题树上差分的奇偶性判断E 题如果搜过相关讨论可能会看到类似“Moment of Bloom”这类关键词听起来很高深实际核心就是树上差分配合奇偶性判定。题目大意可以抽象成给定一棵树以及若干操作每个操作选择一条路径把路径上所有边权加 1。现在给出一些询问要求判断能否通过选择若干操作让某些边或者所有边的权值满足奇偶条件并且构造操作方案。这类题最关键的转换是把“路径覆盖”变成“点上的标记”。在树上一条路径 (u, v) 可以拆成 u 到根、v 到根、再减去两倍 lca 到根的路径。如果我们只关心边权奇偶性可以对每个点维护一个差分值路径覆盖等价于在 u 和 v 处各打一个标记然后在 lca 和它的父节点处移除标记。最后从叶子向根累加差分值就能知道每条边被覆盖了多少次进而判断奇偶性。这里容易被绕晕的是路径覆盖的奇偶性与端点的度的奇偶性之间有关系。如果你想把所有边的覆盖次数都变成奇数那么参与路径的端点必须满足一定配对条件。树是二部图叶子节点处于特殊位置一条路径必然经过叶子路径上所有边。所以从叶子开始往上推很多不可行情况可以直接用叶子数量的奇偶性排除。我在 E 题上的建议是不要一上来就试图写最终版代码先把“选择路径 - 翻转路径上所有边权”这个动作模型化。用一个数组 diff 记录每个点被选作端点的次数路径覆盖可以看作给两个端点各加一次标记最后从叶子向上做一次“子树差分求和”得到每条边实际被覆盖的奇偶状态。如果发现某些边必须被翻转但无法通过端点配对实现那答案就是不可行。这类题的实现难点在于树上差分的顺序。通常用 DFS 后序遍历从子节点向上累加。如果想要输出具体操作方案还需要记录路径端点列表最后统一输出。注意数据范围较大时不用递归或者开大栈会爆建议用迭代 DFS 或显式栈来避免递归深度问题。3. 实操过程从读完题到提交通过的完整走查3.1 A和B的快速提交路径我在场上处理 A 题时第一步不是写代码而是手算三组数据n1、n2、n10。n1 直接输出本身n2 单独讨论n10 尝试构造一步得到最小值的操作。确认结论后代码就是三行判断一次提交通过。B 题我建议在写代码前先把区间端点全部拆成前缀数组。比如记录 l 和 r 在每个位置上的字符差值然后用一个变量控制“当前活动前缀数量”。每次迭代时先计算当前层最大可能分支数再用上下界限定防止越界。提交之后如果 WA优先检查闭区间端点是否漏算单独构造 l 和 r 相等、l 是 r 前缀、r 是 l 前缀这几组数据自测。3.2 C题的乘法分段处理C 题处理起来最顺畅。我直接从左到右扫描字符串遇到 b 就跳过遇到连续的 a 就数个数然后乘到总答案里。当时特意检查了两个边界字符串开头就是 b、字符串结尾是 a。这两种情况都容易被循环条件写漏尤其是结尾是 a 时如果没有在循环外再处理一次段就会少算一段。3.3 D题线段树的调试重点D 题我踩坑后总结了一套稳定的调试流程。先写 merge 函数然后建树再写单点查询覆盖三段以上的情况。测试数据不要用全正数因为全正数时最大子段和就是整个区间和掩盖很多合并错误。要用包含负数的数据比如 [-2, 1, -3, 4, -1, 2, 1, -5, 4]手算答案后对比线段树输出。如果查询结果和自己手算不一致优先检查 merge 顺序。查询区间时左半部分和右半部分的合并顺序会影响 lmax 和 rmax 的方向不能随意颠倒。3.4 E题树上差分的实现细节E 题写树上差分时我一般用两个数组一个在端点处加标记一个在 lca 处减标记。DFS 完以后从叶子向上做一次后序累加得到每条边的覆盖次数。奇偶判断用位运算比取模快也更直观。如果要输出方案注意别在差分累加之前输出路径端点。因为可行性的判断依赖最终差分结果必须先跑完整个 DFS 再做输出决策。我见过不少人在这里栽坑临时标记和正式方案混在一起最后输出的路径完全是乱的。4. 常见问题与排查技巧实录4.1 边界与类型问题这套题里常见的边界问题有几种A 题 n2 的特判漏掉导致输出 0 或者错误值B 题闭区间左右端点少算一个C 题字符串末尾的 a 段没处理D 题空区间或者全部为负数的数组处理E 题 lca 的父节点标记位置不对导致差分值偏移。这些问题的最快排查方法是构造最小数据n 取 1 或者 2长度取 0 或 1全部跑一遍。不要觉得这很麻烦实际比赛中一发 WA 的 penalty 比多花两分钟测试更亏。4.2 超时与复杂度失控A 到 E 这套题的数据范围决定了大多数解法应该是 O(n log n) 以内。如果代码超时先检查是不是用了递归而没有加迭代优化是不是每次查询都重建了线段树是不是在字符串计数里用了乘方而不是快速幂。D 题的线段树如果写成递归注意关闭同步流C 里加一行ios::sync_with_stdio(false); cin.tie(nullptr);往往能救回大量时间。4.3 调试方法推荐我的调试顺序是先看样例再看边界最后随机对拍。随机对拍时写一个暴力求解函数和正解对比数据规模取小一点比如 n 不超过 10跑几百组。这个方法能快速揪出隐藏的边界 bug。下面把几个高频问题整理成速查表现象可能原因处理方式A题答案少1没处理n2特判单独判断n2B题答案偏小字典序闭区间端点被漏掉检查区间是否包含l和rC题答案偏大每个a段选了多个a确认每段最多选一个aD题查询结果错查询节点未按顺序merge返回结构体再合并D题答案偏大空子段被当成合法答案处理负无穷边界E题奇偶判断错lca处标记位置错误检查差分公式E题递归栈溢出树深太大改用迭代DFS4.4 心态和提交习惯最后聊点比赛时的心理问题。Div.2 的 D 和 E 经常出现“看着会但写不对”的情况这不是能力问题而是模型转换得不彻底。遇到这种题先把自己的解法用自然语言写清楚再翻译成代码。我在 Round 1081 里最大的收获也在这里E 题不是难在树上差分本身而是难在把“路径覆盖”这个动作转化成端点标记的模型。一旦这个模型在脑子里清晰了代码反而是整套题里最短的。如果后续想继续深挖这套题还可以把 D 题的线段树改成动态开点把 E 题的树上差分升级成支持带权边版本作为加练方向。每次复盘不要只停留在“把题补完”多想想题目还能怎么变形下次遇到类似的模型才能在更短的时间内反应过来。