2025 CSP 游记
So_noSlack
·
·
生活·游记
\text{Day -INF}
初赛 79/42.5。
初赛是在本校考的，甚至就是我们信息课的机房。
## $\text{Day 0.5}
中午 11 点才起，收拾一下，吃了个牛肉面就去考点了。
今年考点有点远啊，一个小时才到。在门口见到了教练，还有很多之前的同学。
进场前教练嘱咐说先去个厕所，洗把脸。
不过都不重要了，现在我也遇到了很优秀的教练，和很好的同学。
还有个小插曲，进场的时候见到了一个身高不足一米的小朋友，给我吓得，结果一想貌似他是来考 $\text{X}$ 组的，我都忘了 $\text{HA}$ 今年新添了 $\text{X}$ 组。不过话说怎么现在二三年级都开始学 $\text{OI}$ 了，$\text{HA}$ 的 $\text{OI}$ 正在蒸蒸日上！
考场在三楼，找到考场之后先去了趟厕所，洗了把脸，清醒多了。
坐到位置上，感觉还早，其实还是有点慌的，因为我当时已经有预感今天可能会卡在 $\text{A}$ 题，其实我也不知道为什么有这个预感，但确实当时我就是这么想的。为了让自己不那么紧张，我劝说自己不用追求多高的分，只要一等就行，$\text{NOIP}$ 才重要。于是趴桌子上休息了一会。
## $\text{Day 1}
$14:26$ 公布压缩包密码，快速建了子文件夹和题目文件，看题。
$14:41$ $\text{A}$ 题先想了贪心，感觉没有正确性，于是想了 $\text{dp}$，感觉一下子推不出来正解，就一直在推 $O(n^3)$ 的解法。
（后面时间点记不清了，等代码公示了补。）
但是推了很久才勉强推出来一个类 $O(n^3)$ 的解法，写了写，调对了。
感觉没底，又写了 $O(3^n)$ 的暴力解。
此时已经快一个半小时了，感觉有点慌，就去开 $\text{B}$ 了。
当时看 $\text{A}$ 没什么思路的时候看过 $\text{B}$，于是吸取 $\text{A}$ 的教训，先写了 $k=0$ 的特殊性质，直接 $\text{Kruskal}$ 即可（其实我赛时不会拼哈哈，写成 $\text{Kruscal}$ 了，不过不影响）。
接着发现特殊性质 $\text{A}$ 可以转化成边，不过直接暴力转的话大概有大于 $1e7$ 条边来着，所以考虑开一个数组 $f_{i,j}$ 表示 $i$ 连 $j$ 的最小边权，这样最多有 $1e6$ 条边。接着跑 $\text{Kruskal}$ 就行了，但这样只能过 $n=10^3$ 的点，不过也有 $40\text{pts}$ 了，不管了扔了。
接着准备把 $\text{CD}$ 的暴力先拿到，$\text{C}$ 写了个暴力，只能跑过 $1 \sim 2$ 的点，只有 $10\text{pts}$，不管了扔了。
开 $\text{D}$，全排列有 $8\text{pts}$，快速写完，但 $m=1/n$ 这两个部分分没想，$s_i=1$ 也没想，感觉这个不难想，但当时 $\text{A}$ 没做出来就有点急，先去看 $\text{A}$ 了。
事实上 $\text{A}$ 没有任何大的进展，只把特殊性质 $\text{AC}$ 写了，然后就不会了，直到现在我还觉得 $\text{A}$ 这个 $\text{dp}$ 一定能推出来。
接着浏览了一遍后三题，$\text{B}$ 貌似没有什么好写的部分分了，看了 $\text{C}$ 题，感觉 $3 \sim 5$ 的点可以暴力卡一下，然后就开始卡常。
没想到真卡过去了，不优化本地跑 $12s$，优化之后本地跑不到 $3s$，希望 $\text{CCF}$ 评测机能发点力，毕竟今年评测机还升级了。
剩下的时间就是在想 $\text{A}$，最后 $20$ 分钟，检查了一下各个题的部分分特判，把能写的都写了，每道题重新测了样例和大样例。
检查了一下 `freopen` 就交了。
## $\text{Day 2}
重现了考场代码，没挂分，不过我这分好像没什么能挂的了。
云斗：$70+64+60+12=206$。
核桃：$70+64+25+8=167$。
小图灵：$90+48+25+32=195$。
## 总结
这场虽然难度严格大于去年，但感觉还是策略失误比较多，加上这场 $\text{A}$ 题思路完全偏了，实际上我很多次想过是不是解法问题，但只考虑了状态设计不对，一直没想过这题就不是 $\text{dp}$，当时就应该多想想贪心的，不过这都是后话了。
其次 $\text{B}$ 题部分分没有把握准确，实际上 $k \le 5$ 的部分分完全可做，甚至 $n \le 10^3$ 都比较简单。$\text{CD}$ 也没有拿除暴力以外的部分分，感觉很亏。
打击是有的，但得到的经验就是，考虑清楚一道题所有的解法可能，觉得是 $\text{dp}$ 的题有可能能用贪心写，觉得是贪心的题有可能是 $\text{dp}$，这次判断失误主要是因为觉得朴素贪心的正确性无法保证，但实际上还是因为不够贪！
其次真的不能死磕一道题，我还算好的，实在不可做就跳了，至少把暴力分和简单的特殊性质打了，赛后发现有些人甚至磕了 $2.5$ 小时 $\text{A}$ 题，太逆天了。
最重要的是心态问题吧，被 $\text{A}$ 题扰乱了做题策略，之后也没有完全调整过来。
达成成就：机房唯一蓝钩也是唯一没切 $\text{A}$、参加 $\text{S}$ 组三年以来唯一一场没切任何一题 $\dots