2022年的ICPC中国浙江省级赛已经过去挺久了，可直到现在，训练群里隔三差五还有人讨论第19届省赛那几道题。趁着周末没什么比赛，我把当时觉得有代表性的五道题重新推了一遍，整理成这篇题解笔记。笔记主要面向准备区域赛的选手，也适合刚入坑竞赛、想看看省赛到底考什么的朋友。文章不按题号顺序来，而是挑五类不同方向的问题——贪心、字符串、树上数据结构、最短路建模、生成树——每道题都会讲清楚我在赛场上的第一反应、最终的写法，以及容易踩的坑。如果你是在赛后补题，想对照思路，可以直接跳到对应小节。

提示：文中题面是我凭比赛印象重新叙述的，如果有细节出入，以官方题面为准。这篇笔记的重点是解题思路和实现细节，不是逐字复述题面。

1. 比赛概况与我的补题顺序

1.1 这场省赛留给我的整体印象

第19届浙江省赛给我的第一感觉是：难度梯度做得不错。开场签到题基本是秒出思路，中等题需要一点模型转化，最后一两题则明显是拉区分度的硬骨头。看完整套题之后，我大概判断这次的重点集中在贪心、字符串匹配、树上问题、图论和最短路建模这几块，没有特别冷门的算法，但每道题都考了“你能不能把一个看似复杂的问题，压缩成熟悉的模型”。

这里说一个大多数参赛选手都会犯的毛病：拿到题就按题号顺序开始做，结果卡在一道明明不难的题上浪费了四十分钟。我个人的习惯是先把所有题面扫一遍，给每道题打一个“算法标签”，比如这题像贪心、那题像DP、这题可能要数据结构。打完标签再决定开题顺序。这套方法在这次省赛里很管用，因为题目分布比较典型，扫一遍大概就知道哪些是必须稳拿的，哪些是要冲的。

1.2 我挑选这五道题的标准

这篇笔记没有面面俱到，我只挑了五道题，每一道代表一类竞赛里非常核心的套路：

• 中位数贪心，考察的是最基础的“排序 + 绝对值和最小化”；
• 字符串循环同构，考察的是怎么把一个看似暴力的匹配过程用卷积加速；
• 树上路径颜色众数，考察的是把树上问题转换成序列问题的能力；
• 同余最短路，考察的是对“体积小、容量大”的特殊背包问题的建模敏感度；
• 最小瓶颈路，考察的是对最小生成树性质的理解深度。

这五个方向基本覆盖了省赛里最高频的几种考察手段。把它们吃透了，遇到同类变体至少不会慌。下面每一题我都会按“题意理解 - 思路推导 - 代码实现 - 坑点提醒”的顺序来讲。

2. 签到题：中位数贪心，别急着套二分

2.1 题意与第一反应

这道题的大意是：给定 n 个整数，每次操作可以把任意一个数加一或者减一，代价都是 1，问最少操作多少次能让所有数变得一样。

说实话，这种题我刚开始打竞赛时经常踩坑，第一反应是算平均数，然后让所有数往平均数靠。样例一过，看似很合理，但等数据出现极端值的时候就会出问题。为什么平均数不行？因为绝对值和函数在平均数的位置并非总是取得最小值，反而可能出现某个大数把平均数拉偏，导致总代价反而变大。

我当时在赛场上大概花了二十秒判断出这题应该是中位数，然后快速验证了几组数据，确认无误后直接写代码。原因很简单：如果要把所有 x_i 变成同一个值 p，总代价就是 sum |x_i - p|，这是典型的“到定点距离和最小化”问题，最优解就是数据的中位数。

2.2 为什么答案就是中位数

我们不妨从直观上理解这个问题。把 n 个数看成数轴上的 n 个点，我们要选一个点 p，让所有点到 p 的距离总和最小。假设现在 p 略微向右移动了一小段距离，那么位于 p 左边的每个点到 p 的距离都会增加一小段，位于 p 右边的每个点到 p 的距离都会减少一小段。换句话说，向右移动的“边际收益”取决于右边点的个数减去左边点的个数。

当 p 左边有超过一半的点、右边少于一半的点时，再往右移动会让总距离增加；当 p 左边少于一半、右边多于一半时，再往右移动会让总距离减少。只有当左右两边都是半数左右时，总距离才会达到最低点，而满足这个条件的点就是中位数。对于偶数个数，中位数可以取中间两个数之间的任意值，代价一样，代码里直接取 a[n/2] 即可。

这个证明并不复杂，但很多新手会忽略“为什么不是平均数”这个问题。平均数是让平方和最小，中位数是让绝对值和最小，两者场景完全不同，放在一起对比最容易理解。

