CSP-S游记

· · 生活·游记

本人坐标BJ，是最后一年CSP了，为了纪念这一次于是准备详细写一下游记吧

初赛

今年考场上第一大题居然给出了两个偏数论的题目，感觉我做过的初赛题目似乎没几个会这么出

最后根据洛谷平台给出的参考答案，估分59(最终成绩也是59)，最后如愿以偿晋级复赛了，在等待北京分数线的时候，一直担心过不了，但是北京分数线48，也算是目前比较好的结局了

复赛

复赛考前，监考说要求两点才可以进入考场教室，但一点五十就放进去了，于是又被请了出来。

14:30 - 15:07

拿到卷子时，感觉四个题目都不简单，于是从头开始看 T1。

T1 我一开始题目读错了，以为是问合成次数最多，看到样例才发现是问相同的个数最多是多少个。数据范围顶多支持 O(n\log n) 的算法。我一开始只想到 O(n^2) 的暴力，后来又想到二分答案，但 check 函数写起来很复杂， 优化时还想过树状数组，但方向明显不对。写法越来越麻烦，我开始猜测贪心，但不会正确性证明，于是决定先写 O(n^2) 暴力。写完后发现可以使用双指针，不过无法系统估算复杂度。

15:07 - 16:41

看到第二个题目很像 2024csp-j 的接龙，但是又有一些区别，我开始写很暴力的 bfs ，结果在后续计算空间使用了 1839MiB 的内存，准备后续优化 。

16:41 - 16:49

开 T3 的时候没看懂怎么做，只草草写了很暴力的搜索就提交了 。

16:49 - 17:01

T4 是唯一一个让我连暴力都不会写的一个，我直接输出 0 或者 1 跳过了，实在不会这个题目 。

17:01 - 17:24

按照往年 T2 爆零的经验，检查了一下 T2 ，发现空间很大，开始着急怎么优化 。

17:50 - 18:30

上完厕所后，发现完全可以连图，跑最短路，于是开始写 Dij 最短路，每次询问跑一次，由于 n+m 点的存储，弗洛伊德完全超时，不敢写，但是 Dij 一直不输出正确答案，直到结束了我也没看出问题所在，最后一年了就还是会出现这样的问题... 。

赛后

在考完后与朋友讨论的时候说 T2 可以缩点直接弗洛伊德 。
结果就交给 CCF 测评机了。最后一年 CSP，过程值得记住，希望 RP++。