CSP-S 2025 游记 & 总结

_Spectator_ · 2025-11-03 11:03:17 · 生活·游记

开 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：

• T1 没有利用好“最多只有一个社团满员”这一个显然的性质。其实注意到这一点很容易想到正解。
• T2 没有想到先跑一遍最小生成树把边数缩小到 n。又因为边数较多而选择了 Prim 而不是 Kruskal。相当于堵死了优化的方向。
• T3 没有认真读题，导致没有判断 |t_1| \neq |t_2|，可能会挂成 0 分。并且调哈希浪费了大量时间，导致没有足够的时间想其他题。
• T4 最后才看，暴力都没时间打。

What should I do：

• 加强贪心、字符串、计数等薄弱板块的训练，加强思维。
• 考场上合理分配时间，认真读题。
• 学会调整心态，尽量减少他人对自己的影响。

NOIP 加油。