CSP-S 2026

进场之前压力巨大,非常害怕获得低下的成绩。

同一个教室里有若干位认识的同学。但偏偏坐在我右边的是一个初一小朋友,非常恼人。这家伙一直不停的试图向我搭话,全然不顾这很烦人的事实。

打开了 vmware,看上去体验不错。建立目录(反复核对准考证号),打缺省源。

搞笑的是很快要求重启电脑(验证 D:/ 的系统还原是否关闭)。于是又不得不第二次打开 vmware,重新敲缺省源。

监考老师不知为何要求在第一行注释写考场、准考证号和学校、姓名。


下发压缩包。第一次还没拿到,于是又发了一遍。看 T1,发现是唐题,20min 通过大样例。发现没有 1e18 的数据,于是检查了 long long,并手造一组样例测试无误。

T2 第一眼感觉题面非常复杂,再看一眼竟然不会。吓出冷汗。仔细想想,很快发现暴力写法。然后很快看出需要建虚点。很快发现可以跑 n 次 dijkstra 求出每个地铁到所有点的距离。发现还是过不了,很快想到跑 n 个地铁彼此间的全源最短路。很快想到对每个站厅枚举地铁线路对来求出邻接矩阵

把复杂度估计成了 $O(n^3 + m d^2 + q d^2)$。感觉有点悬,但是不管不顾就写了。反正 ultra 9 285k 很强,哪怕 3.7GHz 也一样。

(赛后发现其实是 $O(n^3 + m d + q d^2)$)

大约 15:21 过了大样例,我是码力低手 :( 回想起去年 T2 的教训,刻意观察了大样例强度。发现最后一个样例数据范围 d 很小,但倒数第二个几乎是满范围。跑了不到 400ms,显然复杂度应该能过。不过注意到大范围样例都是特殊性质,对正确性的考验不够强。

样例 3 是 n=50,m=500,没有特殊性质。应该足以检验正确性了。只是边权不需要开 long long。稍微检查一下。

同时去年 T2 告诉我们建立虚点需要让某些数组开到 m+n+eps 而不是 m+eps。进行检查。

看 T3。题面很复杂啊。先想 40pts,但是只会 24pts。看 T4,指数级做法有 15pts。

不太行,至少要会一个多项式复杂度做法。发现如果只有一个连通块是简单的,然后枚举一条边割开就可以转化为一个连通块的做法。得到 $O(n^3)$ 做法,30pts。

回去想 T3。注意到特殊性质 A,试图跟随特殊性质获取做法。想出了一些早该注意到的显然的性质,然后会了特殊性质 A,8pts。回去想暴力,会了 $O(n^2)$ 40pts。

大约是 16:45 左右。本来想再想 15min 的,但是考虑到接下来的分数都很难,应该先实现现在会的分数。

先写 T4。写完并通过大样例大约是 17:40。再写 T3。性质 A 很好写,但也调了一会,主要是没完全想明白。然后写 40pts 暴力。在 18:00 左右写完,但是没过样例。

无比紧张。一想到只剩半个小时,又想到可能调不完,就冷汗直流。但是强行压住紧张,冷静思考一下想到了正确的写法。18:16 暴力通过了样例。

仔细检查了所有四个题的文件名,目录结构,文件读写,并检查修改时间以避免意外更改。然后等待比赛结束。

vmware 也来不及用了。


估计分数 100+100+48+30。果然是一个低下的成绩。

感觉比赛策略完全正确。但是没想出 T3 是完全的实力问题。