周末刷完信友队办的这场趣味网络邀请赛，趁热把四道题完整复盘了一遍。邀请赛总共四道题，限时三个小时，整体风格很对我的胃口——它不堆冷门算法，而是更看重你能不能从题目描述里扒出那个隐藏的关键性质。这篇题解按我实际做题的顺序来写：第一题是思维题，第二题是区间DP，第三题是最短路建模，第四题是贪心证明，覆盖的正好是竞赛里最常出现的几类“卡壳点”。如果你正在准备省选，或者想从“背模板”过渡到“会想性质”，这篇复盘应该能给你一些参考。

1. 四道题考点一览：这场趣味赛到底在考什么

1.1 题量与难度分布，适合什么人打

整场比赛的题量控制得比较克制，四道题分别对应四个完全不同的方向：数学建模、动态规划、图论、贪心。难度梯度也比较典型：T1是全场最简单也最吃灵感的签到题，T2和T3是中等题，T4表面上像模拟，实际上要绕一个弯子才能想到线性做法。

从题目风格能看出命题人有明显的教学意图，每道题都在提醒你：先想清楚模型在发生什么，再动手写代码。前两题即使完全没有接触过高级算法，靠朴素模拟也能拿到一部分分，但满分做法都需要一个关键步骤的优化。T3是标准模板题，用来保底送分，但数据范围又逼着你把堆优化Dijkstra写利索。T4则是典型的“暴力思路好想、满分证明难写”的题，适合用来练习贪心正确性的论证。

对正在备战省选的同学来说，这套题最大的价值是让你审视自己能不能快速把问题“翻译”成熟悉模型。T1考的是等价变换，T2考的是区间DP的常规破环技巧，T3考的是最短路建模，T4考的是反直觉贪心。四个考点恰恰是竞赛里最高频的几类“思路转折点”。

1.2 四题考点与关键难点拆解

先放一张总览表，后面逐题展开。

这四道题放在一起吃，能明显感觉到命题人希望选手建立一种习惯：拿到题不要急着套模板，先画出状态变化的过程，找到不变或者等价的量。T1的经典蚂蚁题如果不做等价转换，现场模拟会越写越乱；T2如果把环拆成四条链硬做，复杂度直接爆炸；T3如果说“这不是BFS吗”，遇到带权边就会挂；T4如果真去枚举每个起点模拟，数据范围一大就只能拿部分分。四道题都是在逼同一个能力：模型抽象。

2. 蚂蚁回巢怎么秒掉：把“相遇掉头”想成“互相穿过”

2.1 题目描述与第一反应

一根长度为 L 的水平木杆上，有 n 只蚂蚁，每只初始位置固定，头朝左或右，速度都为 1。任意两只蚂蚁相遇时，都要同时原地掉头继续走。问：从开始到所有蚂蚁全部离开木杆，总共需要多少时间。数据范围是 n 不超过 200000，L 可以达到 1e9，显然不允许按时间模拟。

我第一眼看到“相遇掉头”这四个字，脑子里第一个念头是：这下麻烦了，得把每一只蚂蚁的位置、方向都记下来，一个个判断相遇时刻，再用优先队列模拟。这样虽然是可做的，但复杂度很难压到可接受范围，而且代码细节非常多。比赛时我习惯先问自己一句：这个问题的哪个部分是不重要的？掉头看起来是行为变化，但对整个系统的“清空时间”来说，蚂蚁之间有没有发生碰撞，真的会改变最终时刻吗？

2.2 核心观察：掉头等价于穿过

关键观察其实很朴素：两只蚂蚁迎面相撞，各自掉头，等价于它们互相穿过对方、继续按原来的方向走。区别只在于“身份”交换了——如果你不去区分蚂蚁的编号，只看整个杆子上还有没有蚂蚁，这两种情况是完全相同的。

为什么？假设有两只蚂蚁 A 和 B，A 朝右、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[i+n] = a[i]。任何一段长度为 n 的连续区间 [i, i+n-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[k+1][r] + sum(l, r) )

其中 k 从 l 取到 r-1，sum(l, r) 表示区间 [l, r] 内所有石子的总重量。为什么转移式里要加 sum(l,r)？因为无论你怎么把左右两堆合并出来，最后总要把这两堆合并成一大堆，这一步的实际代价就是当前两堆的重量之和，也就是区间整体的重量和。区间和用前缀和 O(1) 查询，避免每次暴力累加。

枚举顺序要注意：区间长度从小到大，而不是直接从 l 开始乱枚举。因为计算长区间时要依赖短区间的结果。长度从 2 枚举到 n，左端点从 1 枚举到 2n-length+1，分割点再从左端走到右端。核心代码：

#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; vector<ll> 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; vector<vector<ll>> dp(2 * n + 1, vector<ll>(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，前缀和也要算到 2n，dp 矩阵开 2n+1 大小，避免访问越界。这类细节在比赛里出错非常隐蔽，因为它只在边界数据上炸。

3.5 现场翻车与优化思路

