ICPC网络赛七题复盘：常见算法模型的实战运用与代码细节

2022ICPC网络赛第一场的五小时，我们队最后过了A、C、G、H、J、K、L七题，排名不算靠前，但复盘时发现这七题其实都没有特别偏门的算法，全部落在常见套路的射程范围内。赛后我花了两个晚上把每道题重新推到能一次AC的水平，把思考过程、代码细节和踩过的坑一起整理出来。这篇不是官方题解，只是我作为一个普通参赛者的复盘记录，重点放在题目模型、关键观察和实现时容易翻车的位置。

先说明一下，题目原题面我没有完整背下来，下面所有"题意"都是赛后对照代码重新整理的模型化描述。ICPC的题面通常包装得花里胡哨，但拆掉外壳后核心模型往往很朴素，这也是我要强调的东西：比赛里读题快、建模准，比临场想出一个炫技算法有用得多。

1. 复盘：这七题是怎么在五个小时里被我们逐个拿下的

1.1 难度分布：七题的定位和用时

先看一张总览表，这是我赛后根据提交记录整理的：

这个顺序并不是我们实际提交的先后顺序，而是我把AC时间排了一下得到的。可以看到，前两题基本在1小时内解决，中间三段在中档题上消耗了大部分时间，最后一题则是卡到最后快结束才磕出来。实际上我们开场是先做的A，A过了之后我跟队友说C看起来是数学，先让数学好的队友去推，我去看G，结果三线并行，节奏才勉强保住。

1.2 开题策略：前60分钟先拿稳三题

这种网络赛的罚时规则决定了前一个半小时非常宝贵。我的习惯是：开赛后先把每道题都扫一遍题面，不急着写代码，而是给每道题打一个"模型标签"。比如A题看到"相邻交换"立刻想到逆序对，C题看到"gcd等于1"立刻想到容斥，G题看到"树上多个关键点、回路"立刻想到LCA和DFS序，H题看到"区间加、区间和"立刻想到线段树。模型识别出来后，心里就有底了，剩下的只是把细节写对。

前60分钟我们真正写掉的是A和C，G的代码框架已经搭好但没敢交。我的体会是，中档题再稳也要留出至少一个完整的调试周期，所以在1小时内最多期望AC三道以内的题。如果做题顺序乱掉，比如先去死磕L，大概率会崩盘。

2. A、C：两题快题里最容易种的刺

2.1 A题：相邻交换的最小次数不是模拟

题意模型：给定两个长度相同的字符串s和t，保证字符集相同，每次操作可以交换s中相邻两个字符，问把s变成t的最小操作次数，如果不可能则输出-1。字符串长度是1e5级别。

很多新手第一反应是直接模拟冒泡排序去交换字符，这个方向完全错误，因为最坏情况操作次数是O(n^2)，字符串稍微大一点就超时。相邻交换的最小次数在模型上等价于求逆序对数量，关键是要把原串中的每个字符和目标串中的位置对应起来。

做法分三步：

1. 统计s和t中每个字符的出现次数，不一致直接输出-1。
2. 对每个字符维护一个队列，记录该字符在s中出现的全部下标。遍历t的每个字符，从对应队列中取出队首下标，组成一个排列p。
3. 求p的逆序对数量，就是答案。

为什么这个排列的逆序对数量等于最小操作次数？因为目标串已经固定了s中每个字符最终要去的位置，两个字符如果在排列p中的相对顺序反了，它们在移动过程中必然要"跨过"对方一次，而每次相邻交换恰好消除一个逆序对。所以最小次数就是排列的逆序对数，用树状数组或者归并排序都能做到O(n log n)。

核心代码大致这样：

