CSPS2025邮寄

· · 生活·游记

Day -INF

几乎没停课，因为要期中考。

Day0

复习了 KMP，马拉车，平衡树，tarjan（实际一个都没考到，悲）。

注意到 AC 自动机不在提高组大纲里，于是没有复习（伏笔）。

Day1

在本校考，主场作战，天时地利人和先占了一个。

考前吃了几块巧克力，但还是莫名其妙犯困。

14:25 发题，看 T1，10^5 的数据显然贪心，先按最优方法选再贪心排序调整就行了。大概开考后 15min 过了大样例。

开 T2，完全不会做，有点慌。再看一眼，k \le 10，这不暴力枚举最小生成树就做完了。又看了一眼，发现 m 很大，似乎并不简单。但 n 很小，可以先跑一遍 kruskal 缩成 n-1 边，于是我胡出了一个 O(2^kkn) 的做法，很可能被卡常。写得还算顺利，基本一次过了所有大样例，但样例3跑了 3.8s，开了 O2 后 1.2s，写了个快读就卡进了 0.7s（伏笔）。

此时距离开考过了 1.5h，切了两题，心情愉悦。于是开 T3，居然是串串题，感觉是拼拼凑凑然后 AC 自动机，但提高组显然不考 AC 自动机，而且我考前也没复习，就没往这个方向想。然后就只会 10 分了......果断跳题看 T4，拼了个状压 + n! 就跑路了，因为特殊性质似乎并不好做。

忽然想起来看 T2 大样例强度，n 居然只有 10^3，烟斗不演了，测了一下极限数据直接跑 6s，算了一下自己其实只有 80pts。于是疯狂想这个 k 怎么卡掉，未果。此时只有 1h 了，考虑到 T3 还没分，赶紧弃掉。

T3 快速写了个 O(\sum{|t|^2}) 的做法，样例 3 跑了 13s，得分 [10,50] 不等。

最后半小时检查了一下 freopen，就收卷了。

感觉没打出什么有价值的分，估分 100+80+[10,50]+[20,20+?]=[210,250+?]，太菜了。

赛后得知 T3 真是 AC 自动机，一车人切了，唐丸了。

居然能用申诉的 bug 查分，这么有实力。

最终得分：100+80+35+20=235。比去年低了 65 分，乐。

upd：T2在赛时代码上加上两行卡时代码就过了，洛谷只用了600ms，毕竟也不是 IOI 赛制，赛时肯定不敢冒这个险