我写这题时犯了一个低级错误：初始化 dp 矩阵时把所有值都设成了 0，结果算 len=2 的区间时，dp[l][k] + dp[k+1][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 而用堆优化 Dijkstra

n 和 m 的范围如果到 2e5，SPFA 在最坏情况下会退化到 O(nm)，被卡是家常便饭。堆优化 Dijkstra 的复杂度是 O(m log n)，稳定得多。题目边权都为正数，不需要处理负边，所以没有理由不用 Dijkstra。

实现时我习惯用一个结构体数组存邻接表，用pair<long 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; vector<vector<pair<int, 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}); } vector<ll> dist(n + 1, 1LL << 60); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, 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 出发到不了 i+1 这个位置。

这里有一个反直觉的点：如果从 start 走到 i 时油量为负，不仅 start 这个起点不行，区间内 [start, i] 中的任何一个位置作为起点，都不可能顺利通过 i+1。为什么？你可以这样想，从 start 到某个中间点 j 时，剩余油量至少为 0，否则之前就已经失败了；也就是说，从 j 出发时的初始油量不会比从 start 出发更“富有”。既然从 start 出发都撑不过 i 到 i+1，那么从 j 出发，带着更少的油量，更不可能撑过去。所以一旦某个前缀和变负，唯一可能重新开始的点只有 i+1。

5.3 线性扫一遍贪心求起点

基于上面的结论，做法就很清楚了。先算总油量和总消耗量，如果total < 0，那没有任何起点能跑完一圈，直接输出无解。否则，从 0 开始扫描，维护当前起点 start 和当前累计油量 cur。每扫到一个位置，执行cur += a[i] - b[i]。如果 cur 变成负数，就把 start 更新为 i+1，同时把 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; vector<ll> 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 = -1，start 更新为 1，cur 清零；扫到 i=1，cur = 2-1 = 1，没问题。输出 start=1，也就是第二个加油站，模拟一遍确实能跑完。这种小样例虽然简单，但能在整个数组上验证前缀清零的“跳出”逻辑，我建议每道贪心题都先手搓一个边界用例再交。

6. 赛后复盘：三小时怎么分配，五类小坑别踩

6.1 我这场比赛的做题顺序与时间分配

我个人的习惯是先把四道题全部读一遍，不急着写代码。T1一眼看出是经典蚂蚁题，用了大概 15 分钟写完；T2读完意识到是区间DP，但被环形结构卡了一下，中间还因为初始化问题调了十分钟，前后花了接近 40 分钟；T3是最短路模板题，写完一共 25 分钟；T4的贪心证明让我纠结了比较久，写完时大概已经过去两个小时。最后剩余的时间用来对拍T4和检查前面代码的数据范围。

这个时间分配其实偏保守，主要原因是我在T4的贪心证明上花得比较多。如果大家遇到类似比赛，我的建议是：先把所有题的暴力分拿全，再去死磕满分做法。尤其像T4这种题，如果你对贪心证明不够自信，可以先写一个 O(n^2) 的暴力对拍，能极大提升正确率。

6.2 竞赛现场最容易翻车的五个细节

这场四题做下来，我整理出五个高频翻车点，比赛时每一条都值得在提交前过一遍：

第五个坑在T3里尤其隐蔽。如果题目保证了所有点都能从起点到达，那么 dist 数组里不会出现 INF，直接取最大值输出即可。但如果题目没有明说，就要在最后扫描输出时检查一遍，任何一个 dist 还是 INF 就意味着消息传不到，应该输出 -1 或者按题意处理。

6.3 赛后补题：同类型的经典题推荐

如果这场邀请赛让你觉得某些题还差一点熟练度，可以找这些方向的题补一补。蚂蚁题对应“等价变换”能力，可以练一些经典碰撞类问题，比如杆上多只球碰撞、两车相遇掉头之类的变体；石子合并对应区间DP，洛谷和很多OJ上都有成套的环形DP题目，建议从线性石子合并开始，再做环形版本，最后挑战括号序列一类的区间模型；最短路这题想加深的话，可以练带负权图、多源最短路和分层图最短路；加油站题的贪心本质是“前缀和最小点开始”，可以找找类似环形数组分段问题，比如循环数组最大子段和。

补题不需要贪多，每类题找三到五道吃透，比盲目刷一百道重复题目有效得多。

作为赛后收尾，再说一点个人体会：这种趣味邀请赛最让我舒服的地方，是它愿意在题目里留出“想通了就瞬间变简单”的顿悟空间。打比赛久了你会发现，硬件模板熟练度只是底线，能不能在高压下做出正确的模型等价，才是区分选手档次的关键。T1的蚂蚁题如果一上来就模拟，五分钟就能写出一个看似正确但永远跑不完的代码；想通穿过模型的那一刻，它才真正变成一道签到题。这也是我为什么建议大家在平时训练里多花时间做“题目翻译”的练习，把一个看起来很动态的过程，用题目里隐藏的不变量变成静态问题。下次再遇到这种趣味赛，不妨先合上题目，在草稿纸上画一画模型，再决定写什么算法，说不定几道题的代码量加起来还不到两百行。