CSP-S 2025游记

· · 生活·游记

Day -8

发现考试地点在图书馆，但是忘记座位是哪个了。

Day -1

决定复习各种各样的模板。

于是写了快速幂，三分，单调队列，最小生成树，树状数组，线段树，LCA 等模板。尝试写 2021 年的“括号序列”但是写爆了，感觉自己菜完了。

去图书馆试了下机，学习了一下感觉 VSCode 很好用，我会吃一辈子 VSCode 的。环境还是很不错的，键盘有点不习惯但是不算难用。

Day 1

随意翻了下四个题目，发现没有一个一眼是会的（T3 和 T4 题面过于神秘了），决定先看 T1。

看 T1 觉得像是反悔贪，想了一万种方法，无果后思考特殊性质未果。经过发散思维后发现溢出的部门最多有一个。然后强制移动一下做完了，过了大样例就扔了。因为忘记 vscode 的命令行怎么写导致我 T1 做了一个小时。

看 T2，想了半天觉得 k=10 这个东西是什么——一开始的时候还以为是 k 作为一个维度，想不出来，后来往 2^k 去想。因为突然发现选了某个乡镇就一定会选他的边，不选一定不优，然后他就变成一个最小生成树的问题了。

但是这个边数很多还是很倒闭啊，花了一点时间证了非树边一定不会被选中，想了个 O(M \log M +2^k Nk \log Nk） 的做法，发现数据范围最大的时候还是会倒闭。想到找大小小 1 的子集然后把非树边和乡镇边拼起来就做完了，于是写了个 O(M \log M +2^k N\log N） 的东西，过了大样例就扔掉了。

剩下两个小时。

先看了 T3，怎么是神秘串串题，看 T4，怎么是神秘计数题。觉得计数比串串好做，先看了 T4。推了个 s_i=1（假了，后面发现了，根本不是阶乘），m=n 和暴搜，然后看 T3 发现 AC 自动机就可以做但是不会写（事实上根本用不到这个，字典树就行了，但是我串串过菜了）然后 T4 会了状压，于是先去把 T4 的 24 分写了，过了小样例就扔了。回去冲 T3 的 KMP 到结束没写出来。

出了考场发现，怎么都会 T3，T4？

预估 100+[80,100]+0+[20,24]=[200,224]（T4 m=n 没有样例）T2 输入输出优化没加，寄希望于 CCF 机子跑得够快吧。

Day 6

T2 挂到 80 了，T4 也挂到 12 分了，怎么变成 100+80+0+12=192 了。

为什么 T3 要一直想一个我没写过的 AC 自动机？T4 大概率是 n=m 假了然后 CCF 往里面加了若干个点。

恐怕再这样下去 NOIP 就二等了。