CSP2025游记

· · 生活·游记

省流，最后 2min 过掉 T4 大样例。

Day ?

参加了 luogu 的 SCP，大概还有 30min 的时候写完了 T4 的 \mathcal O(n^3)，然后果断选择了拼性质，结果赛后冷静想了 10min 就会了 \mathcal O(n^2) 的优化，痛失 AK，哎。

Day 998244351

倒数第二场模拟赛，花了 2h 让 T4 比大众分高 20pts ，然后 T2 挂了 20pts，和 std 拍了 4269 组才出来，愤怒。

Day 998244352

最后一场模拟赛，在 T3 诡异计数上拼了 2h 获得暴力分，最后 1h 开 T4 想了 10min 发现是 LCT 板，然后细节太多不敢写，遗憾离场。

Day 998244353

上午写了点板子，下午开始颓废，先玩了下 malody，成功从 10dan 退化到不会打 joker。

晚上复建 CS，发现两年只打 \mathcal O(1) 把 CS 成功让我的 AK 只能压 3 发，愤怒，两年前我可是完美 A 段啊。速速寻找机房同学团建，打了几把 dust2 官匹，发现狙的手感还在，成功 carry（被只玩内格夫的同学气笑了）。

Day 1

上午的动车，直接睡觉，到杭州后午饭在膳当家解决，每次来杭州吃的都是这家餐馆，感觉很不错。赛前看 uoj 群，发现 ccf 换新机子，据说 oi 即将迎来 1e9 时代，终于不用担心被常数区分了，考前最后听了 アベリア，之前在周榜看到的，感觉很治愈。

进考场，发现周围坐了很多自己认识的人，心态很平和，上次 NOIP 因为误删文件直接结束赛季，这一次，会赢吗?

-5min

密码是 人杰地灵，但是我只解压了外面一层，以为内层的压缩包有另一个密码，痛失 2min。

0min

看题，这个 T1 怎么看起来很难，T2 估计不会很难，T3 怎么是串串，T4 是计数，CSP 又考串串又考计数，这么色。

5min

tmd，怎么周围人都开始写了，键盘声好响，我咋不会 T1。这 T1 难道不就是 agc018c 吗，但这还有多测，那不是倒闭了？急急急。

10min

冷静一下，CSP T1 考流我吃，既然有流的解法，那大概率就有反悔贪心，理性思考一下，好像会了，大概写了 10min 过掉大样例。

20min

稍微想一下就会 T2 了，毕竟开始就不在 MST 里的边一定没有贡献，那这样就是 \mathcal O(nk2^k)，感觉时间有点超，但想起考前看到 ccf 的新机子，那么就相信一下，20min 写完，测了一下极限大概是 1.5s，感觉 ccf 应该能比杭师大快一倍。

40min

分析一下 T3，大概我们把一个串对去掉 LCP 和 LCS 叫做这个串的核心，然后只有核心相同的串有贡献，此时的限制就是一个前后缀，那不是直接二维数点做完了，然后我以为是 \mathcal O(|L|\log n)，左右脑互搏了一下才发现是 \mathcal O(n\log n)，结果大概想了 30min 才开始写。

120min

写完了，然后空间被卡了，愤怒，开始卡常。

140min

稍微卡了一下，空间卡进去了，然后发现我在 trie 树上 dfs 写成 \mathcal O(|L|\sum) 了，但是改的话要加 vector 记出边，那空间不是倒闭了，摆了。

145min

发现只有 100min 不到了，想 T4，发现有一档分是 1 的个数不多，如果我枚举所有 1 选或不选的话，限制就是有些地方需要 c\ge x 或者 c<x，同时这个 x 是单增的，那么我直接记录这个 x 以及可选的转移点个数，但是如果我选了一个 c\ge x 的 c 的话我不知道什么时候这个 c 会变成 <x，那么贡献延后计算以下，等到 x 扩展的时候再给 c 定系数，那不是做完了，艹，感觉全世界都要 AK 了，大概总共想了 20min，开写。

180min

写完初版了，直接过掉样例 1，然后只能过样例 1，果断开拍，还有 1h，优势在我。

190min

怎么这么难调。

200min

怎么这么难调。

210min

怎么这么难调。

220min

怎么这么难调。

230min

艹，漏了种转移，补上就可以了。

235min

过拍了，来不及了，直接测最大样例，过了，诶不对，我好像写成 \mathcal O(n^4) 了，好像只差一个预处理下降幂。

238min

改完了，极限，还是只测了最大样例，过了，检查一下文件读写，可以，全部检查完之后大概 30s 后比赛结束了。

已经结束力，出考场，问了一下同学分数，我们学校还是一如既往的爆炸，哎。不过听说很多人 T3 写的是 ACAM，那复杂度岂不是和我没优化的一样，那应该不用担心卡常了。

坐动车回去，发现我们学校的人有快 10 个在同一个车厢，然后通过一些外交手段成功坐到了一起，然后车厢有一些神秘设计，大概就是中间一张桌子，周围坐四个人，然后我们学校占满了两张桌子，开始团建桌游，非常舒适。

Day 2

认真打了 5 把 CS，成功定段到魔王 C+，不是，我还打了一把 1v4 残局啊，定位好像已经彻底倒闭了，严肃成为描边大师。不过狙的数据还比较行，平台上还评到 A，果然，只有大狙不会欺骗我。该加训 CS 了。

别挂欧内该别挂欧内该别挂欧内该别挂欧内该别挂欧内该别挂欧内该别挂欧内该别挂欧内该别挂欧内该别挂欧内该别挂欧内该

https://www.luogu.com.cn/article/3feh3lvf

https://www.luogu.com.cn/article/kzq5zlcr