CSP2026 游记

· · 生活·游记

只考了 S。

开场瞄了一下四个题，发现后面三个怎么都有点像图论？没有数学，感觉比较放心。

先做 T1，因为我比较谨慎所以 15min 才弄完。然后去读 T2，发现 n\le 500 而且坐地铁不需要时间，马上就想到处理转两条线路的最短时间。看了下询问发现刚好可以 O(qd^2)，基本确定是对的。但是刚开始脑抽了，还想每个点 O(d^2) 更新两两间最短时间，反应了一会发现 O(d\sum k_i) 就可以做完。于是开始写，20min 写完调完。因为脑抽那一下，时间差不多过了 50min~1h 了。

然后开 T3。看完题直接尝试分析条件，画着画着感觉发现了好多条件，最后给整理了一下，发现简单的有点不对劲？但是鉴于代码好写还是写了一下，测了第一个样例马上发现我没考虑路径最短的条件。还好实在是太简单了只浪费了 30min。然后重新分析，猜了一些简单一点的性质但是都被自己 hack 掉了。此时大概 1.5h 多一点，最后我决定还是先画出普遍的一个结构分析，然后画了下面的图：

上面是一条最短路径，下面是尝试找到另一条同样最短的路径。容易就发现两条路径两端相同，中间总是差 1。

然后就是整场最唐的地方来了，我先没考虑最短的时候就发现，有些时候你两条路径分叉部分如果太长，那么一定可以构造出 >2 条最短路径。然后我在上面图里也尝试了一下，发现找不出来。但是显然：

红色线也是合法的最短路径，于是此时已经必然出现 \ge 3 条了，于是可以得到这题的 key observation。

然后后面就是瞪着这个图尝试维护这个替代路径，看了 1h+ 没有什么思路，发现我这个东西连个 O(n^2) 算法都做不出来，只会个玄学 O(n^3)。最后 50min 有点慌了，放弃正解开始拼暴力。先把 AB 性质打了，B 性质不给大样例我还写了一大堆，我自己造了若干组数据也没问题就跳过了。这时只有 30~35min 了，我开始打我那个维护的算法，打了 20min+ 打完结果一堆问题，急哭了，最后突然急中生智发现建图 Floyd 就是 O(n^3) 的，紧急修改，过了大样例。还剩 5min，打了 T4 爆搜，然后调都没调一下。

最后应该是 100+[80,100]（T2 可能被卡常）+[32,40]（大概 32）+[0,15]（大概 15），直接爆炸，最高只有 255，WC 显然去不了了。

给我的一些教训：