CSP-S 2025 游记

· · 生活·游记

暴力出奇迹。

分数是 100+76+20+8=214，虽然对自己而言已经挺不错了，但是还是有不足之处可以改进的。

T1：道路修复

刚开始看到题没什么思路，意识到第一题没有过去两年那么简单了。

考虑到是第一题，就往贪心上面去想，先让每个人选最大的，多了的就给第二大的，如果第二大的也超过限制了，就给第三大的，便开始写代码。

写着写着突然发现把第一次把最大的踢走后，不可能产生第二次冲突，于是按踢走所减少满意度的从小往大一次排序即可。

写完代码加上测完大样例大约花了 30 min。

T2：道路修复

看到是图论，有点慌，但还好刚复习了 Kruskal。

马上想到了 O(2^k \cdot log(m+nk) \cdot(m+nk)) 的暴力，以及特殊性质 A 的做法（把所有都加进去即可）。

敲完并调试好将近花了有一个小时，代码能力有待提高。

结果发现大样例跑了有 2 秒，有想不出有什么很好的办法优化，便“聪明”地想出了把 2^k 变成 k^2 的错误贪心，却发现大样例跑出来都是对的，就误以为自己想出正解了。

又发现自己可能跑不完，于是加入了快超时就输出当前答案的人类智慧。

到这里又花费了有三四十分钟，速度还是太慢了。

这一通操作就导致 T2 我的得分是在 [48,100] 中的随机数，多亏了 CCF 的数据水，让我骗到了 76 分。

我这个做法从头到尾都是假的，以后再进行优化的时候一定要先保证正确性，即使想要骗分也一定要保留部分分的做法。不然如果出题人想要卡掉你就欲哭无泪了。

T3：谐音替换

字符串算法只学过哈希和字典树，但在本题上都只能用来打 O(nq^2) 的暴力，加上特殊性质 B 可以做到 O(nq)，预期得分 [15,30]，实际上因为严格跑不满，得到了 30 分。

但因为哈希犯的一个弱智错误，写了一个多小时。

本以为字符串算法从来都不会考，没想到今年还真出了。

备考时一定要关注考纲内的知识点，针对性复习。

赛后才知道不一定有 |t1|=|t2|，但我的做法不受影响。

T4：员工招聘

到这里已经没时间了，看特殊性质以为答案是 n!，就先去写，打完发现与大样例不一样，以为是代码写错了，结果发现 c_i 还可以为 0，要做特殊性质的话必须得写 DP。

到这里时间只剩半个小时了，火速写完 O(n!) 的暴力，得到 8 分。

总结：

  1. 代码能力有待提高：有思路时写代码、调代码花了太多时间，导致 T3、T4 只写了暴力。

  2. 思维能力十分欠缺：每题得到的都是送的/暴力的分，就连第二题的简单性质都没有看出来。

  3. 细心程度尚有不足：T3 的 |t1|\ne|t2| 没看到，虽然这次不影响，但谁知道以后类似的情况还会不会有呢。

马上就 NOIP 了，平时训练的时候还是要多积累，多思考。