2025 CSP-S 游记&赛后总结&反思
YGBC_
·
·
生活·游记
2025.11.1
14:30 开考
通读题面，并未想到任何思路，有点着急。努力思考 T1，并得到正解。
15:05
做完 T1。调完之后开 T2，对于前 16\% 的数据和特殊性质 A 显然可以直接 \text{Kruskal} 求得，花半个小时左右调完 48 分代码。之后思考正解，发现贪心，动态规划都不可做，只口胡出了 2^k 暴力 \text{Kruskal} 的办法，认为没有前途，于是决定看 T3。
15:50 左右
发现 T3 特殊性质，暴力分不少，决定冲击 T3。先想了哈希，写挂。再花了很长时间思考其他的想法，均以失败告终。而在重构代码，思考中浪费了很多时间。
17:30 左右
T3 最终打了 10 分暴力和哈希骗分跑路。没时间看 T4 了，回去补 T2 的暴力，最终因若干原因打了若干补丁，最终复杂度约 O(2^k(m\log m))，期望得分 56。
Last 30 min
对代码进行最后的检查，完善（生无可恋），期望得分 100+56+[10,?]+0。
2025.11.2
补 T2，发现每次 \text{Kruskal} 可以不重新排序，可以通过若干 Trick 和优化达到 O(m\log m+nk\log (nk)+2^k(nk\alpha (nk))) 求得（好猎奇的复杂度，之前根本不会想到），足以通过本题。
UPD on 2025.11.7
## 本次比赛暴露出的问题
1. 对 T2 的思考体现出自己对算法不熟练，如果深知 $\text{Kruskal}$ 瓶颈在于排序，对排序的过程略加优化，就不会只有 56 分。
2. 考试中时间分配的失误。对于 T3 不熟悉的字符串，不应该去花过多的时间去做无用功的尝试，应该着重观察特殊性质，或是分配给 T2 或 T4 的暴力。
3. 经验不足，考场上对草稿纸的使用率极低，加上没买水降温，以及重复输密码降低了效率，使状态大打折扣。
## 之后该如何备考 NOIP？
1. 对自己熟悉算法的题目，尽量多加思考，尝试 $70$ 分 ~ 正解，并学习一些优化技巧。对自己不熟悉的题目类型，着重练习部分分和特殊性质，并从中积累，学习。
2. 在模拟赛中不断优化做题顺序，时间分配，达到在 4.5 小时内拿到尽可能多分数的意义。
3. 积累本次考试的经验，并汲取教训，下次做更充足的准备。