CSP-S 2025 游寄

· · 生活·游记

省流：主播很菜，现役高一，寄了，第一次 CSP，可能也是最后一次 CSP（如果 NOIP 也坠机的话）

去杭师大的路上点了杯神秘奶茶，然后在大巴上奶茶和肚子发生了化学反应，再加上晕车，下车之后差点吐了出来，有点影响状态。

看到赛场上有熟悉的 vscode，非常开心。但是鼠标非常难用，非常难受。

文件建好，开题。T1 第一眼看上去像个 dp，设 f_{i,j,k} 是考虑前 i 个人，j 个去第一个部门，k 个去第二个部门，剩下的人去第三个部门的满意度最大值，先拿了 55pts。然后感觉这个 dp 没什么前途，就去看了特殊性质 B，发现可以反悔贪心，打完之后好像发现三个部门和两个部门本质下都是一样的，也可以反悔贪心，1h 打完。

T2 一上来把题面读错了，以为是在给出的 n 个点里选 k 个，然后想了半天，以为是什么树形 dp 之类的东西，然而并没有什么思路，浪费了 0.5h 就跑了。

T3 是多字符串匹配，感觉可以 AC 自动机，但是我已经不会打了，于是就秉着“把暴力打满就有省一”的精神，糊了个 hash 上去，结果因为写法过于神秘调了 1h，然后去开了 T4。

T4 看到一个 n = 18 的点，觉得可以使用状压 dp 枚举每个人来的时间，等到打完了，测了下样例，发现不对，然后发现这个 dp 有后效性，直接假光了，只能小的点 n! 枚举，大的点输出 n! 骗分，结果民间数据居然有 16 pts 也是超预期了。

只剩 1h 了！

再去看那个 T2 ，手模了一下样例，终于发现自己把题面读错了，场上直接急了，脑子非常混乱，独立自主研发了一个神秘贪心，就是把最小生成树建出来之后从大到小枚举树上的边用两条新边（也可能是一条）和一个乡村代替，时间复杂度 O(m \log m + nk)，急急忙忙打出来，大样例调爆了，一个样例偏大一个样例偏小，但是只剩 0.5h 了，我只能寄希望于我的贪心，没有想别的什么思路，到结束也没有调出来。

出场时才发现好像机房同学除了我都把 T2 切了，脑子一片空白。

到大巴上才发现 k 很小，可以 2^k 枚举，就有了一个 80pts 做法，但是一切都晚了。

预估 100 + 16 + 25 + 8 = 149。

感觉这次整体速度有点偏慢了，可能是第一次 CSP，和平时模拟赛节奏还是不大一样。

这次 CSP 虽然没有圆我的勾七梦，但是我也要庆幸这不是 NOIP，我还有一次机会。感觉通过这次 CSP，我也学到了很多，比如读题时一定要看样例解释，不要读错，还有不要在暴力上浪费太多时间，正解也有可能比较暴力，考试快结束时不要急躁，想清楚了再下笔，等等。其实说到底还是实力太菜了。

只能寄希望于 NOIP 了，希望不要再爆一次，不然就直接什么奖都没有就 AFO 了。

upd：出线了，CCF 恩赐了 25 分，100 + 32 + 30 + 5 = 174 冲过省一线了（但是还是无勾七）