CSP-S2026 游记

· · 生活·游记

坠机了。

13:00 到考场了，但被告知得等到 13:40 才能进考场。比较难受。

买了一个阿萨姆喝，还挺好喝的。

13:40 进考场了，开始试机。这回的机子还挺好用的，键盘打起来也舒服，敲击回馈是脆的。

14:30 开题。

首先通读题面，但是并没有通读成功。T2 题面太过诡异了，出题人真的学过中文怎么说吗？这导致我 T3、T4题面没好好读，不过没太大关系。

我终于克服了 T1 恐惧症，大概再也不会切不掉 T1 了。15min 将 T1 写完调完就开始看 T2。

我还是没读懂题面。

于是继续通读题面，通读完还是得看 T2。在草稿纸上画了画图，手膜了一下样例，总算是把题看懂了。

我给自己定的目标是 250+，这意味着我必须要切掉 T2。这也许是个错误的决策，不过现在看来也无所谓了。

我糖丸了，想了很长时间 T2。那个结论甚至是我猜出来的。

怎么猜的呢？

我把 T2 题意精简为了如下内容：你有三排点，前两排点各 m 个，第三排点有 n 个。每个第一排点都有且仅有一条边，这条边连接至第二排点中的对位点。第二排点与第三排点之间有连边，每一个第二排点至多有 d \leq 20 条连接至第三排点的边。所有连边都是无向的。q 次询问，每次询问第一排点中的第 x 个点和第 y 个点之间的最短路。

然后你发现第一排点是滚木，最后再计算就行。

然后你会发现：实际上，每一个询问中的 x 都会从 d 个出边内选择一个“起始点”，并从来自 y 的一个出边结束自己的行程。

所以我猜到了：直接计算第三排点两两间的最短路就行了。

我不知道为啥我在场上总是在想“重复边”这个东西。赛时做题和平时做题真的是不一样的感觉。

但是我一开始并没有发现这个东西，于是我写了个暴力，这个暴力是用 dijkstra 写的。所以我发现这个东西后的代码也是用 dijkstra 写的。

我写了两份“正解代码”，第一份正解代码是直接将第二排点和第三排点连接。我发现这个写法在第 6、7个大样例上会 TLE。

于是，我突然想起了不知道在哪里看见过的结论：dijkstra 的时间复杂度是 O(n \log m) 的。

所以我好像有点开智了，枚举第二排中的每个点，从 d 条出边中组合出 \binom{d}{2} 条边，并直接连接这两条出边所对的两个端点。

我甚至没有去掉重边。

可我发现这个写法对于最大的大样例都能够在 600ms 内正确运行完毕。

由于 #6 大样例是对应的 #16 点，而那个点只是有了一个特殊性质，但数据范围和最大范围是一样的。我就认为我把 T2 写出来了。

我真应该输出一下每个数据的 \sum k。

不知道会挂到多少。希望别挂太多。

dijkstra 的时间复杂度是 O((n+m) \log m)。

写完 T2 已经是考试开始后的 2h40min 了，留给 T3T4 的时间并不宽裕。

场上并没想出 T3 O(tn^2) 怎么写 /fn/fn/fn。

T3 特殊性质 B 还想错了/fn/fn/fn。

T4 的特殊性质和 O(n^2) 好像还挺简单的，但是我没有时间写了。

最终得分 100+[76,100]+32+15 = [223,247]。

有进厕所的风险吗。

没有进厕所的风险那能有 7√ 的风险吗。

7√ 要是都没有那我就跳了。