CSP-S2025 游记

l18608354717 · 2025-11-03 09:56:26 · 生活·游记

其实这是某人的小号。 在 cdqz 学了两个月再回 nszx 考 csp。

其实考前我们机房状态还是很好的，我甚至还向学弟推荐了个解压小游戏？叫做 truffle。周五打了一上午瓦，下午玩你画我猜，晚上玩音游，周六上午好像也是打瓦，还打了几个模板，中午睡醒了就进考场。

T1

简单贪心，但是最开始想错了浪费了点时间，后面实现的时候使用了错误的stl检查了半天，耗时30min，100pts。

T2

最开始就想到了 m\log m+2^k(kn\log n+m) 后面发现弄出mst后边数可以降到n，复杂度变成 m\log m+2^kkn\log n ，后面发现可以归并少一个log，但是没写，1h，80pts。

T3

最开始读错题以为可以替换多次认为不可做，后面才发现只能换一次

然后发现可以hash，因为真正替换的部分才重要，所以想到了枚举替换前后缀，时间复杂度 L+nq+q\log n，洛谷80pts，1.5h。

T4

没头绪，想了30min没有想到任何和当前选的人无关的做法，所以打了 n!。后面发现可以状压，设f_{i,j,st} 表示前i个位置，j个不录取，选了st的人，转移显然，复杂度 n^22^n，20pts。

总结

有24分应该拿但是没拿到，总体自我感觉不良好。