CSP-S 2025 游记

· · 生活·游记

考前动员会改到了考后，说是为了避免 RP 攒到期中考了。结果 RP 是一点没攒到期中考。

考场在北京信息技术学院，据说这里的电脑比较好。突然想到去年北工大的机子了。试机，发现网络断的比较及时，去年有人考前直接上了洛谷。10^8 次乘法取模跑了 0.4 秒，还可以。

T1。读完觉得和 Coins 有点像，只不过 Coins 是 = X, Y, Z，这题是 \le n / 2。于是考虑让所有人都分给第 1 组，然后再调整。实际上转化完的贪心并不好做，因为是 \le。1 h 后只会 65 pts，写完跑路了。

T2。20 pts 是显然的，直接跑 MST 即可。那么加入额外点后怎么做呢？当时认为会额外多 kn^2 条边，导致想不到任何有用的做法，甚至连 O(2^k (m + nk) \log(m + nk)) 的暴力都没想到。赶紧写完了 20 pts。

T3。立马会了 O(nq)，直接开写。写完发现是 O(nmq) 的，加个哈希就好了。哈希直接写了个自然溢出，出题人别卡。最开始以为是 40 pts，但是有一个 q = 1 的性质，所以是 50 pts。

T4。读完题之后就不想思考了，跳过。

2 h 获得了 65 + 20 + 50 + 0 = 135 分。

回到 T1。我在 2 天前提出了 Coins 的假贪心，实在没办法了，写了一下发现过了所有样例。什么鬼？赶紧开拍，拍了 3 万多组没拍出来，那可能是对的吧。怕挂分，把两者合到了一起，写了个数据分治。最后还是挂了 10 pts。

T2 和 T3 都没想法，那就看看 T4。先把 8 pts 打了。发现有一个 n \le 18，尝试进行状压，发现不会。还有 m = 1 和 m = n，以为很简单，结果 c_i 可以为 0，立马不简单了。结果答案要么是 0，要么是 n!。

2.5 h 获得了 100 + 20 + 50 + 8 = 178 分。

后面 1 h 获得了 0 分。在最后 30 min 上了个厕所，突然会了 T2 的 A 性质。在最后 2 min 写完调完交上，目送倒计时结束。

奶奶滴，T1 挂 10 pts。