2.3 参考代码与实现细节

#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); vector<long long> a(n); for (int i = 0; i < n; i++) scanf("%lld", &a[i]); sort(a.begin(), a.end()); long long mid = a[n / 2]; long long ans = 0; for (long long x : a) ans += llabs(x - mid); printf("%lld\n", ans); return 0; }

这题代码很简单，但仍然有三个容易翻车的点：

• 必须开 long long。n 的范围和数值范围如果到 10^5、10^9 级别，总代价可能到 10^14，int 必炸。
• 排序别漏。求中位数不排序就是白给。
• 偶数个数据时取 a[n/2] 还是 a[n/2-1] 都行，但不要取 a[n/2+1]，会越界。

3. 字符串题：循环同构最少修改次数

3.1 题目描述与暴力解法

这道题是典型的“题意一眼就懂，做法要想一想”的类型。大意是：给定两个长度相同的字符串 s 和 t，你允许把 t 循环移位任意多次，问最少修改 s 中的多少个字符，能让 s 和移位后的 t 完全相同。

所谓的循环移位，就是把 t 的最后一个字符挪到最前面，或者反过来，本质上是考虑 t 的所有旋转结果。题目让我们求所有旋转里，与 s 不同字符数最少的那一个。

最先想到的自然是暴力：枚举偏移量 k，从 0 到 n-1，然后逐个位置比较 s[i] 和 t[(i+k)%n]，统计不同的个数，最后取最小值。这个做法复杂度是 O(n^2)，如果 n 只有几千，完全可以直接过；但省赛的数据显然不会这么客气，n 到 10^5 级别时，O(n^2) 是铁定超时的。所以真正的考点是：怎么一次性算出所有偏移下的匹配数。

3.2 用卷积一次性算出所有偏移的匹配数

这里要用到一个竞赛里很常见但很多人不熟的技巧：把字符匹配转换成卷积。

我们先只考虑一个特定字符 c。对 s 和 t，分别构造两个 0/1 数组：

• A[i] = 1 当且仅当 s[i] == c；
• B[i] = 1 当且仅当 t[i] == c。

那么对于某个偏移 k，s 中字符 c 和 t 旋转后字符 c 的匹配数量，就是 sum_{i=0}^{n-1} A[i] * B[(i+k) % n]。这个式子的形式非常像卷积，只是下标带了一个取模。处理方法也很常规：把 B 复制一份变成 B2，长度 2n，其中 B2[i] = B[i % n]，然后对 A 和 B2 做一次标准卷积。卷积结果中某个位置的值，就对应了某个偏移下字符 c 的匹配次数。

把 26 个字符的匹配次数分别算出来，累加，就得到了每个偏移下的总匹配数。总匹配数最大的偏移，就是需要修改字符数最少的旋转方式，答案就是 n - maxMatch。

用 FFT 做一次卷积的复杂度是 O(n log n)，跑 26 次就是 O(26n log n)，在 n = 10^5 级别下完全可行。如果你不会手写 FFT，用 NTT 或者直接用一个库里封装好的卷积函数也可以，思路不变。

3.3 代码实现与边界处理

#include <bits/stdc++.h> using namespace std; // 假设已经实现 vector<double> convolution(vector<double> a, vector<double> b) // 内部是 FFT 标准流程 int minChanges(string s, string t) { int n = s.size(); vector<double> match(n, 0); // match[k] 表示偏移 k 的匹配数 for (char c = 'a'; c <= 'z'; c++) { vector<double> A(n, 0), B(2 * n, 0); for (int i = 0; i < n; i++) if (s[i] == c) A[i] = 1.0; for (int i = 0; i < 2 * n; i++) if (t[i % n] == c) B[i] = 1.0; vector<double> C = convolution(A, B); for (int k = 0; k < n; k++) { // 取卷积结果中与偏移 k 对应的位置 match[k] += C[n - 1 + k]; } } double best = 0; for (int k = 0; k < n; k++) best = max(best, match[k]); return n - (int)(best + 0.5); }

这里最容易写错的是卷积结果的下标。A 长度为 n，B2 长度为 2n，卷积结果长度为 3n-1。我们需要的偏移 k，对应的是 A 的最后一个元素与 B2 中第 k 个元素对齐的那个位置，按下标计算就是 n-1+k。不放心的话，可以先拿 n=3 的小数据手算一遍验证。

另外有两个边界要注意：

• n=1 的时候循环同构只有一个结果，直接比较即可，卷积也能跑通但没必要；
• 浮点误差会影响取整，最后用 best + 0.5 再转 int，不要直接 int(best)。