long long minSwapToMakeSame(string s, string t) { int n = s.size(); vector<queue<int>> pos(26); for (int i = 0; i < n; i++) { pos[s[i] - 'a'].push(i); } vector<int> p; p.reserve(n); for (char c : t) { int id = c - 'a'; if (pos[id].empty()) return -1; p.push_back(pos[id].front()); pos[id].pop(); } // 树状数组求逆序对 long long ans = 0; BIT bit(n); // 下标从1开始 for (int i = 0; i < n; i++) { ans += i - bit.sum(p[i] + 1); // 已经插入的前i个位置中，比p[i]大的数量 bit.add(p[i] + 1, 1); } return ans; }

注意树状数组从1开始的下标偏移，这是最容易WA的点。我当时就是因为p[i]直接传进bit.add导致越界，白送了一发罚时。另外，字符集如果扩展到大小写字母，数组开到52或128都无所谓，但不要忘了'a'偏移。

2.2 C题：gcd=1的计数，容斥筛出答案

题意模型：统计长度为n、每个元素取值在[1, m]范围内的数组个数，要求整个数组的最大公约数恰好为1，答案对1e9+7取模。n可以到1e9，m到1e6。

直接枚举数组显然不可能，但这种"gcd恰好为1"的问题有固定套路：莫比乌斯反演。先明确一个恒等式：

[gcd(a1, a2, ..., an) == 1] = sum_{d | gcd(a1, ..., an)} mu(d)

于是方案数可以写成对d求和：

ans = sum_{d=1}^{m} mu(d) * floor(m / d)^n

解释一下：所有元素都能被d整除的数组个数是floor(m/d)^n，乘上莫比乌斯系数做容斥，就筛掉了所有gcd大于1的情况。mu(1)=1，所以d=1这一项就是总方案数m^n，后面的项是在一点点扣除非法方案。

实现时需要用线性筛预处理mu数组到m，然后对每个d做一次快速幂。如果mu(d)为0，说明d含有平方因子，可以直接跳过。复杂度O(m + m log n)，在m=1e6时完全没有压力。

const int MOD = 1e9 + 7; long long qpow(long long a, long long b) { long long r = 1; while (b) { if (b & 1) r = r * a % MOD; a = a * a % MOD; b >>= 1; } return r; } int solve(int n, int m) { vector<int> mu(m + 1), primes; vector<bool> isPrime(m + 1, true); mu[1] = 1; for (int i = 2; i <= m; i++) { if (isPrime[i]) { primes.push_back(i); mu[i] = -1; } for (int p : primes) { if (1LL * i * p > m) break; isPrime[i * p] = false; if (i % p == 0) { mu[i * p] = 0; break; } else { mu[i * p] = -mu[i]; } } } long long ans = 0; for (int d = 1; d <= m; d++) { if (mu[d] == 0) continue; ans = (ans + mu[d] * qpow(m / d, n)) % MOD; } ans = (ans + MOD) % MOD; return ans; }

这里的坑是负数的取模。mu[d]可能为-1，累加过程中ans会变成负数，必须在最后加一个MOD再取模。类似的数论题，只要公式里出现加减混合，我都会养成最后(ans + MOD) % MOD的习惯，省得样例过了还是WA。

3. G、H：中档题的稳定输出

3.1 G题：按DFS序排序，回路问题瞬间变简单

题意模型：给定一棵n个点的树，q次询问，每次给出k个关键点，问从任意一个关键点出发，访问完所有关键点并回到出发点的最短闭合路径长度。

这题的关键点是"回到出发点"，所以路径一定形成一个闭合回路。对于树上连通块，包含所有关键点的最小连通子树（其实就是把它们之间的路径并起来）中的每条边，在这个回路里恰好会走两次。那么怎么快速算出这个"两次总长"呢？

标准做法是把关键点按树的DFS序排序，然后依次求相邻两个关键点在树上的距离，再把首尾两个也连起来，累加所有相邻距离。这个总和就是闭合回路长度。原理是：把所有关键点放在DFS序的环上，相邻点的路径组合起来恰好覆盖了最小连通子树的每条边两次。

对于求距离，我用倍增LCA预处理，dist(u, v) = depth[u] + depth[v] - 2 * depth[lca(u, v)]，其中depth是点到根的距离，边权为1时就是深度，带权树也同理。

vector<int> dfn; // 每个节点的DFS序 long long solveQuery(vector<int> nodes) { sort(nodes.begin(), nodes.end(), [&](int a, int b) { return dfn[a] < dfn[b]; }); long long ans = 0; int cnt = nodes.size(); for (int i = 0; i < cnt; i++) { int u = nodes[i]; int v = nodes[(i + 1) % cnt]; ans += getDist(u, v); } return ans; }

这个结论背下来很值钱。如果再延伸一步：如果题目改成"不需要回到起点"，那么答案就是上面的闭合回路长度减去关键点集合在树上的直径。因为回路中有一条最长路径可以省掉，恰好省掉的就是直径。G题我们当时没有往这个方向想，还在考虑是不是要建虚树，后来发现不需要，直接DFS序排序就够。建虚树当然也能做，但复杂度高、代码量大，网络赛里没必要。

坑点在于dfn的编号要在同一个DFS里预处理，不要用递归深度可能导致栈溢出，就用迭代或者直接开大数组。还有k=1时，回路长度为0，不要因为取模或者特殊逻辑输出负数。

3.2 H题：区间加的线段树，重在三处细节

题意模型：给定长度为n的数组，维护两种操作：区间[l, r]内每个数加上一个值v，查询区间[l, r]的元素和。n, q都是1e5这个量级。

这类题是线段树区间懒标记的入门题，但现场AC率并不高，原因往往是细节处理不够谨慎。细节主要有三个：

1. sum和lazy都要开long long。区间加操作的值、累加和都可能超过int，尤其在多次累加之后。
2. 区间更新时，当前节点的sum要加上add * (r-l+1)，而不是只加add。lazy标记则直接累加add。
3. pushdown时，先给两个孩子节点的sum加上lazy * 子区间长度，再把lazy传下去，最后清空当前节点lazy。顺序不能反。

代码核心部分：

void push(int p, int l, int r) { if (!lazy[p]) return; int mid = (l + r) >> 1; int left = p << 1, right = left | 1; sum[left] += lazy[p] * (mid - l + 1); lazy[left] += lazy[p]; sum[right] += lazy[p] * (r - mid); lazy[right] += lazy[p]; lazy[p] = 0; } void add(int p, int l, int r, int ql, int qr, long long v) { if (ql <= l && r <= qr) { sum[p] += v * (r - l + 1); lazy[p] += v; return; } push(p, l, r); int mid = (l + r) >> 1; if (ql <= mid) add(p << 1, l, mid, ql, qr, v); if (qr > mid) add(p << 1 | 1, mid + 1, r, ql, qr, v); sum[p] = sum[p << 1] + sum[p << 1 | 1]; }

我们队伍在H题上WA了两发，第一发是没用long long，第二发是写add的时候忘了对当前节点的sum乘上区间长度。这种低级错误很伤士气。如果你用递归线段树，记得把操作函数加上inline，不然在1e6级别的操作下递归开销会比较明显，我也试过被卡常的情况。另外，如果追求极限，可以把线段树改成非递归的zkw写法，但比赛里我通常只在迫不得已时才换。

4. J、K：两道优化题的经验教训

4.1 J题：任务调度贪心，小根堆替换是精髓

题意模型：有n个任务，每个任务需要1个单位时间完成，第i个任务有截止时间d[i]和收益p[i]。同一时刻只能做一个任务，求能获得的最大总收益。

这个模型非常经典，思路也清晰：先把任务按截止时间从小到大排序，然后从左到右扫描。用一个变量now表示当前已经安排的任务数量，也就是当前占用到的时间点。如果now < d[i]，说明目前还有空位，直接把这个任务加入已选集合；如果now == d[i]，但这个任务的收益比已选任务中收益最小的还要大，就用它替换掉那个最小收益任务。已经选中的任务集合用一个小根堆维护，堆顶就是当前收益最小的任务。

这样做的正确性在于：每个截止时间d之前最多只能安排d个任务，遇到冲突时保留收益更大的任务一定不会更差。替换操作相当于牺牲一个低收益任务，腾出位置给高收益任务，总收益单调不减。

struct Task { int d, p; }; bool cmp(Task a, Task b) { return a.d < b.d; } long long maxProfit(vector<Task> a) { sort(a.begin(), a.end(), cmp); priority_queue<int, vector<int>, greater<int>> pq; long long ans = 0; for (auto &t : a) { if ((int)pq.size() < t.d) { pq.push(t.p); ans += t.p; } else if (!pq.empty() && t.p > pq.top()) { ans += t.p - pq.top(); pq.pop(); pq.push(t.p); } } return ans; }

这个题的坑在于截止时间可能不是连续的、也可能超过n。如果d[i]特别大，pq.size()永远不会超过它，所以可以直接当作有足够空位处理，不会出错。还有一个常见误解是把任务按收益从大到小排序，然后往时间轴上塞，这个思路也能做但要配合并查集找空位，反而更复杂。按截止时间排序+堆替换是我认为最容易写对、也最容易讲清楚的版本。

4.2 K题：状压TSP之前，先跑一遍Floyd

题意模型：n个点（n <= 18）的无向带权图，求从点0出发，经过每个点至少一次并回到点0的最短路径长度。

因为有"至少一次"这个条件，如果两点之间的最短路径可能经过其他未访问点，直接用原始邻接矩阵做状压DP会出错。正确做法是先跑一遍Floyd-Warshall，得到任意两点之间的最短距离，然后再用状压DP求经过所有点的最短回路。

状态设计是dp[mask][i]：已经访问过的节点集合为mask，当前停在节点i的最短路径长度。初始dp[1 << 0][0] = 0，转移时枚举下一个未访问节点j：

for (int mask = 0; mask < (1 << n); mask++) { for (int i = 0; i < n; i++) { if (!(mask & (1 << i))) continue; if (dp[mask][i] == INF) continue; for (int j = 0; j < n; j++) { if (mask & (1 << j)) continue; int nmask = mask | (1 << j); dp[nmask][j] = min(dp[nmask][j], dp[mask][i] + dist[i][j]); } } }

最后答案枚举所有i，取dp[(1 << n) - 1][i] + dist[i][0]的最小值。

复杂度是O(2^n * n^2)，n=18大约8e7次转移，能跑但要注意常数。我当时在循环里加了一个if (dp[mask][i] == INF) continue;，这个剪枝能明显减少无效转移。另外dist数组要先Floyd，否则直接拿到原边权，样例都可能过不了。很多选手栽在这题都是因为忘记了Floyd这一层。

5. L题：最小圆覆盖，随机化增量法值得拥有

5.1 题意转化：半径最小的覆盖圆

题意模型：给定平面上的n个点，求一个半径最小的圆，使得所有点都在圆内或圆上，输出半径。n可以达到1e5。

如果这题出现在数学卷子上，可以用几何性质推；在算法竞赛里，最稳妥的解法是随机增量法。算法名字听着唬人，核心思想其实很朴素：

1. 把所有点随机打乱。
2. 初始以第一个点为圆心、半径为0。
3. 依次加入每个点，如果当前点在圆内，继续；否则说明当前圆不能覆盖它，这个点一定在最终最小圆的边界上。
4. 以当前点为圆心、半径为0，重新扫描它前面的所有点，逐步扩大圆。
5. 如果新增一个点在圆外，那么这一点也在边界上，需要用当前点和之前的一个点确定一个圆（两点为直径的圆）。
6. 如果再碰到圆外的点，就用三个点确定唯一的外接圆。

每次"碰壁"后重新构造圆，因为点集是随机顺序，期望复杂度是O(n)。虽然最坏是O(n^3)，但随机化后几乎不会发生。

两点确定圆很简单，就是这两个点的中点为圆心，距离的一半为半径。三点确定外接圆需要解一个二元一次方程组，这里最容易写错，建议直接背模板。

5.2 三点定圆的实现与浮点精度

三点A(x1,y1), B(x2,y2), C(x3,y3)的外心坐标可以这样推：外心到三点距离相等，所以可以列出两个线性方程：

(x1 - x2) * X + (y1 - y2) * Y = (x1^2 - x2^2 + y1^2 - y2^2) / 2 (x1 - x3) * X + (y1 - y3) * Y = (x1^2 - x3^2 + y1^2 - y3^2) / 2

用克莱姆法则解出X, Y即可。注意如果三点接近共线，行列式接近0，这个时候精度会炸。比赛题通常数据比较温和，但还是要用long double和eps判。

核心代码片段：

const double eps = 1e-8; struct Point { double x, y; }; double dis(Point a, Point b) { return hypot(a.x - b.x, a.y - b.y); } Point circumcenter(Point a, Point b, Point c) { double a1 = b.x - a.x, b1 = b.y - a.y; double c1 = (a1 * (a.x + b.x) + b1 * (a.y + b.y)) / 2; double a2 = c.x - a.x, b2 = c.y - a.y; double c2 = (a2 * (a.x + c.x) + b2 * (a.y + c.y)) / 2; double det = a1 * b2 - a2 * b1; return Point{(c1 * b2 - c2 * b1) / det, (a1 * c2 - a2 * c1) / det}; } Circle minCoverCircle(vector<Point> p) { random_shuffle(p.begin(), p.end()); Point o = p[0]; double r = 0; for (int i = 1; i < (int)p.size(); i++) { if (dis(o, p[i]) > r + eps) { o = p[i]; r = 0; for (int j = 0; j < i; j++) { if (dis(o, p[j]) > r + eps) { o = Point{(p[i].x + p[j].x) / 2, (p[i].y + p[j].y) / 2}; r = dis(o, p[i]); for (int k = 0; k < j; k++) { if (dis(o, p[k]) > r + eps) { o = circumcenter(p[i], p[j], p[k]); r = dis(o, p[i]); } } } } } } return {o, r}; }

L题现场我们卡了很久，原因是我一开始把r设成了1e18，导致初始判断全部绕过，算法退化成了枚举所有点对，直接TLE。正确的初始化应该是第一个点作为半径0的单位圆，然后一层层扩。另外random_shuffle之前记得给随机数种子srand(time(0))，否则固定顺序在某些构造数据下会被卡成最坏复杂度。浮点输出一般要求保留若干位小数，注意格式。

6. 如果你也想在下一次网络赛少罚时

6.1 考前要练熟的四个模板

从这七道题回头看，网络赛高频套路其实就那么几块。与其在比赛时现推，不如提前把模板练成肌肉记忆：

• 树链工具包：倍增LCA、DFS序、树上距离。G题直接用到，很多树的题都会用到。
• 区间数据结构：线段树懒标记、树状数组。H题和A题都能用。
• 贪心与堆：任务调度、区间选点，J题这类题几乎每场都有。
• 状态压缩DP：TSP、子集枚举，K题是典型。

这四个模板我在赛前其实都练过，但实战时还是会因为小细节卡壳。建议把每个模板的"易错点清单"写在笔记里，比赛前翻一遍，比临时翻题解高效太多。

6.2 对拍脚本：赛后复盘和打比赛都靠它

很多WA我一次发现不了，但用对拍就能快速锁定。赛后复盘时，我会写一个暴力版本和一个优化版本，然后用一个数据生成器随机制造小规模测试数据，不停对比两个版本的输出。

最简单的对拍脚本大概是这样的：

while true; do python3 gen.py > input.txt ./brute < input.txt > brute.out ./fast < input.txt > fast.out if diff brute.out fast.out; then echo "AC" else echo "WA" break fi done

gen.py写一个能生成随机小数据的程序，brute.cpp是暴力枚举，fast.cpp是正解。数据范围要小到暴力能在1秒内跑完，同时随机性要强，这样更容易碰出边界情况。A题我当时就是用这种方法在赛后发现了逆序对数组下标越界的问题，才知道自己WA在哪里。

这套对拍流程我现在几乎每场正式比赛前都会准备至少一道题的对拍模板，尤其是贪心和数据结构题，基本能挡住90%的细节错误。个人体会是，竞赛水平的差距很多时候不在算法思路，而在能不能快速发现自己写错了、以及写错后能不能冷静地对拍定位。希望这篇复盘对正在准备ICPC网络赛的朋友有帮助。