比赛链接
分数：\(100 + 100 + 0 + 0 = 200\)
永康喵喵又没有翻车！
有了前几次翻车的教训，我形成了先写注释（对于难题）\(\rightarrow\) 仔细写题 \(\rightarrow\) 静态检查 \(\rightarrow\) 动态检查 \(\rightarrow\)（所有能做的题做完后）对拍 \(\rightarrow\) 最后核查的流程，大大降低了翻车率。
言归正传，分析题目。
T1
为什么数据这么水啊，\(n \le 50\) 是啥阴。这题明明有 \(n^2\) 做法，而且并不难，为什么不把数据范围开到 \(n \le 3000\)。
当然考场上写题速度很重要，所以我当然是暴力打 \(n^4\)。如果要 \(n^2\)，可以先计算出没有老师时的握手次数，然后枚举老师的位置，更新其周围的握手情况。握手需要 \(2\) 个人进行，所以最后不要忘了 \(\div 2\)。
T2
在变换次数比较小（\(k \le 1000\)）时，暴力的时间复杂度可以接受，可是如果变换次数达到 \(10^9\) 就会 T 飞。但是如果仔细分析变换的过程就会发现这是一个周期性变换。因此可以先暴力找到周期 \(a\)，然后将 \(k\) 对 \(a\) 取模，再进行暴力。考虑到 \(|S| \le 1000\)，如果要进一步缩短程序运行时间，甚至可以打表（我就是如此场切的）。
T3
不知道为什么 ZR 也学上了 aoao，先放两道特别水的题，然后在 T3 突然上难度，很搞人心态。
不过要是摸清了这道题的本质就不难了。今天下午我学了 Floyd 最短路算法，其本质是寻找一个中转点，然后用它更新两边点的距离。这道题也类似。我们可以设 \(f_{i, j}\) 表示当前路径的两个端点分别为 \(i, j\)，且已经访问了从 \(1\) 到 \(\max(i, j)\) 的所有点时的最小时间。初始时，\(f_{1,1}=0\)。
然后进行状态转移：
-
遍历 \(i, j\)。
-
计算下一个要访问的点 \(k = \max(i, j)+1\)。如果 \(k > n\) 则跳过。
-
更新两个新状态：
-
从端点 \(j\) 扩展到 \(k\)：路径变为 \((i, k)\)，时间增加 \(d_{j, k}\)，即 \(f_{i, k} = \min(f_{i, k}, f_{i, j} + d_{j, k})\)。
-
从端点 \(i\) 扩展到 \(k\)：路径变为 \((k, j)\)，时间增加 \(d_{i, k}\)，即 \(f_{k, j} = \min(f_{k, j}, f_{i, j} + d_{i, k})\)。
这样扩展保证了当访问点 \(k\) 时，所有小于 \(k\) 的点都已经被访问，满足限制条件。
-
输出答案时，遍历所有 \(i\)，然后取 \(f_{n, i}\) 和 \(f_{i, n}\) 的最小值作为答案。