4. 树上路径颜色众数：莫队上树

4.1 树上路径为什么难处理

这道题是一棵带颜色的树，每个点有一种颜色，多次询问，每次给两个点 u 和 v，问路径 u->v 上出现次数最多的颜色是什么，以及出现次数是多少。

看到“树上路径 + 区间查询”的第一反应，往往会想到树链剖分加线段树。这确实能做，但问题在于众数这个信息不好合并。两个区间各自出现最多的颜色，合并到大的区间后，答案可能变成某个两边都出现但到中间才累积起来的“第二颜色”，线段树维护起来很麻烦。

另一种思路是树上莫队。原理很巧妙：先对树做一次欧拉序，把每个点在第一次进入和最后一次离开时各记录一次，得到一个长度为 2n 的序列。这样任意一条树上路径，都可以映射成这个序列里的某一段区间或者两段区间的组合。剩下的问题就变成了普通的序列莫队：在区间里动态加入和删除元素，维护每种颜色的出现次数，以及“出现次数为 x 的颜色有多少个”。

4.2 欧拉序转换与 LCA 的特殊处理

具体映射规则是这样的。我们用 st[u] 表示进入 u 时记录的位置，ed[u] 表示离开 u 时记录的位置，序列里每个点出现两次。

对于一次询问 (u, v)，假设 st[u] > st[v]，就先交换一下。如果 u 是 v 的祖先，也就是 lca(u, v) == u，那么对应的询问区间就是 [st[u], st[v]]。否则，路径需要拆成 u 到 lca 和 v 到 lca 两段，映射到序列上就是 [ed[u], st[v]]，同时还要额外把 lca(u, v) 加进来。

为什么是 ed[u] 而不是 st[u]？因为 st[u] 到 st[v] 这段区间里，会包含一些不属于路径的分支节点。在欧拉序的机制里，把 u 的出点作为左端点，就能把已经结束遍历的分支排除掉。这个细节我第一次写树上莫队时想了很久，后来验证了几个例子才完全明白。

还有一个关键点是：在莫队维护区间时，一个点如果在区间内出现了两次，相当于这个点不在路径上，它的颜色贡献应该抵消。所以我们维护的不是“点的个数”，而是“出现次数的奇偶状态”。每次在序列中遇到一个点，就根据它当前是否已经在区间里来决定加入还是删除；cnt[color] 随之变化，再同步更新 freq[出现次数]。

4.3 核心代码框架与复杂度

