昨晚把 AtCoder Weekday Contest 0014 Beta 打完整场刚开始看到 Beta 这个后缀就知道题目不会按套路出牌。五道题从 A 到 E难度梯度比普通周赛要陡不少A、B 属于入场券C 是典型的二分答案D 开始上强度E 不仅考最小生成树还要求判断“唯一性”。整场打下来最大的感受是这周题目并不在炫算法模板而是反复在边界条件和“你以为对其实不对”的地方埋雷。这篇文章不打算只贴代码。我会把每道题从读题、想通到写码的完整链路拆开讲说明每个关键选择为什么这么做、哪些细节容易翻车、复杂度靠不靠谱。不管你是正在备战 ABC、想把难度往上探一探还是纯粹想拿几道题练手这套复盘都值得对着过一遍。1. 赛前复盘题面难度分布与开题策略1.1 A-E 题目速览与考点先把五道题的考察内容和标签整理成一张表后面每道题再展开。题号核心考察点难度定位建议用时A分支判断、输入处理签到3 分钟B哈希计数、反转串配对入门8 分钟C二分答案、贪心 check主流20 分钟D倍数枚举、容斥计数进阶35 分钟E最小生成树唯一性、并查集分组压轴35 分钟Beta 赛最明显的特点就是“难度跳跃感”。A 和 B 基本是白送但 C 的二分答案如果一开始没看出来很容易绕到 DP 上去白白浪费时间。D 题则是对数论敏感度的一次体检E 题代码量不大但要把唯一性判断想透也没那么简单。由于是限时赛我的策略是开场先扫一眼所有题面尤其注意 D、E 的数据范围。数据范围往往直接暗示解法方向比如看到 N 和值域都到 3×10^5基本能猜到 D 的复杂度模型应该是 O(n log n) 级别的枚举而不是背包。1.2 时间分配与卡题处理我在这次比赛里的实际节奏是前 10 分钟写完 A、B然后直接进 C。C 定位是“必须拿下”的中档题给了自己 20 分钟上限。D 题读完第一反应是“子集计数”下意识想枚举子集马上被数据范围拦住于是转去想容斥前前后后花了大约半小时还是被绕进一个细节里。我选择先跳过 D把最后半小时留给 E。事实证明这个决定是对的——E 的框架我在 10 分钟内就搭好剩下时间回头补 D 的容斥式用草稿纸手算了两组样例确认无误才真正写代码。这里有个经验比赛时卡题超过 20 分钟最合理的动作不是继续死磕而是立刻换题。尤其 Beta 赛的难度分布常有“山峰”D 卡住不代表 E 也卡先做灵活的题目能稳住心态也让大脑换个频道。赛后复盘时我发现D 卡住的点其实只是“统计倍数集合”的枚举方向没理顺这说明开题阶段先判断复杂度模型多么重要。2. A 题与 B 题把送分题稳稳装进口袋2.1 A 题题解纯分支判断A 题的题面很精简给两个整数 X、Y一个操作符 op只可能是 或 *再给一个整数 Z。如果 XYZ输出 add如果 X*YZ输出 mul否则输出 none。保证 add 和 mul 不会同时成立。这题没有任何算法含量考的就是输入处理和分支书写的干净程度。我第一次提交差点在 op 的读入上踩坑如果用 cin 读 int 之后再读 charchar 变量会把上一行末尾的换行符读进去。C 里最稳妥的方式是直接char op; cin op;它天然跳过空白字符。Python 则要input().strip()后再取内容不然空字符串会带来不必要的麻烦。参考代码Pythonx, y map(int, input().split()) op input().strip() z int(input()) if op : print(add if x y z else none) else: print(mul if x * y z else none)参考代码C#include bits/stdc.h using namespace std; int main() { int x, y, z; char op; cin x y; cin op; cin z; cout (op ? (x y z ? add : none) : (x * y z ? mul : none)) \n; return 0; }这段代码最需要强调的是输出字符串必须和题面完全一致。比赛里不少人在签到题上因为输出Add或None拿不到分纯属可惜。2.2 B 题题解反转串配对计数B 题给定 N 个字符串字符串内容由小写字母组成可能有重复。要统计有多少个无序下标对 (i, j)i j满足第 i 个字符串的反转恰好等于第 j 个字符串。比如ab和ba是一对aba和aba也可以是一对前提是两个索引上的字符串都等于同一个回文串。最直接的双重循环复杂度 O(N^2 × 串长)N 到 2×10^5 的时候直接爆炸。正确做法是线性扫描 哈希计数。核心逻辑是每读到一个新字符串 s先看它的反转rev(s)之前出现过几次把那个次数加到答案里然后再把 s 自己的出现次数加一。这个“先查后加”的顺序非常关键它保证每个配对只被统计一次不会拿当前索引和自己配对。用回文串举个例子如果aba出现 3 次那么第 1 次读到aba时aba的计数是 0ans 加 0第 2 次读到ans 加 1第 3 次读到ans 加 2总配对数是 3正好是 C(3, 2)。如果先把 s 加入计数再查询回文串就会出现自己和自己配对的错误。参考代码Pythonfrom collections import Counter n int(input()) cnt Counter() ans 0 for _ in range(n): s input().strip() ans cnt[s[::-1]] cnt[s] 1 print(ans)参考代码C#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; unordered_mapstring, int cnt; long long ans 0; for (int i 0; i n; i) { string s; cin s; string t s; reverse(t.begin(), t.end()); ans cnt[t]; cnt[s]; } cout ans \n; return 0; }2.3 两题共用的输入与边界细节这两道题在 AtCoder 系的比赛里属于必拿分题但细节依然值得列一下B 题允许重复字符串所以不能用unordered_set去重必须用计数 map 或字典。反转串和原串相同时配对数量按组合数计算“先查后加”能自动处理。答案用long longN 最大 2×10^5 时配对数量可能达到约 2×10^10int 会溢出。比赛里的输入字符串长度可能很大如果用 Python 的reverse切片会创建新字符串内存稍微多一点但 N 和总长度可控时没问题。我第二次打这类题时基本不看样例直接写因为这个模式太经典所有需要“无序配对”的统计都可以用“边查边加”的计数器替代双重循环。3. C 题二分答案解决“最大段和最小化”3.1 题目模型与单调性判断C 题的题面可以概括为给定一个长度为 N 的正整数数组 A要求把数组切成恰好 K 个连续非空块求所有块中元素和的最大值的最小值。N 和 K 最大都是 2×10^5A_i 最大 10^9。看到“最大值最小”这种描述第一反应就应该是二分答案。为什么因为答案 X 的可行性具备单调性如果 X 可以做到那么任何比 X 更大的值也一定可以做到如果 X 做不到那么任何比 X 更小的值也一定做不到。有了单调性就能把“最优解问题”变成“判定问题”。具体地说我们二分一个候选值 limit检查能不能用不超过 K 段让每一段的和都不超过 limit。如果可行说明答案不超过 limit收紧右边界否则答案一定大于 limit收紧左边界。3.2 贪心 check 的写法判定函数是这题的灵魂。从左到右扫描数组维护当前段的累加和 cur遇到新元素时先判断cur v是否超过 limit。如果没超过就把 v 放进当前段否则必须另起一段段数加一cur 重置为 v。为什么要这样贪因为在所有元素都是正数的情况下每一段“尽量多装”一定不会让段数变多。如果最优解在某个位置提前切开了而我们可以把它和后面的元素合并合并后段和增大但不超过 limit段数只会减少或不变。所以贪心得到的是最少段数。这里有一个新手容易写错的点新开一段时cur v而不是cur 0。因为 v 已经属于新的一段如果 cur 置 0下一次再累加会漏掉 v。另外如果数组里存在单个元素本身就大于 limit那么无论怎么切都不可能合法。我在 check 函数开头直接判断v limit就返回 False。参考代码Pythondef can(limit): seg_cnt 1 cur_sum 0 for v in a: if v limit: return False if cur_sum v limit: seg_cnt 1 cur_sum v if seg_cnt k: return False else: cur_sum v return seg_cnt k lo max(a) hi sum(a) while lo hi: mid (lo hi) // 2 if can(mid): hi mid else: lo mid 1 print(lo)3.3 二分边界与代码实现下界为什么是max(a)因为切成单块时任何一块的和至少等于其中最大的元素不可能小于它。上界为什么是sum(a)因为切成一块时段和就是全部元素之和这个值一定是可行方案。二分循环采用常见的lo hi写法mid (lo hi) // 2判断可行就把 hi 收到 mid不可行就把 lo 收到 mid 1。这个写法最终会收敛到第一个可行值。手动推一组边界数组[7, 2, 5]K 2。max(a)7sum(a)14。mid10 时贪心切出来是[7]和[2,5]段数 2可行hi10。mid8 时[7]和[2,5]两段和分别是 7、7也可行hi8。mid7 时[7]段和 7257还是可行hi7。答案 7。这里正好卡在max(a)上说明下界设成 max(a) 不是保守而是必须。复杂度是 O(N log(sumA))在 N2×10^5、sumA2×10^14 的规模下完全跑得动。4. D 题倍数容斥统计 gcd1 子集4.1 直接枚举子集的死路D 题的题面是给 N 个正整数 A_i统计有多少个非空子集满足子集内所有元素的最大公约数恰好为 1。答案对 998244353 取模。N 和 A_i 的最大值都到 3×10^5。如果直接枚举子集2^N 直接不可能。第一步想法是 DP按 gcd 作为状态计数理论上可以做到 O(N × 值域)但值域 3×10^5N 同样大乘起来是 9×10^10跑不动。所以需要换角度不从“子集构造”出发而是从“约数集合”出发。4.2 从“倍数集合”到容斥定义cnt[x]表示数组中有多少个元素是 x 的倍数。如果一个子集里所有元素都是 x 的倍数那么这个子集的 gcd 一定也是 x 的倍数。这类子集有多少个如果数量是 c那么非空子集数量为2^c - 1。把这个值记为f[x]。举个例子数组里有 4 个偶数那么“所有元素都是 2 的倍数”的非空子集数就是2^4 - 1 15这 15 个子集的 gcd 可能是 2、4、6 等等但一定都是 2 的倍数。现在定义g[x]表示“所有元素 gcd 恰好为 x”的子集数量。根据上面的关系f[x]应该等于所有g[d]的和其中 d 是 x 的倍数。于是得到f[x] g[x] g[2x] g[3x] ...从大到小枚举 x就可以逐个反推出g[x]g[x] f[x] - sum(g[d])d 为 x 的所有大于 x 的倍数。最终答案就是g[1]。4.3 实现细节与复杂度先统计每个数值的出现次数freq[v]然后对每个 x 枚举它的倍数 y累加freq[y]得到cnt[x]。这一步的总复杂度是调和级数L/1 L/2 ... L/L ≈ L log L在 L3×10^5 时大约 360 万次操作非常快。预处理 2 的幂次数组pow2[i] pow2[i-1] * 2 % MOD用于快速计算2^cnt - 1。参考代码PythonMOD 998244353 N int(input()) A list(map(int, input().split())) L max(A) freq [0] * (L 1) for v in A: freq[v] 1 cnt [0] * (L 1) for x in range(1, L 1): for y in range(x, L 1, x): cnt[x] freq[y] pow2 [1] * (N 1) for i in range(1, N 1): pow2[i] pow2[i - 1] * 2 % MOD f [0] * (L 1) g [0] * (L 1) for x in range(1, L 1): f[x] (pow2[cnt[x]] - 1) % MOD for x in range(L, 0, -1): g[x] f[x] for d in range(2 * x, L 1, x): g[x] (g[x] - g[d]) % MOD print(g[1] % MOD)写这段代码时有三个必须留意的点减法取模后可能变成负数所以要% MOD调整到正数区间。cnt[x]的枚举方向是“统计每个 x 的倍数”不是“统计每个数的因子”这个方向别写反。pow2数组长度是 N1因为cnt[x]最大就是 N。在赛场上手算样例[2, 3, 6]可以快速验证只有子集[2,3]和[2,3,6]的 gcd 为 1答案是 2。照着代码走一遍能确认容斥过程没有绕乱。5. E 题唯一最小生成树的判定5.1 问题转化与判断依据E 题的题面很直接给一个 N 个点、M 条边的无向连通图每条边有权值。判断这个图的最小生成树是否唯一。如果唯一输出Unique否则输出Not Unique。如果只求最小生成树的总权重裸 Kruskal 就够了。但“唯一性”需要额外处理。一个非常经典的结论是如果存在两种不同的最小生成树方案那么一定有某条权值相同的边可以在最小生成树里被替换成另一条同权边且总权重不变。因此唯一性判断可以聚焦到“同一权值组”的边上。具体方法不是常见的“先求 MST再求次小 MST”而是把 Kruskal 过程按权值分组对于所有权值相同的边统一先做一次联通性检查统计“有资格进入 MST”的候选边数再真正执行合并统计实际被合并的边数。如果候选边数大于实际合并边数说明这一组内存在多余的替代选择MST 不唯一。5.2 同权边分组克鲁斯卡尔为什么必须先统计候选边数再执行合并因为并查集合并是动态的。如果边 a 和边 b 是同权平行边连接同一对点先合并 a 之后b 的两个端点已经在同一集合里此时再检查 b 会发现它无法合并导致候选数少算一条唯一性判断就出错。正确顺序是当前权值组里的所有边在尚未进行这一组任何合并时各自检查端点是否属于不同连通块。满足条件的就是候选边。随后执行真正的合并把能够合并的边都合并进去并累加生成树权值。这里“能够合并”的边数就是这一组里必须连接不同连通块的边数它同时等于连通块减少的数量。候选数大于合并数时说明有一些边虽然也连接着不同的连通块但因为先被其他边合并了而没能选上这正好说明存在多种选法。5.3 实现细节与复杂度参考代码Pythonclass DSU: def __init__(self, n): self.fa list(range(n 1)) def find(self, x): while self.fa[x] ! x: self.fa[x] self.fa[self.fa[x]] x self.fa[x] return x def union(self, a, b): a self.find(a) b self.find(b) if a b: return False self.fa[a] b return True n, m map(int, input().split()) edges [] for _ in range(m): u, v, w map(int, input().split()) edges.append((w, u, v)) edges.sort() dsu DSU(n) possible True i 0 while i m: j i while j m and edges[j][0] edges[i][0]: j 1 candidate 0 for k in range(i, j): w, u, v edges[k] if dsu.find(u) ! dsu.find(v): candidate 1 merged 0 for k in range(i, j): w, u, v edges[k] if dsu.union(u, v): merged 1 if candidate merged: possible False i j print(Unique if possible else Not Unique)实现里有一个小技巧candidate的统计不依赖实际合并顺序所以第一遍循环只是为了“点数”。第二遍循环才真正修改并查集。如果candidate merged没必要立刻退出直接标记后继续后续组也没问题因为后续判断不依赖这个标记只是最终输出前用一下。从复杂度看排序是 O(M log M)扫描部分每组每条边最多看两遍并查集带路径压缩后接近 O(M α(N))整体足够应对 2×10^5 级别的数据。这题让我联想到之前打某场练习赛时遇到的一个变体不是判断 MST 是否唯一而是问“有多少条边可能出现在某个 MST 中”。处理思路本质上相同仍然要分组统计候选边。能把唯一性判断吃透那道变体基本是送分。6. 现场翻车点与自查清单6.1 高频翻车点速查表这场打下来结合同场几位选手赛后聊到的失分点我整理了一张高频翻车对照表位置典型错误正确做法A 题用getchar()读运算符吃进换行用cin op或input().strip()B 题用set去重丢失重复字符串用计数 dict/map先查后加B 题ans 开 int溢出变负数用long longC 题新段开始时cur 0漏掉当前元素新段重置为当前元素值C 题下界设成 0 或 1下界应为max(a)D 题减法取模后为负手动加 MOD 后再取模D 题把“统计倍数”写成“统计因子”内层循环range(x, L1, x)枚举倍数E 题同权组内边先合并再统计候选边先整体统计候选边再执行合并6.2 二分与取模两个典型坑C 题的二分最容易出现死循环。如果写成lo hi且判断可行时lo mid那在只剩两个元素时会因为 mid 等于 lo 而卡住。本次 C 题我采用hi mid与lo mid 1的配对保证 mid 向下取整时不会原地踏步。这个配对在绝大多数“求最小可行值”的问题里都能通用。D 题的取模则提醒我Python 里% MOD会保证结果非负但 C 里如果写成(g[x] - g[d]) % MOD负数的模仍然是负值输出就会错。最稳妥的写法是g[x] (g[x] - g[d] MOD) % MOD虽然稍微多运算一次但安全。6.3 赛后复盘建议比赛结束不等于任务完成。我通常会给每道题建一个小档案记录四件事第一第一眼看到题面时想到了什么算法第二为什么走了弯路第三正确解法里最关键的那一步是什么第四如果下次再遇到相同模型第一步应该做什么。以这场为例C 题的关键是看到“最大值最小”立刻转二分D 题的关键是意识到值域小适合枚举倍数E 题的关键是并查集分组处理同权边。这些“关键一步”才是赛后最有价值的沉淀。单纯把 AC 代码塞进收藏夹下次遇到变体还是不会。我也建议读者别只看题解自己独立把每道题从零写一遍然后故意制造几个常见 bug 运行输出比如把 B 题 counter 顺序换一下、把 E 题合并顺序调一下看看结果差在哪。亲手踩过坑之后印象远比读十遍题解深刻。最后说一点个人体会Beta 周赛题的实验性更强偶尔会考一些陈旧但经典的模型。这类比赛最大的收获不是排名而是让你发现自己在思维习惯上的盲区。我这次最值的一笔投入就是花十几分钟把 E 题的同权边分组逻辑彻底推通了。这个结论以后遇到最小生成树相关的边计数题还能继续复用属于打一场比赛赚三道题的知识迁移。 
长河君 · 2026/10/14 23:11:49 · 阅读 1.2k AtCoder Beta赛全题复盘：二分答案与MST唯一性判定实战
昨晚把 AtCoder Weekday Contest 0014 Beta 打完整场刚开始看到 Beta 这个后缀就知道题目不会按套路出牌。五道题从 A 到 E难度梯度比普通周赛要陡不少A、B 属于入场券C 是典型的二分答案D 开始上强度E 不仅考最小生成树还要求判断“唯一性”。整场打下来最大的感受是这周题目并不在炫算法模板而是反复在边界条件和“你以为对其实不对”的地方埋雷。这篇文章不打算只贴代码。我会把每道题从读题、想通到写码的完整链路拆开讲说明每个关键选择为什么这么做、哪些细节容易翻车、复杂度靠不靠谱。不管你是正在备战 ABC、想把难度往上探一探还是纯粹想拿几道题练手这套复盘都值得对着过一遍。1. 赛前复盘题面难度分布与开题策略1.1 A-E 题目速览与考点先把五道题的考察内容和标签整理成一张表后面每道题再展开。题号核心考察点难度定位建议用时A分支判断、输入处理签到3 分钟B哈希计数、反转串配对入门8 分钟C二分答案、贪心 check主流20 分钟D倍数枚举、容斥计数进阶35 分钟E最小生成树唯一性、并查集分组压轴35 分钟Beta 赛最明显的特点就是“难度跳跃感”。A 和 B 基本是白送但 C 的二分答案如果一开始没看出来很容易绕到 DP 上去白白浪费时间。D 题则是对数论敏感度的一次体检E 题代码量不大但要把唯一性判断想透也没那么简单。由于是限时赛我的策略是开场先扫一眼所有题面尤其注意 D、E 的数据范围。数据范围往往直接暗示解法方向比如看到 N 和值域都到 3×10^5基本能猜到 D 的复杂度模型应该是 O(n log n) 级别的枚举而不是背包。1.2 时间分配与卡题处理我在这次比赛里的实际节奏是前 10 分钟写完 A、B然后直接进 C。C 定位是“必须拿下”的中档题给了自己 20 分钟上限。D 题读完第一反应是“子集计数”下意识想枚举子集马上被数据范围拦住于是转去想容斥前前后后花了大约半小时还是被绕进一个细节里。我选择先跳过 D把最后半小时留给 E。事实证明这个决定是对的——E 的框架我在 10 分钟内就搭好剩下时间回头补 D 的容斥式用草稿纸手算了两组样例确认无误才真正写代码。这里有个经验比赛时卡题超过 20 分钟最合理的动作不是继续死磕而是立刻换题。尤其 Beta 赛的难度分布常有“山峰”D 卡住不代表 E 也卡先做灵活的题目能稳住心态也让大脑换个频道。赛后复盘时我发现D 卡住的点其实只是“统计倍数集合”的枚举方向没理顺这说明开题阶段先判断复杂度模型多么重要。2. A 题与 B 题把送分题稳稳装进口袋2.1 A 题题解纯分支判断A 题的题面很精简给两个整数 X、Y一个操作符 op只可能是 或 *再给一个整数 Z。如果 XYZ输出 add如果 X*YZ输出 mul否则输出 none。保证 add 和 mul 不会同时成立。这题没有任何算法含量考的就是输入处理和分支书写的干净程度。我第一次提交差点在 op 的读入上踩坑如果用 cin 读 int 之后再读 charchar 变量会把上一行末尾的换行符读进去。C 里最稳妥的方式是直接char op; cin op;它天然跳过空白字符。Python 则要input().strip()后再取内容不然空字符串会带来不必要的麻烦。参考代码Pythonx, y map(int, input().split()) op input().strip() z int(input()) if op : print(add if x y z else none) else: print(mul if x * y z else none)参考代码C#include bits/stdc.h using namespace std; int main() { int x, y, z; char op; cin x y; cin op; cin z; cout (op ? (x y z ? add : none) : (x * y z ? mul : none)) \n; return 0; }这段代码最需要强调的是输出字符串必须和题面完全一致。比赛里不少人在签到题上因为输出Add或None拿不到分纯属可惜。2.2 B 题题解反转串配对计数B 题给定 N 个字符串字符串内容由小写字母组成可能有重复。要统计有多少个无序下标对 (i, j)i j满足第 i 个字符串的反转恰好等于第 j 个字符串。比如ab和ba是一对aba和aba也可以是一对前提是两个索引上的字符串都等于同一个回文串。最直接的双重循环复杂度 O(N^2 × 串长)N 到 2×10^5 的时候直接爆炸。正确做法是线性扫描 哈希计数。核心逻辑是每读到一个新字符串 s先看它的反转rev(s)之前出现过几次把那个次数加到答案里然后再把 s 自己的出现次数加一。这个“先查后加”的顺序非常关键它保证每个配对只被统计一次不会拿当前索引和自己配对。用回文串举个例子如果aba出现 3 次那么第 1 次读到aba时aba的计数是 0ans 加 0第 2 次读到ans 加 1第 3 次读到ans 加 2总配对数是 3正好是 C(3, 2)。如果先把 s 加入计数再查询回文串就会出现自己和自己配对的错误。参考代码Pythonfrom collections import Counter n int(input()) cnt Counter() ans 0 for _ in range(n): s input().strip() ans cnt[s[::-1]] cnt[s] 1 print(ans)参考代码C#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; unordered_mapstring, int cnt; long long ans 0; for (int i 0; i n; i) { string s; cin s; string t s; reverse(t.begin(), t.end()); ans cnt[t]; cnt[s]; } cout ans \n; return 0; }2.3 两题共用的输入与边界细节这两道题在 AtCoder 系的比赛里属于必拿分题但细节依然值得列一下B 题允许重复字符串所以不能用unordered_set去重必须用计数 map 或字典。反转串和原串相同时配对数量按组合数计算“先查后加”能自动处理。答案用long longN 最大 2×10^5 时配对数量可能达到约 2×10^10int 会溢出。比赛里的输入字符串长度可能很大如果用 Python 的reverse切片会创建新字符串内存稍微多一点但 N 和总长度可控时没问题。我第二次打这类题时基本不看样例直接写因为这个模式太经典所有需要“无序配对”的统计都可以用“边查边加”的计数器替代双重循环。3. C 题二分答案解决“最大段和最小化”3.1 题目模型与单调性判断C 题的题面可以概括为给定一个长度为 N 的正整数数组 A要求把数组切成恰好 K 个连续非空块求所有块中元素和的最大值的最小值。N 和 K 最大都是 2×10^5A_i 最大 10^9。看到“最大值最小”这种描述第一反应就应该是二分答案。为什么因为答案 X 的可行性具备单调性如果 X 可以做到那么任何比 X 更大的值也一定可以做到如果 X 做不到那么任何比 X 更小的值也一定做不到。有了单调性就能把“最优解问题”变成“判定问题”。具体地说我们二分一个候选值 limit检查能不能用不超过 K 段让每一段的和都不超过 limit。如果可行说明答案不超过 limit收紧右边界否则答案一定大于 limit收紧左边界。3.2 贪心 check 的写法判定函数是这题的灵魂。从左到右扫描数组维护当前段的累加和 cur遇到新元素时先判断cur v是否超过 limit。如果没超过就把 v 放进当前段否则必须另起一段段数加一cur 重置为 v。为什么要这样贪因为在所有元素都是正数的情况下每一段“尽量多装”一定不会让段数变多。如果最优解在某个位置提前切开了而我们可以把它和后面的元素合并合并后段和增大但不超过 limit段数只会减少或不变。所以贪心得到的是最少段数。这里有一个新手容易写错的点新开一段时cur v而不是cur 0。因为 v 已经属于新的一段如果 cur 置 0下一次再累加会漏掉 v。另外如果数组里存在单个元素本身就大于 limit那么无论怎么切都不可能合法。我在 check 函数开头直接判断v limit就返回 False。参考代码Pythondef can(limit): seg_cnt 1 cur_sum 0 for v in a: if v limit: return False if cur_sum v limit: seg_cnt 1 cur_sum v if seg_cnt k: return False else: cur_sum v return seg_cnt k lo max(a) hi sum(a) while lo hi: mid (lo hi) // 2 if can(mid): hi mid else: lo mid 1 print(lo)3.3 二分边界与代码实现下界为什么是max(a)因为切成单块时任何一块的和至少等于其中最大的元素不可能小于它。上界为什么是sum(a)因为切成一块时段和就是全部元素之和这个值一定是可行方案。二分循环采用常见的lo hi写法mid (lo hi) // 2判断可行就把 hi 收到 mid不可行就把 lo 收到 mid 1。这个写法最终会收敛到第一个可行值。手动推一组边界数组[7, 2, 5]K 2。max(a)7sum(a)14。mid10 时贪心切出来是[7]和[2,5]段数 2可行hi10。mid8 时[7]和[2,5]两段和分别是 7、7也可行hi8。mid7 时[7]段和 7257还是可行hi7。答案 7。这里正好卡在max(a)上说明下界设成 max(a) 不是保守而是必须。复杂度是 O(N log(sumA))在 N2×10^5、sumA2×10^14 的规模下完全跑得动。4. D 题倍数容斥统计 gcd1 子集4.1 直接枚举子集的死路D 题的题面是给 N 个正整数 A_i统计有多少个非空子集满足子集内所有元素的最大公约数恰好为 1。答案对 998244353 取模。N 和 A_i 的最大值都到 3×10^5。如果直接枚举子集2^N 直接不可能。第一步想法是 DP按 gcd 作为状态计数理论上可以做到 O(N × 值域)但值域 3×10^5N 同样大乘起来是 9×10^10跑不动。所以需要换角度不从“子集构造”出发而是从“约数集合”出发。4.2 从“倍数集合”到容斥定义cnt[x]表示数组中有多少个元素是 x 的倍数。如果一个子集里所有元素都是 x 的倍数那么这个子集的 gcd 一定也是 x 的倍数。这类子集有多少个如果数量是 c那么非空子集数量为2^c - 1。把这个值记为f[x]。举个例子数组里有 4 个偶数那么“所有元素都是 2 的倍数”的非空子集数就是2^4 - 1 15这 15 个子集的 gcd 可能是 2、4、6 等等但一定都是 2 的倍数。现在定义g[x]表示“所有元素 gcd 恰好为 x”的子集数量。根据上面的关系f[x]应该等于所有g[d]的和其中 d 是 x 的倍数。于是得到f[x] g[x] g[2x] g[3x] ...从大到小枚举 x就可以逐个反推出g[x]g[x] f[x] - sum(g[d])d 为 x 的所有大于 x 的倍数。最终答案就是g[1]。4.3 实现细节与复杂度先统计每个数值的出现次数freq[v]然后对每个 x 枚举它的倍数 y累加freq[y]得到cnt[x]。这一步的总复杂度是调和级数L/1 L/2 ... L/L ≈ L log L在 L3×10^5 时大约 360 万次操作非常快。预处理 2 的幂次数组pow2[i] pow2[i-1] * 2 % MOD用于快速计算2^cnt - 1。参考代码PythonMOD 998244353 N int(input()) A list(map(int, input().split())) L max(A) freq [0] * (L 1) for v in A: freq[v] 1 cnt [0] * (L 1) for x in range(1, L 1): for y in range(x, L 1, x): cnt[x] freq[y] pow2 [1] * (N 1) for i in range(1, N 1): pow2[i] pow2[i - 1] * 2 % MOD f [0] * (L 1) g [0] * (L 1) for x in range(1, L 1): f[x] (pow2[cnt[x]] - 1) % MOD for x in range(L, 0, -1): g[x] f[x] for d in range(2 * x, L 1, x): g[x] (g[x] - g[d]) % MOD print(g[1] % MOD)写这段代码时有三个必须留意的点减法取模后可能变成负数所以要% MOD调整到正数区间。cnt[x]的枚举方向是“统计每个 x 的倍数”不是“统计每个数的因子”这个方向别写反。pow2数组长度是 N1因为cnt[x]最大就是 N。在赛场上手算样例[2, 3, 6]可以快速验证只有子集[2,3]和[2,3,6]的 gcd 为 1答案是 2。照着代码走一遍能确认容斥过程没有绕乱。5. E 题唯一最小生成树的判定5.1 问题转化与判断依据E 题的题面很直接给一个 N 个点、M 条边的无向连通图每条边有权值。判断这个图的最小生成树是否唯一。如果唯一输出Unique否则输出Not Unique。如果只求最小生成树的总权重裸 Kruskal 就够了。但“唯一性”需要额外处理。一个非常经典的结论是如果存在两种不同的最小生成树方案那么一定有某条权值相同的边可以在最小生成树里被替换成另一条同权边且总权重不变。因此唯一性判断可以聚焦到“同一权值组”的边上。具体方法不是常见的“先求 MST再求次小 MST”而是把 Kruskal 过程按权值分组对于所有权值相同的边统一先做一次联通性检查统计“有资格进入 MST”的候选边数再真正执行合并统计实际被合并的边数。如果候选边数大于实际合并边数说明这一组内存在多余的替代选择MST 不唯一。5.2 同权边分组克鲁斯卡尔为什么必须先统计候选边数再执行合并因为并查集合并是动态的。如果边 a 和边 b 是同权平行边连接同一对点先合并 a 之后b 的两个端点已经在同一集合里此时再检查 b 会发现它无法合并导致候选数少算一条唯一性判断就出错。正确顺序是当前权值组里的所有边在尚未进行这一组任何合并时各自检查端点是否属于不同连通块。满足条件的就是候选边。随后执行真正的合并把能够合并的边都合并进去并累加生成树权值。这里“能够合并”的边数就是这一组里必须连接不同连通块的边数它同时等于连通块减少的数量。候选数大于合并数时说明有一些边虽然也连接着不同的连通块但因为先被其他边合并了而没能选上这正好说明存在多种选法。5.3 实现细节与复杂度参考代码Pythonclass DSU: def __init__(self, n): self.fa list(range(n 1)) def find(self, x): while self.fa[x] ! x: self.fa[x] self.fa[self.fa[x]] x self.fa[x] return x def union(self, a, b): a self.find(a) b self.find(b) if a b: return False self.fa[a] b return True n, m map(int, input().split()) edges [] for _ in range(m): u, v, w map(int, input().split()) edges.append((w, u, v)) edges.sort() dsu DSU(n) possible True i 0 while i m: j i while j m and edges[j][0] edges[i][0]: j 1 candidate 0 for k in range(i, j): w, u, v edges[k] if dsu.find(u) ! dsu.find(v): candidate 1 merged 0 for k in range(i, j): w, u, v edges[k] if dsu.union(u, v): merged 1 if candidate merged: possible False i j print(Unique if possible else Not Unique)实现里有一个小技巧candidate的统计不依赖实际合并顺序所以第一遍循环只是为了“点数”。第二遍循环才真正修改并查集。如果candidate merged没必要立刻退出直接标记后继续后续组也没问题因为后续判断不依赖这个标记只是最终输出前用一下。从复杂度看排序是 O(M log M)扫描部分每组每条边最多看两遍并查集带路径压缩后接近 O(M α(N))整体足够应对 2×10^5 级别的数据。这题让我联想到之前打某场练习赛时遇到的一个变体不是判断 MST 是否唯一而是问“有多少条边可能出现在某个 MST 中”。处理思路本质上相同仍然要分组统计候选边。能把唯一性判断吃透那道变体基本是送分。6. 现场翻车点与自查清单6.1 高频翻车点速查表这场打下来结合同场几位选手赛后聊到的失分点我整理了一张高频翻车对照表位置典型错误正确做法A 题用getchar()读运算符吃进换行用cin op或input().strip()B 题用set去重丢失重复字符串用计数 dict/map先查后加B 题ans 开 int溢出变负数用long longC 题新段开始时cur 0漏掉当前元素新段重置为当前元素值C 题下界设成 0 或 1下界应为max(a)D 题减法取模后为负手动加 MOD 后再取模D 题把“统计倍数”写成“统计因子”内层循环range(x, L1, x)枚举倍数E 题同权组内边先合并再统计候选边先整体统计候选边再执行合并6.2 二分与取模两个典型坑C 题的二分最容易出现死循环。如果写成lo hi且判断可行时lo mid那在只剩两个元素时会因为 mid 等于 lo 而卡住。本次 C 题我采用hi mid与lo mid 1的配对保证 mid 向下取整时不会原地踏步。这个配对在绝大多数“求最小可行值”的问题里都能通用。D 题的取模则提醒我Python 里% MOD会保证结果非负但 C 里如果写成(g[x] - g[d]) % MOD负数的模仍然是负值输出就会错。最稳妥的写法是g[x] (g[x] - g[d] MOD) % MOD虽然稍微多运算一次但安全。6.3 赛后复盘建议比赛结束不等于任务完成。我通常会给每道题建一个小档案记录四件事第一第一眼看到题面时想到了什么算法第二为什么走了弯路第三正确解法里最关键的那一步是什么第四如果下次再遇到相同模型第一步应该做什么。以这场为例C 题的关键是看到“最大值最小”立刻转二分D 题的关键是意识到值域小适合枚举倍数E 题的关键是并查集分组处理同权边。这些“关键一步”才是赛后最有价值的沉淀。单纯把 AC 代码塞进收藏夹下次遇到变体还是不会。我也建议读者别只看题解自己独立把每道题从零写一遍然后故意制造几个常见 bug 运行输出比如把 B 题 counter 顺序换一下、把 E 题合并顺序调一下看看结果差在哪。亲手踩过坑之后印象远比读十遍题解深刻。最后说一点个人体会Beta 周赛题的实验性更强偶尔会考一些陈旧但经典的模型。这类比赛最大的收获不是排名而是让你发现自己在思维习惯上的盲区。我这次最值的一笔投入就是花十几分钟把 E 题的同权边分组逻辑彻底推通了。这个结论以后遇到最小生成树相关的边计数题还能继续复用属于打一场比赛赚三道题的知识迁移。