CSP2025 游记

_Acheron_ · 2025-11-02 22:27:38 · 生活·游记

第一篇 CSP 游记。

Day -10086

全停集训了，好久没有全停了，甚至不是特别适应。一直摆烂菜完了，首要任务是回复状态。

Day -1145

感觉这段时间训了个滚木，不写了。

Day -2

考前最后一场模拟赛，关于模拟赛部分不想写太多，在这里。算一定的信心场，T2 std 写 500B，而我爆写近 3k。请注意你的做法是否过于复杂。

Day -1

好无聊，板刷一遍 S 组板子，下班。

Day 0

好无聊，写了一遍擂台游戏，还没调出来/kk。

回家摆烂，这个原神异梦溶媒我要的时候一个不出，不要了又疯狂出，何意味。

任何比赛前都会失眠，你们有什么头绪吗？

Day 1

不用考 J 组还是太爽了，直接睡自然醒，起床精神还不错。早早去考场了，坐标广州六中。

在路上见到了 @Lucky_Luo 和 @DZ1000。

到考场闲的没事，瞄了一眼 J 组 T4。不是今年 T4 怎么水成这样了？？那我被接龙游戏硬控算什么？？？？

考场放行了，然而还不能进考场，进考场都快开始了，不理解。

解压密码是人杰地灵。

开赛！！开赛倒数的时候挺紧张，但看到题目冷静下来了。快速扫一遍四道题目，T1 怎么这么神秘，T2 看起来像最小生成树板子，T3 少见串串题，T4 什么答辩。

回头看 T1，马上想到了暴力贪最大，如果有个选了 \dfrac{n}{2} 个，枚举那个类型，假如是类型 0，然后按照 a_{i,0}-\max(a_{i,1},a_{i,2}) 贪心选前 \dfrac{n}{2} 个类型 0 即可。

不对，怎么过不了第三个大样例？有点慌，感觉暴力贪不太对，惶恐了 5 分钟，发现自己代码一个 3 写成了 2，改了就过了，神秘。此时 30 min。

开 T2，扫数据范围看到了 k\le 10，何意味啊，这不直接枚举状态跑最小生成树就做完了。这个 m\le 10^6 有点神秘啊，每次拿一个最小生成树跑感觉就对了，复杂度是 O(m\log m+2^knk\log nk) 的，感觉有点危险啊！发现排序可以归并，然后直接开写，写完一遍过大样例，此时应该 1h？

开 T3，神秘串串题，每次取出中间不同部分，然后相当于两边都是前缀。感觉这个东西很难刻画啊，而且感觉这个东西不弱于 AC 自动机板子题（其实是因为我没看到 t_1\ne t_2），然后对着 AC 自动机想，想不到一点，然后去搞 trie 了，感觉怎么扫描线都不太对啊！！没什么思路，先弃。

开 T4，这个状态很难定义啊，感觉要记一堆情况，只会 O(n^22^n) 是不是没救了。感觉很多部分分啊，但是发现自己还是不会性质分，只会暴力和 m\in\{1,n\}，给自己烫完了，光速写完回去看 T3。此时 2.5h。

看 T3，依旧没有头绪，发现 AB 性质都很简单啊，但是感觉真几把难写。没办法了，直接开码，在离结束还有 6 分钟的时候写完了，极限。