ICPC省赛五类算法题解：贪心、字符串、树上莫队、最短路与MST

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); vectorlong 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^14int 必炸。排序别漏。求中位数不排序就是白给。偶数个数据时取 a[n/2] 还是 a[n/2-1] 都行但不要取 a[n/21]会越界。3. 字符串题循环同构最少修改次数3.1 题目描述与暴力解法这道题是典型的“题意一眼就懂做法要想一想”的类型。大意是给定两个长度相同的字符串 s 和 t你允许把 t 循环移位任意多次问最少修改 s 中的多少个字符能让 s 和移位后的 t 完全相同。所谓的循环移位就是把 t 的最后一个字符挪到最前面或者反过来本质上是考虑 t 的所有旋转结果。题目让我们求所有旋转里与 s 不同字符数最少的那一个。最先想到的自然是暴力枚举偏移量 k从 0 到 n-1然后逐个位置比较 s[i] 和 t[(ik)%n]统计不同的个数最后取最小值。这个做法复杂度是 O(n^2)如果 n 只有几千完全可以直接过但省赛的数据显然不会这么客气n 到 10^5 级别时O(n^2) 是铁定超时的。所以真正的考点是怎么一次性算出所有偏移下的匹配数。3.2 用卷积一次性算出所有偏移的匹配数这里要用到一个竞赛里很常见但很多人不熟的技巧把字符匹配转换成卷积。我们先只考虑一个特定字符 c。对 s 和 t分别构造两个 0/1 数组A[i] 1 当且仅当 s[i] cB[i] 1 当且仅当 t[i] c。那么对于某个偏移 ks 中字符 c 和 t 旋转后字符 c 的匹配数量就是 sum_{i0}^{n-1} A[i] * B[(ik) % 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; // 假设已经实现 vectordouble convolution(vectordouble a, vectordouble b) // 内部是 FFT 标准流程 int minChanges(string s, string t) { int n s.size(); vectordouble match(n, 0); // match[k] 表示偏移 k 的匹配数 for (char c a; c z; c) { vectordouble 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; vectordouble 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 长度为 nB2 长度为 2n卷积结果长度为 3n-1。我们需要的偏移 k对应的是 A 的最后一个元素与 B2 中第 k 个元素对齐的那个位置按下标计算就是 n-1k。不放心的话可以先拿 n3 的小数据手算一遍验证。另外有两个边界要注意n1 的时候循环同构只有一个结果直接比较即可卷积也能跑通但没必要浮点误差会影响取整最后用 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。vectorlong long dist(mn, INF); priority_queuepairlong long, int, vectorpairlong 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[nk]而不是 C[n-1k]导致 n2 的小数据能过、n3 开始全错。后来写了一小段对拍程序专门拿 n 从 1 到 10 的所有小字符串去和暴力结果对比才把下标关系彻底弄明白。这也让我养成了一个好习惯涉及卷积的题一定先和暴力对拍再交正式数据。第三个坑是树上莫队的区间包含规则。我当时忘记处理“区间内出现两次的节点要抵消”的逻辑导致众数计数翻倍。这个问题的本质是欧拉序里每个节点会出现两次你不能简单地把两个位置都当成普通元素加进区间。还有同余最短路里 dist 初始化不够大的问题。一开始用了 0x3f3f3f3f也就是大约 10^9但 R 可以到 10^18导致一些大金额的同余类无法正确统计。改成 LLONG_MAX / 4 之后才好。7.2 一份可直接抄的速查清单我把这次比较典型的坑整理成一张表之后比赛前扫一眼也算给自己提个醒。问题原因解决办法贪心题用平均数目标是最小化绝对值和排序后取中位数卷积结果下标错位FFT 结果位置与偏移对应关系理解不到位小数据对拍验证 n-1k 的取法树上区间重复计数欧拉序每个点出现两次用 vis 数组维护点是否在区间内dist 初始化偏小大金额场景下 INF 不够大用 LLONG_MAX / 4树上 dfs 爆栈链式数据导致递归过深显式栈或非递归 DFS未判断 mn 1同余最短路退化为单点加特判分支图不连通时倍增越界孤立节点的 up/depth 未处理多个连通块分别 DFS 并初始化这张表不是理论而是每个问题都能在真实比赛中遇到的实际教训。省赛的题往往不会在算法上卡你真正卡人的反而是这种细节。最后再分享一点补题的小习惯我个人补题的习惯是这样先把题目当成一场独立的模拟赛来做不直接看题解卡在一个地方超过一小时再去看别人的思路。看完思路之后也不急着抄代码而是合上题解自己从头推一遍。这个过程中我会特别留意自己第一次卡住的那个点把它记在题解的旁边。平时刷题我也喜欢看一些高质量博主的思路讲解比如灵茶山艾府这类能把复杂问题拆成小模型来讲的对培养“题目模型化”的感觉帮助很大。这篇笔记里好几处地方其实都受了这种方法的影响。补题这件事真正有意义的不是“我学会了这道题”而是“我记住了我在哪一步卡住了”。把它记录下来下次遇到类似的结构你的反应速度会明显快一截。希望这篇题解能对你有点用也欢迎你来和我讨论不同的做法。