CSP-S 2025 游记

10.30

生病了，为啥每次 CSP 都会生病......

10.31

上午睡大觉。

下午出发，很早就到了酒店，然后继续睡大觉。

11.1

上午睡大觉，顺便写了几个板子。

感冒还没好。

下午开考。

T1 显然是个奶龙题，但是我脑袋爆炸，被这个题控了 15 分钟，发现按最优的选至多只有一个超过，切无论如何调整总是合法的，然后就做完了。

T2 是个很典的题，先 $2^k$ 枚举选哪些乡镇（可能是叫这个名字吧），然后把边拿出来跑最小生成树是 $O(2^k (m+nk) \log (m+nk))$ 的，但显然只有最小生成树上的边有用，于是去掉其他边，变为 $O(2^k nk \log nk + m \log m)$，发现边可以先提前排序，再顺次拿出来（这是很多分块题的套路），然后就做完了，$O(2^k nk + m \log m)$。

T3 看到是字符串，心态直接要炸了。仔细想想发现可以分为三段，我对 $s$ 的前两段存下来，然后分出 $t$ 的三段，枚举 $t$ 的中间段的前面一段，然后在对应的 $s$ 中枚举，check 一下第三段是否存在。然后复杂度是 $O(len \log n + nq)$ 的，但是把大样例艹过去了。

T4 写了前 $20$ 的状压，后面全输出 $n!$ 跑路了。

预计得分 100+100+?+20=220+?，倒大闭了。

后记

? 疑似等于 $70$。