CSPS2025 游记

acb437 · 2025-11-10 21:33:20 · 生活·游记

CSPS2024 游记

Day 1 11/1

今年不参加 J 组了，所以上午睡到 0900，然后写了几个模板。

中午出门稍晚了一点，地铁又坐过了一个站，出站后狂奔才赶在 1410 前到了考场楼下。但教练说不用着急，我才发现其他人原来都在候考室，也是差不多这个时候才出发去考场，所以其实没必要跑的。

我的考场所在的 7 楼只有女厕所，6 楼只有男厕所，所以上厕所得下一层楼。

1427 解压压缩包，密码是 Ren5Jie4Di4Ling5%。T1 看了十几分钟才想出来，然后在 1500 左右测完大样例。看起来 T2 并不难。

基于 k 的规模，我认为复杂度中应该有 2^k，而由于 m 太大，我认为不是求 2^k 次最小生成树，因此在错误的道路上思考了大约 2h，其间简单阅读和思考了 T3 和 T4。

此时我发现，先做一次 kruskal 之后，有用的边就只剩下 n-1 条，完全可以参与到 2^k 次枚举中，并计算复杂度，认为它可以获得 80pts。我也随机了一组极限规模的输入，跑完需要 3s 左右。而时间已经不多，我认为正解或许不容易想出来，于是写完这些分数就开始写 T3 和 T4 的暴力。

字符串题做得不多，T3 完全没有头绪，花了十几分钟写了字符串哈希。然后将 T4 的阶乘和 m=n 写了，当时我以为阶乘能过 n=20，所以将分数估为 24pts。

最后半个小时，我尝试写 T3 的性质 B，然而最后 10 分钟时仍有相当一部分没写完，我判断无法完成，所以放弃了。最后过了一遍所有题，确认 freopen，头文件和数组空间没有问题，并测试了大样例。

结语

出考场时我还以为阶乘可以过 n=20，所以当时的估分是 100+80+25+24=229pts。不过 S 组已经是小事了，我也没有犯什么大错，所以也没有很难受。

略微遗憾的是 T2 的 m\rightarrow n 应该是比较显然的，而错误的做法一看就没有前途（或许可以用 LCT 完成这个做法），我却仍然浪费了 2h，这些时间或许可以为我换取 50\sim 80pts。

后来和同学交谈的时候我才想起阶乘是过不了 20 的，这一档是状压的分，所以估分变成了 100+80+25+12=217pts，最后出分果然如此，一分不多一分不少，本来还有点期待 T2 能多卡过一两个点的。

赞美万机之神/破碎之神/Omnissiah/Mekhane/WAN。

记于 2025/11/13。