void add_position(int pos) { int u = euler[pos]; vis[u] ^= 1; // 奇偶切换 if (vis[u]) { int c = color[u]; freq[cnt[c]]--; cnt[c]++; freq[cnt[c]]++; } else { int c = color[u]; freq[cnt[c]]--; cnt[c]--; freq[cnt[c]]++; } }

每次添加或删除一个位置，cnt 和 freq 的更新都是 O(1) 的。查询当前众数出现次数时，只需要从当前维护的最大值开始向下找第一个 freq 非零的位置。因为众数出现次数会随着区间变化小幅波动，从 maxNow 往下搜的均摊代价可以接受，整体复杂度是 O((n + q) sqrt(n))，在 n 和 q 都是 2*10^5 级别时可以跑过。

实现时我建议先把树建好，预处理 lca 的倍增表，然后再做欧拉序。块大小取 2n / sqrt(q) 左右效果比较好，取太大或太小都会让排序后的移动距离变大。这个问题我从一开始就忽略了，后来对着数据调了块大小才稳定通过。

5. 背包容量巨大但体积很小：同余最短路

5.1 为什么是完全背包却不能真用完全背包

这道题表面上是背包：有 n 种硬币，每种硬币面值不超过 100，数量无限，问在区间 [L, R] 内有多少种金额可以被凑出来。L 和 R 可以到 10^18 这个级别。

看到“无限数量”，第一反应是完全背包。但完全背包的复杂度是 O(n * 容量)，容量都到 10^18 了，直接做是绝对不可能的。这里有一个非常巧妙的经典套路：因为硬币面值都很小，所以我们可以取其中最小的面值 mn，把所有金额按模 mn 分成 mn 个同余类。如果某个金额 x 能被凑出来，那么 x + mn 也一定能被凑出来，因为再放一枚面值为 mn 的硬币就行。

这样一来，问题就变成了：对于每个同余类余数 r，我们只需要知道能被凑出的最小金额 dist[r]。只要知道了 dist[r]，这个余数下所有大于等于 dist[r] 的金额都能被凑出来，区间计数就直接等差数列求数量。

5.2 把问题建模成最短路

怎么求每个余数对应的最小可达金额？方法是在模 mn 的意义下建图。图有 mn 个节点，编号 0 到 mn-1。对每个节点 x 和每种硬币面值 a_i，连一条从 x 到 (x + a_i) % mn 的有向边，边权是 a_i。

这条边的含义是：如果当前能凑出的金额是 y，且 y % mn == x，那么再加一枚 a_i 硬币，就能凑到 y + a_i，而 y + a_i 对 mn 取模就变成了 (x + a_i) % mn。从起点 0 出发跑最短路，dist[x] 就是模 mn 余 x 的最小可达金额。因为所有边权都是正数，用 Dijkstra 就行。

这里可能有人会问：为什么图上的边权跨度不影响正确性？边权直接取硬币面值而非取模后的值，是因为我们要算的是“真实金额”，不能把多余的进位丢掉了。模 mn 只是用来划分状态，边权必须保留真实代价。

5.3 正确性分析与实现细节

正确性的核心只有一句话：任意一个能被凑出的金额，在模 mn 意义下一定对应某个节点，并且这个金额一定不会小于该节点对应的 dist[x]。反过来，只要 dist[x] 可达，那么 dist[x] + k * mn 都可达，因为每加一枚 mn 硬币都能让余数保持不变。

所以对每个余数 x，如果 dist[x] <= R，那么它在 [L, R] 内能凑出的金额个数为：

(R - dist[x]) / mn - (L - 1 - dist[x]) / mn

如果 dist[x] > R，贡献就是 0。这个公式本质上就是“区间内包含多少个与 dist[x] 同余且不小于 dist[x] 的数”。

实现时有几个坑需要特别注意：

• mn 可能等于 1，此时图只有一个节点，Dijkstra 直接退化为一次判断，特判一下；
• dist 数组的初始值不能用 int 的 0x3f3f3f3f，因为金额可以很大，用 long long 的 INF 初始化；
• 建图不需要真开邻接表，直接在 Dijkstra 内部遍历所有硬币面值转移即可，因为 n 很小而 mn 最多只有 100。

vector<long long> dist(mn, INF); priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq; dist[0] = 0; pq.push({0, 0}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d != dist[u]) continue; for (int i = 0; i < n; i++) { int v = (u + coin[i]) % mn; if (dist[v] > d + coin[i]) { dist[v] = d + coin[i]; pq.push({dist[v], v}); } } }

这题最精彩的地方在于，它把“数论取模”和“图论最短路”两个看似无关的领域结合了起来。你如果只看硬币面值很小这个条件，很难联想到建图；但一旦想到了取模分类的思路，整个题目就变得非常自然。

6. 最小瓶颈路：MST + 树上倍增

6.1 最小瓶颈路的定义与结论

最后一道想聊的是图论题。给定一张 n 个点 m 条边的无向图，每条边有一个边权，多次询问 u 到 v 的所有路径中，边权最大值最小是多少。

这是很经典的最小瓶颈路问题。结论先说：一张无向图中，任意两点之间所有路径的“最小化最大边权”，等于这两点在原图的最小生成树（MST）上唯一路径的最大边权。换句话说，答案就在 MST 上。

这个结论的证明可以用 Kruskal 的加边过程来理解。Kruskal 每次按边权从小到大尝试加入一条边，并用并查集维护连通性。当某条边 e 的加入第一次使得 u 和 v 连通时，说明在加入这条边之前 u 和 v 还不连通，而所有边权小于等于 e 的边都无法把 u 和 v 连起来。因此，从 u 到 v 的任何路径，必然至少经过一条权重大于等于 e 的边，而 e 本身就是一条可以连通它们的边，所以 e 的权值就是答案。

这个观察非常本质，相当于在最小生成树的生长过程中，动态维护了“任意两个集合之间的瓶颈值”。最终落到 MST 上，两点路径的最大边权就是他们的最小瓶颈值。

6.2 为什么答案在 MST 上而不是最短路

这里最容易和普通最短路混淆。普通最短路求的是路径上所有边权和最小，而最小瓶颈路求的是路径上边权最大值最小。两者完全不同。

举个例子，两条路径，一条由三条权值为 5 的边组成，另一条由一条权值为 10 的边组成。按最短路，第一条总权 15，比 10 大，所以最短路是第二条；但按瓶颈路，第一条最大边是 5，比第二条的 10 小，所以瓶颈路是第一条。因此不能直接用最短路算法做。

