2022ICPC网络赛第一场的五小时我们队最后过了A、C、G、H、J、K、L七题排名不算靠前但复盘时发现这七题其实都没有特别偏门的算法全部落在常见套路的射程范围内。赛后我花了两个晚上把每道题重新推到能一次AC的水平把思考过程、代码细节和踩过的坑一起整理出来。这篇不是官方题解只是我作为一个普通参赛者的复盘记录重点放在题目模型、关键观察和实现时容易翻车的位置。先说明一下题目原题面我没有完整背下来下面所有题意都是赛后对照代码重新整理的模型化描述。ICPC的题面通常包装得花里胡哨但拆掉外壳后核心模型往往很朴素这也是我要强调的东西比赛里读题快、建模准比临场想出一个炫技算法有用得多。1. 复盘这七题是怎么在五个小时里被我们逐个拿下的1.1 难度分布七题的定位和用时先看一张总览表这是我赛后根据提交记录整理的题号核心模型难度定位我们AC的时间A相邻交换转逆序对签到0:32C莫比乌斯容斥计数签到偏上0:58GLCA DFS序排序中档1:47H线段树区间加区间和中档2:20J贪心 小根堆中档2:51K状压TSP较难3:44L最小圆覆盖随机增量压轴4:52这个顺序并不是我们实际提交的先后顺序而是我把AC时间排了一下得到的。可以看到前两题基本在1小时内解决中间三段在中档题上消耗了大部分时间最后一题则是卡到最后快结束才磕出来。实际上我们开场是先做的AA过了之后我跟队友说C看起来是数学先让数学好的队友去推我去看G结果三线并行节奏才勉强保住。1.2 开题策略前60分钟先拿稳三题这种网络赛的罚时规则决定了前一个半小时非常宝贵。我的习惯是开赛后先把每道题都扫一遍题面不急着写代码而是给每道题打一个模型标签。比如A题看到相邻交换立刻想到逆序对C题看到gcd等于1立刻想到容斥G题看到树上多个关键点、回路立刻想到LCA和DFS序H题看到区间加、区间和立刻想到线段树。模型识别出来后心里就有底了剩下的只是把细节写对。前60分钟我们真正写掉的是A和CG的代码框架已经搭好但没敢交。我的体会是中档题再稳也要留出至少一个完整的调试周期所以在1小时内最多期望AC三道以内的题。如果做题顺序乱掉比如先去死磕L大概率会崩盘。2. A、C两题快题里最容易种的刺2.1 A题相邻交换的最小次数不是模拟题意模型给定两个长度相同的字符串s和t保证字符集相同每次操作可以交换s中相邻两个字符问把s变成t的最小操作次数如果不可能则输出-1。字符串长度是1e5级别。很多新手第一反应是直接模拟冒泡排序去交换字符这个方向完全错误因为最坏情况操作次数是O(n^2)字符串稍微大一点就超时。相邻交换的最小次数在模型上等价于求逆序对数量关键是要把原串中的每个字符和目标串中的位置对应起来。做法分三步统计s和t中每个字符的出现次数不一致直接输出-1。对每个字符维护一个队列记录该字符在s中出现的全部下标。遍历t的每个字符从对应队列中取出队首下标组成一个排列p。求p的逆序对数量就是答案。为什么这个排列的逆序对数量等于最小操作次数因为目标串已经固定了s中每个字符最终要去的位置两个字符如果在排列p中的相对顺序反了它们在移动过程中必然要跨过对方一次而每次相邻交换恰好消除一个逆序对。所以最小次数就是排列的逆序对数用树状数组或者归并排序都能做到O(n log n)。核心代码大致这样long long minSwapToMakeSame(string s, string t) { int n s.size(); vectorqueueint pos(26); for (int i 0; i n; i) { pos[s[i] - a].push(i); } vectorint 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题gcd1的计数容斥筛出答案题意模型统计长度为n、每个元素取值在[1, m]范围内的数组个数要求整个数组的最大公约数恰好为1答案对1e97取模。n可以到1e9m到1e6。直接枚举数组显然不可能但这种gcd恰好为1的问题有固定套路莫比乌斯反演。先明确一个恒等式[gcd(a1, a2, ..., an) 1] sum_{d | gcd(a1, ..., an)} mu(d)于是方案数可以写成对d求和ans sum_{d1}^{m} mu(d) * floor(m / d)^n解释一下所有元素都能被d整除的数组个数是floor(m/d)^n乘上莫比乌斯系数做容斥就筛掉了所有gcd大于1的情况。mu(1)1所以d1这一项就是总方案数m^n后面的项是在一点点扣除非法方案。实现时需要用线性筛预处理mu数组到m然后对每个d做一次快速幂。如果mu(d)为0说明d含有平方因子可以直接跳过。复杂度O(m m log n)在m1e6时完全没有压力。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) { vectorint mu(m 1), primes; vectorbool 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时就是深度带权树也同理。vectorint dfn; // 每个节点的DFS序 long long solveQuery(vectorint 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里预处理不要用递归深度可能导致栈溢出就用迭代或者直接开大数组。还有k1时回路长度为0不要因为取模或者特殊逻辑输出负数。3.2 H题区间加的线段树重在三处细节题意模型给定长度为n的数组维护两种操作区间[l, r]内每个数加上一个值v查询区间[l, r]的元素和。n, q都是1e5这个量级。这类题是线段树区间懒标记的入门题但现场AC率并不高原因往往是细节处理不够谨慎。细节主要有三个sum和lazy都要开long long。区间加操作的值、累加和都可能超过int尤其在多次累加之后。区间更新时当前节点的sum要加上add * (r-l1)而不是只加add。lazy标记则直接累加add。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(vectorTask a) { sort(a.begin(), a.end(), cmp); priority_queueint, vectorint, greaterint 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转移时枚举下一个未访问节点jfor (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)n18大约8e7次转移能跑但要注意常数。我当时在循环里加了一个if (dp[mask][i] INF) continue;这个剪枝能明显减少无效转移。另外dist数组要先Floyd否则直接拿到原边权样例都可能过不了。很多选手栽在这题都是因为忘记了Floyd这一层。5. L题最小圆覆盖随机化增量法值得拥有5.1 题意转化半径最小的覆盖圆题意模型给定平面上的n个点求一个半径最小的圆使得所有点都在圆内或圆上输出半径。n可以达到1e5。如果这题出现在数学卷子上可以用几何性质推在算法竞赛里最稳妥的解法是随机增量法。算法名字听着唬人核心思想其实很朴素把所有点随机打乱。初始以第一个点为圆心、半径为0。依次加入每个点如果当前点在圆内继续否则说明当前圆不能覆盖它这个点一定在最终最小圆的边界上。以当前点为圆心、半径为0重新扫描它前面的所有点逐步扩大圆。如果新增一个点在圆外那么这一点也在边界上需要用当前点和之前的一个点确定一个圆两点为直径的圆。如果再碰到圆外的点就用三个点确定唯一的外接圆。每次碰壁后重新构造圆因为点集是随机顺序期望复杂度是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(vectorPoint 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题这类题几乎每场都有。状态压缩DPTSP、子集枚举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 donegen.py写一个能生成随机小数据的程序brute.cpp是暴力枚举fast.cpp是正解。数据范围要小到暴力能在1秒内跑完同时随机性要强这样更容易碰出边界情况。A题我当时就是用这种方法在赛后发现了逆序对数组下标越界的问题才知道自己WA在哪里。这套对拍流程我现在几乎每场正式比赛前都会准备至少一道题的对拍模板尤其是贪心和数据结构题基本能挡住90%的细节错误。个人体会是竞赛水平的差距很多时候不在算法思路而在能不能快速发现自己写错了、以及写错后能不能冷静地对拍定位。希望这篇复盘对正在准备ICPC网络赛的朋友有帮助。