CSP-S 2025逆袭记

· · 生活·游记

Day ?-1

我要写题啊啊啊！

Day ?

初赛，不知道直接水过了。

Day -1

睡得很死。

Day 0

睡不着觉。

Day 0.5

J 组考完了，感觉挺好的，去吃了神秘 KFC。

Day 1

开场看 T1，简单想了一下 dp，发现还是贪心更可行，然后发现了一个社团可以最多有 \frac n2 个人，然后把多出来的移到次喜欢的，这样其他社团也不会超，20 分钟写出来了，然后简单证了一下就保存了。

然后看了一眼 T2，发现 Kruskal 忘了，跳过。

看了眼 T3，感觉是 ACAM，不会写，跳过。

看了眼 T4，发现有 72pts 特殊性质，写写写，然后发现只会写 12~24pts。

不知道要干嘛，突然想起来 Kruskal 是一个贪心的算法，然后随便画了几个图，发现是按边权排序，然后就去写 T2 了。

写写写写写写写写写写写写。
调调调调调调调调调调调调。

写出来了一个 O(2^km\ log\ m)，但是大样例怎么跑的这么慢？想了一下，写了一个启发式合并，然后随便剪了一点枝，变成了 O(2^km\ \!\alpha(m))，大样例过了，感觉有点悬，不管了写 T3。

想到了一个 O(q\ log^2n) 的写法，但是要 ACAM，不会写，只能去写暴力了，25pts 跑路了。

最后又给 T3T4 瞎搞了一下，感觉还行。

赛后

T3 大样例跑了 140s，错了，但是考场上看都没看就关了，于是 25->5。
T2 挂了 20pts，意料之中。
T4 12pts，意料之中。

最后 100+80+5+12=197 SH 好像是 rk140？
1=了，可以去 NOIP玩了，有蓝钩了 YaY！