CSP-S 2025 游记 & 总结

开 T1。

第一眼：这不就贪心。。。

第二眼：这怎么贪心？？？

第三眼：好像 dp 也可以做（开始推 dp）。

40min 左右写了一个 $O(n^3)$ 的 dp，可以过 $n\le200$。

试图从 dp 的结果中找贪心的结论，但失败了。

试图优化 dp。发现难以优化。于是先放着。

开 T2。

0s 想到 $2^k$ 枚举乡镇然后暴力连边跑最小生成树。

没有想到把边数缩到 $n$。发现 $m$ 很大，所以选择用 Prim。

又花了一点时间写 Prim。发现大样例跑得很慢。

尝试用 pb_ds 的堆优化。诶怎么 Windows 下没有 pb_ds。

启动虚拟机。好吧 pb_ds 也没多快。

不会优化了。先放着。

开 T3。

怎么是字符串。我只会哈希和 Trie 啊。

0s 想到 $O(L\sqrt L)$ 的暴力哈希。开写。

过了两个小样例。大样例怎么挂了。是不是哈希冲突了。

试试双哈希。怎么还是挂。

是不是值域太小了。换成 unsigned long long。还是挂。

。。。

旁边的小朋友尝试 cos IOI 2024 国家队选手，将电话手表带进了考场（安检在哪？？？），这时候电话手表响了。小朋友拼命解释，然后开始哭。场面一度十分混乱，也确实对我造成了一定的影响。

最终调了快 1h 都没过大样例 3。大样例 4 倒是过了。这时候已经快 18:00 了，遂放弃。

回去看 T2。写了一个小小的常数优化，大样例跑快了 1 倍。

回去看 T1。写了特殊性质 AB 的贪心。加上 dp 估计能有 70 分。

尝试把 T1 特殊性质 B 的贪心拓展到正解。但是时间不多了，思绪比较混乱，最后没有成功。赛后回想起来其实已经很接近正解了。

最后几分钟决定摆烂。检查了一下 checker，看了一下 T4 的题面。

结束了。

估分 $70+[30,50]+[0,40]+0= [100,160]$。

More and more vegetable：

What should I do：

NOIP 加油。