企业官网建设流程全解析

昨晚把 AtCoder Weekday Contest 0014 Beta 打完整场，刚开始看到 Beta 这个后缀就知道题目不会按套路出牌。五道题从 A 到 E，难度梯度比普通周赛要陡不少：A、B 属于入场券，C 是典型的二分答案，D 开始上强度，E 不仅考最小生成树，还要求判断“唯一性”。整场打下来最大的感受是：这周题目并不在炫算法模板，而是反复在边界条件和“你以为对其实不对”的地方埋雷。

这篇文章不打算只贴代码。我会把每道题从读题、想通到写码的完整链路拆开讲，说明每个关键选择为什么这么做、哪些细节容易翻车、复杂度靠不靠谱。不管你是正在备战 ABC、想把难度往上探一探，还是纯粹想拿几道题练手，这套复盘都值得对着过一遍。

1. 赛前复盘：题面难度分布与开题策略

1.1 A-E 题目速览与考点

先把五道题的考察内容和标签整理成一张表，后面每道题再展开。

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。如果 X+Y=Z，输出 add；如果 X*Y=Z，输出 mul；否则输出 none。保证 add 和 mul 不会同时成立。

这题没有任何算法含量，考的就是输入处理和分支书写的干净程度。我第一次提交差点在 op 的读入上踩坑：如果用 cin 读 int 之后再读 char，char 变量会把上一行末尾的换行符读进去。C++ 里最稳妥的方式是直接char op; cin >> op;，它天然跳过空白字符。Python 则要input().strip()后再取内容，不然空字符串会带来不必要的麻烦。

参考代码（Python）：

x, 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的计数是 0，ans 加 0；第 2 次读到，ans 加 1；第 3 次读到，ans 加 2，总配对数是 3，正好是 C(3, 2)。如果先把 s 加入计数再查询，回文串就会出现自己和自己配对的错误。

参考代码（Python）：

from 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_map<string, 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 long，N 最大 2×10^5 时，配对数量可能达到约 2×10^10，int 会溢出。
• 比赛里的输入字符串长度可能很大，如果用 Python 的reverse切片会创建新字符串，内存稍微多一点，但 N 和总长度可控时没问题。

我第二次打这类题时基本不看样例直接写，因为这个模式太经典：所有需要“无序配对”的统计，都可以用“边查边加”的计数器替代双重循环。

3. C 题：二分答案解决“最大段和最小化”

3.1 题目模型与单调性判断

C 题的题面可以概括为：给定一个长度为 N 的正整数数组 A，要求把数组切成恰好 K 个连续非空块，求所有块中元素和的最大值的最小值。N 和 K 最大都是 2×10^5，A_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。

参考代码（Python）：

def 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)=7，sum(a)=14。mid=10 时，贪心切出来是[7]和[2,5]，段数 2，可行，hi=10。mid=8 时，[7]和[2,5]两段和分别是 7、7，也可行，hi=8。mid=7 时，[7]段和 7，2+5=7，还是可行，hi=7。答案 7。这里正好卡在max(a)上，说明下界设成 max(a) 不是保守，而是必须。

复杂度是 O(N log(sumA))，在 N=2×10^5、sumA=2×10^14 的规模下完全跑得动。

4. D 题：倍数容斥统计 gcd=1 子集

4.1 直接枚举子集的死路

D 题的题面是：给 N 个正整数 A_i，统计有多少个非空子集，满足子集内所有元素的最大公约数恰好为 1。答案对 998244353 取模。N 和 A_i 的最大值都到 3×10^5。

如果直接枚举子集，2^N 直接不可能。第一步想法是 DP：按 gcd 作为状态计数，理论上可以做到 O(N × 值域)，但值域 3×10^5，N 同样大，乘起来是 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，在 L=3×10^5 时大约 360 万次操作，非常快。

预处理 2 的幂次数组，pow2[i] = pow2[i-1] * 2 % MOD，用于快速计算2^cnt - 1。

参考代码（Python）：

MOD = 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数组长度是 N+1，因为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 实现细节与复杂度

参考代码（Python）：

class 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 高频翻车点速查表

这场打下来，结合同场几位选手赛后聊到的失分点，我整理了一张高频翻车对照表：

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 题的同权边分组逻辑彻底推通了。这个结论以后遇到最小生成树相关的边计数题还能继续复用，属于打一场比赛赚三道题的知识迁移。