最小生成树之所以适用于瓶颈问题，是因为 MST 的“最小”是全局最小连通结构，它的连边方式天然保证了任意两点之间的连通“成本”已经被降到最低。这个性质在竞赛里常被用来压缩图上问题的规模：一旦把原图变成 MST，图从 m 条边缩小到 n-1 条边，很多问题都会好做很多。

6.3 树上倍增查询与实现要点

既然答案落在 MST 上，后续就变成了树上问题：多次询问树上两点路径的最大边权。这个可以用树上倍增在 O(log n) 内回答。先对 MST 做一次 DFS，预处理每个节点的深度 depth[u]、倍增祖先 up[u][j]，以及从 u 到 up[u][j] 这段路径上的最大边权 mx[u][j]。

查询 u 到 v 时，先把更深的节点往上跳到同一深度，过程中不断记录当前跳过的路径最大值，然后两个节点一起向上跳到 LCA，同样记录最大值。最终得到的就是路径最大边权。

int query(int u, int v) { int ans = 0; if (depth[u] < depth[v]) swap(u, v); for (int j = LOG - 1; j >= 0; j--) { if (depth[up[u][j]] >= depth[v]) { ans = max(ans, mx[u][j]); u = up[u][j]; } } if (u == v) return ans; for (int j = LOG - 1; j >= 0; j--) { if (up[u][j] != up[v][j]) { ans = max(ans, max(mx[u][j], mx[v][j])); u = up[u][j]; v = up[v][j]; } } ans = max(ans, max(mx[u][0], mx[v][0])); return ans; }

这个代码模板在很多题目里都能直接套用，但要提醒两点：

• 如果原图不连通，需要对每个连通块分别建树，否则孤立点的 depth 和 up 数组会访问异常；
• DFS 深度过大时可能爆栈，省赛现场如果测评环境比较旧，建议把 dfs 改成显式栈，或者在本地改成非递归写法再交。

7. 比赛中的常见坑与排查速查表

7.1 我这次比赛里实际踩过的几个坑

先把丑话说在前头，省赛题目难度不大，但小坑一点都不少。我自己在补这几道题的时候，就重新踩过几遍，现在列出来当作反面教材。

第一个坑是求中位数那题，我一开始用了平均数去算样例，样例居然几个都对了，结果到随机大数据直接 WA。后来仔细一查，才发现平均数在绝对值和问题上完全不成立。这个错误比较典型，很多新手都会犯，但问题是它不容易通过小样例暴露，必须靠推导确认。

第二个坑是循环同构题的卷积下标。我在 FFT 实现里把取结果位置写成了 C[n+k]，而不是 C[n-1+k]，导致 n=2 的小数据能过、n=3 开始全错。后来写了一小段对拍程序，专门拿 n 从 1 到 10 的所有小字符串去和暴力结果对比，才把下标关系彻底弄明白。这也让我养成了一个好习惯：涉及卷积的题，一定先和暴力对拍，再交正式数据。

第三个坑是树上莫队的区间包含规则。我当时忘记处理“区间内出现两次的节点要抵消”的逻辑，导致众数计数翻倍。这个问题的本质是欧拉序里每个节点会出现两次，你不能简单地把两个位置都当成普通元素加进区间。

还有同余最短路里 dist 初始化不够大的问题。一开始用了 0x3f3f3f3f，也就是大约 10^9，但 R 可以到 10^18，导致一些大金额的同余类无法正确统计。改成 LLONG_MAX / 4 之后才好。

7.2 一份可直接抄的速查清单

我把这次比较典型的坑整理成一张表，之后比赛前扫一眼也算给自己提个醒。

这张表不是理论，而是每个问题都能在真实比赛中遇到的实际教训。省赛的题往往不会在算法上卡你，真正卡人的反而是这种细节。

最后再分享一点补题的小习惯

我个人补题的习惯是这样：先把题目当成一场独立的模拟赛来做，不直接看题解，卡在一个地方超过一小时，再去看别人的思路。看完思路之后也不急着抄代码，而是合上题解，自己从头推一遍。这个过程中，我会特别留意自己第一次卡住的那个点，把它记在题解的旁边。

平时刷题我也喜欢看一些高质量博主的思路讲解，比如灵茶山艾府这类能把复杂问题拆成小模型来讲的，对培养“题目模型化”的感觉帮助很大。这篇笔记里好几处地方，其实都受了这种方法的影响。

补题这件事，真正有意义的不是“我学会了这道题”，而是“我记住了我在哪一步卡住了”。把它记录下来，下次遇到类似的结构，你的反应速度会明显快一截。希望这篇题解能对你有点用，也欢迎你来和我讨论不同的做法。