CSP 2025 游记

· · 生活·游记

Day -？

NOIP 模拟赛是什么，我们只打过 NOI 模拟赛。次次模拟赛垫底好慌啊。

Day -5 ~ -2

在机房做真题、做真题、做真题、打模板……我好菜啊怎么连绿题也不会做。

Day -1

提早放学了，回来打模板。写了 KMP、O(n) 求逆元、最短路全家桶、Tarjan 模板，希望能用上。睡觉，希望能七级钩。

CSP J

热身赛。键盘手感特别好。

8：30 开赛，看题。T1 是一眼贪心，T2 是一眼模拟，怎么这么简单？

8：41 通过 T1。

8：50 通过 T2。

这个 T3 看起来怎么这么难？先想到前缀和 f(l,r) = f(1,l-1)\oplus f(1,r)，转化为 s_{l-1}\oplus s_r=k，那么对于一个 s_r，符合条件的 s_{l-1} 必定就是 s_r\oplus k。贪心地遍历 r，每次尽可能取右边的 l，然后 DP 就做完了。

9：24 通过 T3。

T4 怎么是道计数？完了还没在正赛做出来过计数。感谢善良的出题人给了我多边形判定条件。先排序，固定最大值 a_i，那么问题就转化为在 [1,i) 中有多少个子集，满足子集和 >a_i。正着做是困难的，那么用背包反着做，就转移到 a_i 这个背包容量，DP 含义换成方案数就做完了。大样例一个接一个的通过，难道我要 AK 了？

9：46 通过 T4。

我就这么水灵灵地 AK 了？？？？

AK ？？？

AK 是个什么东西？

第一次 AK 比赛竟然是在 CSP-J 正赛，哈哈哈。

CSP S

有了上午 CSP-J AK 的信心，好像没那么紧张了。希望三点前能通过 T1。

14：30 开赛，看题。好像都不好做，今年怎么没有橙色的 T1 了？

看着 T1 感觉好慌啊，模拟赛的 T1 我很少 AC。怎么办？在草稿纸上灵感大发，把 6 10 8 转化成了 -4 10 -2，然后就想到反悔贪心了。然后还得注意调剂到的那个部门也不能超过 n/2 个人，一个人也不能被调剂两次。调了一会才发现这个问题。

15：00 通过 T1。

T2 肯定是个最小生成树。一开始试着对于每一个乡村，都 O(n^2) 的进行连边，但是一直没发现是错的，因为样例 1, 2 都过了，3 和 4 跑不出来。然后后面没思路了，开始做 T3。

T3 好神秘啊，不知道在表达什么。KMP 码上去，样例 1 和 2 过了，3 跑了整整 60 秒，后面就一点思路都没有了（AC 自动机听说过但是完全不会），希望 CCF 的少爷机能救我。

T4 更神奇了（原来本来是一道 NOI D2T1）怎么做啊不会不会。写了 n=10 和 m=n，其他的写了不可以总司令（printf("0\n")），最逆天的 OJ 这题测下来 28 分。

这时候回过来想 T2，发现可以枚举我打开哪些乡镇，然后 O(nk) 连边之后跑最小生成树，这里我犹豫了很久，Kruskal 看起来效率不高，所以最后选择了 Prim，出来听同学说是 O(n^2) 的，但其实堆优化的是 O(m \log n) 的，应该不会似。又过了一会，快五点半了，想起来对拍一下，然后发现一开始那个方法是错的，有些 c_i 会被重复算多次，我真是个傻逼。换了写法，样例 3 跑了 6s，样例 4 跑了 1.2s，希望 CCF 的少爷机能救我。

18：10 重启进 Linux 编译，开了各种 Warning，把各种 shadow、conversion 都改掉了。然后查了一下数组有没有开小，准备交卷。

18：30 交卷。心里很慌，对 T2 和 T3 的得分完全没有底，希望不要挂没。

Day +2

J：100+100+100+100=400。

S：100+[72,80]+[30,60]+[12,28]=[214,268]，希望能七级。

NOIP 再战！