CSP-S2024 游记

· · 生活·游记

跨越山川终已至，定数无可避。

  • Day-1

教练在题单里放了 20 多个板子，写爽了。

晚饭前送来了一个大蛋糕，机房一起全切了。

晚上找到了今年三月调了五六个小时才过的序列合并，重写半个小时过了，代码还从 3k 压到 2k，赢。（但是跟我一起写的 zibenlun 对着 5k 代码一直没调出来）

上午在机房随便写了点奇怪的东西（比如用 Splay 写了线段树 1），水了点水题。

中午吃完午饭出发，路上一直在跟 zibenlun 一起听，睡了一觉，打了会集成战略。到酒店以后颓。

晚上试机，考场在 803，爬楼梯上去。但是键盘很好用，随便写了写线段树和 Tarjan 就跑了。因为没啥很熟的同学 + 社恐，没有面基。

回酒店一群人聚到一个屋准备开颓，然后被教练抓了。之后五六个人在我和 zibenlun 屋，点了蜜雪，四个人打了会集成战略，打完集就睡了。

吃了早饭就开始看各种考前提醒，写了模拟退火和对拍。一群人聚到我们屋，一块在电视上乱看，最后在看奶龙的时候被教练把电视关了。中午吃完饭睡了一会，在酒店门口拍了个合照就去考场了。

开场发现 T1 水，很快写完了。T2 仔细想了想感觉也不难，45 min 的时候写完，大样例跑了 1.1 秒。看到大样例只有一半是极限数据，开始卡常。推了个式子替掉了二分，还试了用 vector 桶排代替快排，但变慢了所以没采用。最终优化到 0.8 秒。

这时大概开场 80 min，开了 T3。由于自己很菜并且往年题不简单，所以觉得 T3 肯定切不了，直接先写了 O(TnV) 的 DP。结果仔细一看怎么这么好优化，敲了个线段树优化到 O(Tn\log V)。写之前算复杂度还算错了，以为是 4e8，但是觉得反正线段树好写，写了再说。写出来测完样例重新算了一遍才发现是 4e7，感觉能过。

此时也就开场 2h 多点，开始看 T4，这是我未曾设想的速度。读懂题以后感觉这难度不是我能做的，直接开写 n,m\le8 暴力，写完调对大概是 3h。这时我觉得 T4 太困难就直接弃了，其实 A 性质好像并不困难，但我没看。赛后发现我的暴力在 A 性质下是 O(n^2) 的，或许还能多过一点。

弃掉 T4 后就回去检查了，毕竟从未场切过这么多题，这回还是求稳了。重读了代码，确认了格式，重测了样例，在 3.5h 的时候整完了。最后把 T2T3 的代码拿出来写对拍，T2 用二分和式子拍，T3 用暴力和线段树拍，一直拍到结束也没拍出错。也可能是数据造水了之类，不管了。

如果不挂应该是 [312,320]，比去年只会暴力好多了。赛后看洛谷发现 T4 是黑，这下没冲也没啥遗憾了。

返程一直在刷 B 站，八点开始看明日方舟前瞻直播，不过此时已经有同学开始在大巴上打 ABC 了。

把前三题代码复刻了一遍，交了洛谷和云斗，结果 T3 线段树被卡 T 了。然后发现线段树就求了个前后缀最大值，改成树状数组全过了并且跑得很快，而且直接维护全局最大值也不会影响答案，寄麻了。T3 变成 [75,100]，总分变成 [287,320]。

没了，希望出分不挂，希望一个月后的 NOIP 顺利。

声闻形貌终已远，变数未可知。