周末刷完信友队办的这场趣味网络邀请赛趁热把四道题完整复盘了一遍。邀请赛总共四道题限时三个小时整体风格很对我的胃口——它不堆冷门算法而是更看重你能不能从题目描述里扒出那个隐藏的关键性质。这篇题解按我实际做题的顺序来写第一题是思维题第二题是区间DP第三题是最短路建模第四题是贪心证明覆盖的正好是竞赛里最常出现的几类“卡壳点”。如果你正在准备省选或者想从“背模板”过渡到“会想性质”这篇复盘应该能给你一些参考。1. 四道题考点一览这场趣味赛到底在考什么1.1 题量与难度分布适合什么人打整场比赛的题量控制得比较克制四道题分别对应四个完全不同的方向数学建模、动态规划、图论、贪心。难度梯度也比较典型T1是全场最简单也最吃灵感的签到题T2和T3是中等题T4表面上像模拟实际上要绕一个弯子才能想到线性做法。从题目风格能看出命题人有明显的教学意图每道题都在提醒你先想清楚模型在发生什么再动手写代码。前两题即使完全没有接触过高级算法靠朴素模拟也能拿到一部分分但满分做法都需要一个关键步骤的优化。T3是标准模板题用来保底送分但数据范围又逼着你把堆优化Dijkstra写利索。T4则是典型的“暴力思路好想、满分证明难写”的题适合用来练习贪心正确性的论证。对正在备战省选的同学来说这套题最大的价值是让你审视自己能不能快速把问题“翻译”成熟悉模型。T1考的是等价变换T2考的是区间DP的常规破环技巧T3考的是最短路建模T4考的是反直觉贪心。四个考点恰恰是竞赛里最高频的几类“思路转折点”。1.2 四题考点与关键难点拆解先放一张总览表后面逐题展开。题号题目类型核心考点关键难点推荐用时T1思维 / 数学相遇模型的等价转换敢把“掉头”看成“穿过”15 分钟T2区间 DP环形 DP 的破环为链状态设计与合并代价计算35 分钟T3图论 / 最短路Dijkstra 堆优化把“同时传播”翻译成最短路25 分钟T4贪心 / 前缀和环形贪心起点证明想通为什么可以跳过中间点40 分钟这四道题放在一起吃能明显感觉到命题人希望选手建立一种习惯拿到题不要急着套模板先画出状态变化的过程找到不变或者等价的量。T1的经典蚂蚁题如果不做等价转换现场模拟会越写越乱T2如果把环拆成四条链硬做复杂度直接爆炸T3如果说“这不是BFS吗”遇到带权边就会挂T4如果真去枚举每个起点模拟数据范围一大就只能拿部分分。四道题都是在逼同一个能力模型抽象。2. 蚂蚁回巢怎么秒掉把“相遇掉头”想成“互相穿过”2.1 题目描述与第一反应一根长度为 L 的水平木杆上有 n 只蚂蚁每只初始位置固定头朝左或右速度都为 1。任意两只蚂蚁相遇时都要同时原地掉头继续走。问从开始到所有蚂蚁全部离开木杆总共需要多少时间。数据范围是 n 不超过 200000L 可以达到 1e9显然不允许按时间模拟。我第一眼看到“相遇掉头”这四个字脑子里第一个念头是这下麻烦了得把每一只蚂蚁的位置、方向都记下来一个个判断相遇时刻再用优先队列模拟。这样虽然是可做的但复杂度很难压到可接受范围而且代码细节非常多。比赛时我习惯先问自己一句这个问题的哪个部分是不重要的掉头看起来是行为变化但对整个系统的“清空时间”来说蚂蚁之间有没有发生碰撞真的会改变最终时刻吗2.2 核心观察掉头等价于穿过关键观察其实很朴素两只蚂蚁迎面相撞各自掉头等价于它们互相穿过对方、继续按原来的方向走。区别只在于“身份”交换了——如果你不去区分蚂蚁的编号只看整个杆子上还有没有蚂蚁这两种情况是完全相同的。为什么假设有两只蚂蚁 A 和 BA 朝右、B 朝左。它们相遇后分别掉头A 变成朝左B 变成朝右。如果我们把 A 的名字贴到 B 原来的运动轨迹上把 B 的名字贴到 A 原来的运动轨迹上那么从外观上看就像 A 和 B 从一开始就没有掉头只是擦肩而过。因为题目只问“所有蚂蚁离开木杆的时间”不关心具体哪只蚂蚁从哪边掉下去所以我们可以完全忽略掉头认为每只蚂蚁始终沿着初始方向匀速走到端点。这样一来第 i 只蚂蚁离开杆子的时间就非常简单如果它一开始朝左离开时间是当前位置 x_i如果朝右则是 L - x_i。最终答案取所有这些值里的最大值。更形式化一点因为每只“物理蚂蚁”在穿过模型里都等价于一个匀速直线运动的点最晚离开的那个点决定了整场运动的总时长所以答案就是所有蚂蚁沿初始方向到达对应端点所需时间的最大值。这个结论也解释了为什么不需要关心任何中间碰撞。2.3 代码与复杂度十几行就能写完代码很短但一旦想通了模型这十几行就是拳拳到肉。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long L; cin n L; long long ans 0; for (int i 0; i n; i) { long long x; char d; cin x d; long long t (d L) ? x : (L - x); ans max(ans, t); } cout ans \n; return 0; }时间复杂度 O(n)空间复杂度 O(1)完全足够跑过 200000 的数据。这个解法本身不难但它在提醒你竞赛里很多看似动态的过程只要找到一个不变量或者等价关系就能瞬间变成静态计算题。2.4 一个容易被忽略的输入细节这道题现场浪费了我几分钟原因不是模型想歪了而是卡在输入读取上。位置是整数方向是单个字符我习惯用cin x d但在某些字符环境下方向字符可能带上换行符或空格如果你直接用%c读前面残留的空白符会直接读成方向导致答案完全错乱。严格的做法是cin x d让 C 流自动跳过空白如果你用scanf记得在%c前面加空格写成scanf(%lld %c, x, d)。另一个坑是数据类型。位置和 L 都可能到 1e9计算L - x时如果不开long long在 32 位整数上会溢出变成负数答案是错的。这种纯思维题最后挂在数据范围上是最亏的。3. 环形石子合并最少花多少力气区间DP从这儿入门3.1 题意和数据范围有一圈石子一共 n 堆第 i 堆的重量为 a_i。每次只能选择相邻的两堆合并成一堆消耗的体力值等于这两堆重量之和合并后新堆的重量也等于两者之和。目标是把所有石子合并成一堆求最小消耗的总体力值。n 最大只有 300但因为是环形排列直接套线性石子合并的模板会漏情况。这个题我第一反应是“每次挑重量最小的相邻两堆合并不就完事了”——这是很多贪心思路的本能反应但很可惜这个反例一分钟就能找出来三堆石子重量分别是 8、9、10如果先合并 8 和 9代价是 17新堆 17 再和 10 合并代价 27总代价 44如果先合并 9 和 10代价 19再和 8 合并代价 27总代价 46。贪心选择的顺序不一样答案不一样所以局部最优不是全局最优。3.2 为什么贪心在这里会翻车石子合并有两种常见版本一种允许多堆石子任意合并成新堆每次代价是重量之和那是标准哈夫曼问题可以用优先队列贪心另一种就是我们这道题每次只能合并相邻两堆这个邻接限制破坏了“随时取最小”的性质。合并顺序相当于在决定这堆石子最终被“切”成左右两部分合并的次序所以问题天然具有区间结构。更直观地说你最后一步一定是把整个环分成两段然后把这两段各自身合并成两堆再合并成一大堆。所以任意一次合并都可以看作在某个区间内找一个分割点左边合成一堆右边合成一堆再把它们合并。这正好是区间DP的标准形态。3.3 破环为链两倍数组的经典技巧线性石子合并的解法是定义dp[l][r]表示把从 l 到 r 这段连续石子合并成一堆的最小代价转移是枚举中间分割点。但这里是一个环最后一堆会首尾相连如果只固定一个起点当链来做你会漏掉那些跨过“数组结尾和开头”的合并方式。破环为链的经典操作是把原数组复制一遍扩展到 2n 的长度。比如原来 a[1] 到 a[n]现在变成 a[1] 到 a[2n]其中 a[in] a[i]。任何一段长度为 n 的连续区间 [i, in-1] 都对应原环的一种“从 i 处剪开拉直”的情况。于是环形石子合并的最小代价就是所有长度为 n 的区间各自做线性合并后取最小值。这个技巧在很多环形DP题里都会用到比如环形取数、环形排队问题背下来能省很多事但更重要的是理解它为什么成立环上任意一个断开点拉直后就是一条长度为 n 的链枚举所有断点就覆盖了所有可能。3.4 DP状态、转移方程与前缀和加速设dp[l][r]为合并区间 [l, r] 内所有石子的最小体力代价。初始化时单个石子无需合并代价为 0所以所有dp[i][i] 0。转移时分两段dp[l][r] min( dp[l][k] dp[k1][r] sum(l, r) )其中 k 从 l 取到 r-1sum(l, r) 表示区间 [l, r] 内所有石子的总重量。为什么转移式里要加 sum(l,r)因为无论你怎么把左右两堆合并出来最后总要把这两堆合并成一大堆这一步的实际代价就是当前两堆的重量之和也就是区间整体的重量和。区间和用前缀和 O(1) 查询避免每次暴力累加。枚举顺序要注意区间长度从小到大而不是直接从 l 开始乱枚举。因为计算长区间时要依赖短区间的结果。长度从 2 枚举到 n左端点从 1 枚举到 2n-length1分割点再从左端走到右端。核心代码#include bits/stdc.h using namespace std; using ll long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorll a(2 * n 1), s(2 * n 1, 0); for (int i 1; i n; i) { cin a[i]; a[i n] a[i]; } for (int i 1; i 2 * n; i) s[i] s[i - 1] a[i]; const ll INF 1LL 60; vectorvectorll dp(2 * n 1, vectorll(2 * n 1, 0)); for (int len 2; len n; len) { for (int l 1; l len - 1 2 * n; l) { int r l len - 1; dp[l][r] INF; for (int k l; k r; k) { dp[l][r] min(dp[l][r], dp[l][k] dp[k 1][r] s[r] - s[l - 1]); } } } ll ans INF; for (int i 1; i n; i) ans min(ans, dp[i][i n - 1]); cout ans \n; return 0; }时间复杂度是 O(n^3)n 只有 300所以完全够用。开两个数组时要注意下标复制数组后实际长度是 2n前缀和也要算到 2ndp 矩阵开 2n1 大小避免访问越界。这类细节在比赛里出错非常隐蔽因为它只在边界数据上炸。3.5 现场翻车与优化思路我写这题时犯了一个低级错误初始化 dp 矩阵时把所有值都设成了 0结果算 len2 的区间时dp[l][k] dp[k1][r]全是 0最小值永远来自分割成单堆再合并的情况导致答案变成了“每次只合并两堆最轻的”那种错误结果。正确做法是把长度大于 1 的区间初始化为 INF只有长度为 1 的区间才是 0。另外这题其实可以用平行四边形不等式优化把枚举分割点的复杂度从 O(n) 降到近似 O(1) 的决策范围但对 300 的数据量完全没有必要。比赛中先写朴素区间DP拿分再考虑优化是更稳妥的策略。4. 消息同时传遍全网的最短时间一个典型的最短路建模4.1 题目描述与建模过程有一个 n 个节点、m 条双向边的网络每条边有一个通过时间 w。某个初始节点 s 诞生了一条消息消息沿着边向邻居传播传播是可以并行的一个节点一旦收到消息会立刻同时向所有相邻节点继续转发。问多久之后所有节点都能收到消息。这道题的关键在于看穿“并行传播”这句话。很多人第一反应是“那不就是多源BFS嘛”但 BFS 的前提是边权都为 1。这里每条边通过时间不同BFS 的队列按层展开就不再正确。实际上一个节点最早收到消息的时间就是节点 s 到它的最短路径长度。因为消息在每条边上的传播时间就是边权所有边同时开始传播等价于从起点到每个点有多条路径消息一定沿着最早到达的那条路径传播。所以答案就是起点到所有点的最短路径中的最大值。这个建模是竞赛里特别经典的“翻译题”把“并行传播”翻译成“最短路”。一旦翻译完成剩下的就是板子。4.2 为什么不用 SPFA 而用堆优化 Dijkstran 和 m 的范围如果到 2e5SPFA 在最坏情况下会退化到 O(nm)被卡是家常便饭。堆优化 Dijkstra 的复杂度是 O(m log n)稳定得多。题目边权都为正数不需要处理负边所以没有理由不用 Dijkstra。实现时我习惯用一个结构体数组存邻接表用pairlong long, int存“到当前点的距离、当前点编号”优先队列用小根堆按距离排序。每次从堆顶取出当前距离最小的点如果这个距离已经比记录在 dist 数组里的值大说明该点已经处理过直接跳过否则松弛它所有相邻边。这个“懒删除”写法比较省事不用维护标记数组实测下来也没有性能问题。4.3 核心代码与几个容易写错的点#include bits/stdc.h using namespace std; using ll long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorpairint, ll g(n 1); for (int i 0; i m; i) { int u, v; ll w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); } vectorll dist(n 1, 1LL 60); priority_queuepairll, int, vectorpairll, int, greaterpairll, int pq; dist[1] 0; pq.push({0, 1}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; for (auto [v, w] : g[u]) { if (dist[v] d w) { dist[v] d w; pq.push({dist[v], v}); } } } ll ans 0; for (int i 1; i n; i) ans max(ans, dist[i]); cout ans \n; return 0; }代码里最容易翻车的几个点一是dist初始值要和 INF 匹配我写得比较大是 1LL 60防止dist[v] d w时因为 INF 不够大而漏更新二是判断if (d ! dist[u])这行如果不写同一个点可能被重复松弛多次时间会慢不少三是输出答案时注意如果图本身不连通有些 dist 还是 INF这时题目应该保证连通性否则需要先判一下有没有 INF 存在。4.4 这道题给我的一个提醒最短路模板本身不难难在建模和边界判断。我在比赛时因为开了int存距离样例一过就直接交结果在一组边权很大的数据上 WA 了。后来改成long long才通过。竞赛里边权总和超过 2^31 实在太常见了凡是涉及路径累加的题距离变量一律开long long这是用真实教训换来的习惯。5. 环形加油站选起点一个产自前缀和的贪心结论5.1 题目描述与暴力思路n 个加油站围成一个环第 i 个加油站能加 a_i 升油从第 i 个加油站开到下一个加油站要消耗 b_i 升油。车初始油箱为空油箱容量无限大你需要选择一个加油站作为起点然后按顺序走完一圈回到起点。问是否存在可行起点如果有输出任意一个。暴力的做法很简单枚举每个起点从它开始模拟一整圈中间一旦发现油量 cup 小于 0 就说明这个起点不行。复杂度 O(n^2)n 一旦到 2e5 就完全不行。这题真正要想清楚的问题是怎么快速排除大量无效起点。5.2 关键观察前缀油量变成负数的意义我们先把每个加油站的净收益记作 net[i] a[i] - b[i]也就是从 i 出发到下一站之前油箱里的油会变化多少。从某个起点 start 出发走完一圈可行的条件是任意前缀和都不小于 0。如果存在某个位置 i走到 i 时cur sum(net[start] ... net[i]) 0说明从 start 出发到不了 i1 这个位置。这里有一个反直觉的点如果从 start 走到 i 时油量为负不仅 start 这个起点不行区间内 [start, i] 中的任何一个位置作为起点都不可能顺利通过 i1。为什么你可以这样想从 start 到某个中间点 j 时剩余油量至少为 0否则之前就已经失败了也就是说从 j 出发时的初始油量不会比从 start 出发更“富有”。既然从 start 出发都撑不过 i 到 i1那么从 j 出发带着更少的油量更不可能撑过去。所以一旦某个前缀和变负唯一可能重新开始的点只有 i1。5.3 线性扫一遍贪心求起点基于上面的结论做法就很清楚了。先算总油量和总消耗量如果total 0那没有任何起点能跑完一圈直接输出无解。否则从 0 开始扫描维护当前起点 start 和当前累计油量 cur。每扫到一个位置执行cur a[i] - b[i]。如果 cur 变成负数就把 start 更新为 i1同时把 cur 清零。扫描结束后start 就是可行起点。这个算法的复杂度是 O(n)原因在于每次放弃一段前缀后新的起点直接从失败点的下一个位置继续扫过的位置不会回头所以总扫描是一次性的。5.4 核心代码与现场验证#include bits/stdc.h using namespace std; using ll long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorll a(n), b(n); for (int i 0; i n; i) cin a[i]; for (int i 0; i n; i) cin b[i]; ll total 0; for (int i 0; i n; i) total a[i] - b[i]; if (total 0) { cout -1 \n; return 0; } ll cur 0; int start 0; for (int i 0; i n; i) { cur a[i] - b[i]; if (cur 0) { start i 1; cur 0; } } cout start \n; return 0; }这里有几个细节容易踩坑第一如果无解注意输出格式是要输出 -1 还是别的占位符我一开始漏了无解分支直接白交一次第二如果题目要求输出可行起点编号是最小的那个这个贪心得到的其实就是从左往右扫出的第一个可行位置原因在于我们放弃了所有被证明不可行的前缀第三如果环的下标从 1 开始最后输出 start 时要小心是否要加 1我经常在这类环上栽跟头。现场我还做了一件事用一个最简单的样例验证贪心起点逻辑a [1, 2], b [2, 1]总油量为 0可行。从 0 开始cur 1-2 -1start 更新为 1cur 清零扫到 i1cur 2-1 1没问题。输出 start1也就是第二个加油站模拟一遍确实能跑完。这种小样例虽然简单但能在整个数组上验证前缀清零的“跳出”逻辑我建议每道贪心题都先手搓一个边界用例再交。6. 赛后复盘三小时怎么分配五类小坑别踩6.1 我这场比赛的做题顺序与时间分配我个人的习惯是先把四道题全部读一遍不急着写代码。T1一眼看出是经典蚂蚁题用了大概 15 分钟写完T2读完意识到是区间DP但被环形结构卡了一下中间还因为初始化问题调了十分钟前后花了接近 40 分钟T3是最短路模板题写完一共 25 分钟T4的贪心证明让我纠结了比较久写完时大概已经过去两个小时。最后剩余的时间用来对拍T4和检查前面代码的数据范围。这个时间分配其实偏保守主要原因是我在T4的贪心证明上花得比较多。如果大家遇到类似比赛我的建议是先把所有题的暴力分拿全再去死磕满分做法。尤其像T4这种题如果你对贪心证明不够自信可以先写一个 O(n^2) 的暴力对拍能极大提升正确率。6.2 竞赛现场最容易翻车的五个细节这场四题做下来我整理出五个高频翻车点比赛时每一条都值得在提交前过一遍细节错误表现正确做法数据范围没开 long long累加时溢出答案变成负数或大随机数所有距离、重量、代价相关变量一律 long long输入字符带空白符方向字符读到换行T1直接WA用 cin 读 char或 scanf 里加空格DP 初始化错误长区间被初始化为 0转移全错除边界外dp 数组设 INF环形数组下标越界复制数组后忘记扩展 dp 矩阵大小数组长度 2n1访问时严格检查 llen-1 2n图不连通时未判 INF输出 INF 当作答案先确认输入保证连通否则需特判第五个坑在T3里尤其隐蔽。如果题目保证了所有点都能从起点到达那么 dist 数组里不会出现 INF直接取最大值输出即可。但如果题目没有明说就要在最后扫描输出时检查一遍任何一个 dist 还是 INF 就意味着消息传不到应该输出 -1 或者按题意处理。6.3 赛后补题同类型的经典题推荐如果这场邀请赛让你觉得某些题还差一点熟练度可以找这些方向的题补一补。蚂蚁题对应“等价变换”能力可以练一些经典碰撞类问题比如杆上多只球碰撞、两车相遇掉头之类的变体石子合并对应区间DP洛谷和很多OJ上都有成套的环形DP题目建议从线性石子合并开始再做环形版本最后挑战括号序列一类的区间模型最短路这题想加深的话可以练带负权图、多源最短路和分层图最短路加油站题的贪心本质是“前缀和最小点开始”可以找找类似环形数组分段问题比如循环数组最大子段和。补题不需要贪多每类题找三到五道吃透比盲目刷一百道重复题目有效得多。作为赛后收尾再说一点个人体会这种趣味邀请赛最让我舒服的地方是它愿意在题目里留出“想通了就瞬间变简单”的顿悟空间。打比赛久了你会发现硬件模板熟练度只是底线能不能在高压下做出正确的模型等价才是区分选手档次的关键。T1的蚂蚁题如果一上来就模拟五分钟就能写出一个看似正确但永远跑不完的代码想通穿过模型的那一刻它才真正变成一道签到题。这也是我为什么建议大家在平时训练里多花时间做“题目翻译”的练习把一个看起来很动态的过程用题目里隐藏的不变量变成静态问题。下次再遇到这种趣味赛不妨先合上题目在草稿纸上画一画模型再决定写什么算法说不定几道题的代码量加起来还不到两百行。