CSP2024 游记

· · 生活·游记

直接快进到进考场。

因为去年的 CSP 很简单所以我觉得今年的应该也不会很难，所以决定一道一道慢慢做。

先花了 3 分钟写缺省源，然后看 T1，发现好难。想了 5 分钟才想到一个排序贪心的方法，写完之后不知道为啥感觉大样例太弱了就写了个拍，14:50 才去看 T2。

发现 T2 可以把每辆车的超速区间处理出来，然后转化成了选最少个点使得每个区间都有被选的点。然后不知道为啥我在想一个线段树优化 dp，并且还写完了，写完之后发现大样例跑了 1s 才发现会被卡常，然后赶紧改成一个看起来很对的贪心，感觉大样例强度尚可就不写拍了（实际上是不太会写暴力）。应该差不多 15:45 才搞完。

T3 一眼就会了一个二维 dp，然后发现可以线段树优化。直接开写，写完之后发现极限数据 1s，感觉可能又会被卡常，才发现完全可以把线段树去掉。写完之后又写了一个 O(2^n n) 的暴力，和线段树一起拍。拍的时候发现了一个神秘的问题，system("color") 不会运行同一目录下的 color.exe，然后搞了好久才发现 color 原来是 windows 内置的一个命令，要 system("color.exe") 才行。搞完这个拍上之后已经差不多 16:30 了。

T4 感觉比预想中困难很多，这个时候才发现前面浪费太多时间了。先写了一个 O(Tn^2 \log n) 的暴力，然后这个显然能通过线段树 pushup 的方式做到 O(Tn \log^2 n)。感觉 \log^2 太唐了，再看看数据范围感觉小常数 O(Tn \log n) 应该能过，就想了一个自顶向下的 O(Tn \log n)。开始写的时候才发现细节很多。这个时候已经有点红温了。差不多 18:00 才写完。但是怎么样例 1 就挂了？？？调调调，怎么还是挂？？？还有不到半个小时就结束了，这个时候我已经彻底急了，好不容易把样例 1 调出来，样例 4 又挂了（甚至连答案的位数都不一样），而这时只剩下不到 5 分钟就结束了，我只能对着屏幕发呆，甚至连 O(Tn^2 \log n) 的暴力都没交。

出场的时候发现有 O(n) 个人 T4 像我一样没调出来（但是大部分人都写的是线性）。dhf 说他写出 O(Tn \log n) 了，wrx 说他 O(Tn) 没调出来，感觉全世界就我一个小丑写 O(Tn \log n) 还没调出来，破大防。

总结：策略失误，对自己太过自信了导致不够时间调 T4。以及要保持最大化得分的策略（不然我可以把 O(Tn \log^2 n) 写出来，也不至于结果这么难看）。还有考场的 Dev-C++ 用着太别扭了，希望 noip 的时候有 CP Editor 能好一点吧。