CSP-S 2025 游记

· · 生活·游记

先按照惯例看一遍所有题目，然后想大致思路写在草稿纸上。

以下是我草稿纸上的内容：

T1:贪心 or dp

T2:最小生成树（Kruskal）

T3:字典树？

T4:计数dp?

然后开始写代码。

T1

好像没什么好说的，5min写完贪心，一发过了。

//ps:真的能评绿吗，感觉严格小于J组T3。

T2

本来想了个直接在原图上连边的思路，然后发现要多连 n^2k 条边，时间复杂度假了。

观察数据范围可得 k 的范围非常小，于是想到暴力选乡镇，然后每次要选乡镇时直接再加个点，然后加 n 条边，总共只用加 nk 条边，感觉非常优。

写完后发现大样例跑得非常慢，注意到算法瓶颈为 Kruskal，因为每次跑Kruskal都是会有 m+nk 条边的，总时间复杂度为 O(2^k(m+nk)) (也就是XaoWa118的做法)，并不能通过，于是考虑如何优化。

注意到时间瓶颈在 m，又联想到Kruskal的选边逻辑，于是可以先在原图上跑一遍Kruskal，将要用的边加入边集，然后每次暴力dfs跑就行了，时间复杂度为 O(2^knk)。

又加入了一些剪枝，最优性剪枝(Kruskal中途如果答案大于已有的答案直接跳，在随机数据中可以跑得很快)，并查集的启发式合并。

最后大样例跑了0.1s。

造了 100 组极限数据，竟然都比大样例跑得快，怀疑大样例是构造过的。

T2总共花了大概60min。

T3:

不想多说，字典树和字符串哈希大概让我浪费了60min，结果只过了小样例&&大样例1，导致我本来应该会的T4并没有写出来，但我感觉我的做法是正确的？

于是果断换为暴力+特殊性质。

暴力为 O(n^2q)，若字符串是“特殊的”则是 O(nq) 的。

T4:

//我的意难平

一个比较典的计数dp。

这种题其实有比较常见的做法（大概?）。

首先根据数据范围设状态的维数，看到 n\leq500 于是知道是(二或三)维的。

然后根据题目中每个人如何根据前面的转移来设计状态。

注意到每个人被录用是具有单调性的（可能比较抽象？）。

也就是说如果一个人在前面面试就会直接离开，那他在后面面试也会直接离开。

所以说可以定义状态为 f_{i,j,k} 表示第 i 天面试完，面试完的人已经有 j 个未被录用，且当前的能用人数为 k 时，只选择没用的人的方案数。

但是正在推转移式子时发现时日无多，于是写个了 O(2^n) 的状压（但好像炸了？），于是写个O(n!) 的暴力 +(m=1,m=n,A)的特殊性质跑路了，ps:特殊性质好像炸了，没有管 c_i 等于 0 的情况。

总分大概为 200+ 希望能7勾吧，感觉自己已经唐完了。

已经初二了，估计还没有小朋友 @HasNoName 考得高，可能要 AFO 了吧。

最后，膜拜考场坐我右边大佬，70min AC前三道，10min最后一题写出状压，剩下时间睡觉+俄罗斯方块，最后30min猛然惊醒，开始写T4正解，听他说好像大样例都过了。