CSP-2025 寄

· · 生活·游记

（以下结合了考场思路和结束后的思路）

CSP-S 2025 寄

先花 10 分钟看完所有题并敲出源码

T1

重读了 2 分钟的题，

（没学过反悔贪心😂原来贪心还能反悔 [捂脸]！）看到有限制就直接往 dp 的方向想。

设 dp_{i, j, k} 表示前 i 个新成员，第一组分了 j 人，第二组分了 k 人，第三组分了 l - i - j 人，

于是 dp_{i, j, k} = \max(dp_{i - 1, j - 1, k} + a_{i, 1}, dp_{i - 1, j, k - 1} + a_{i, 2}, dp_{i - 1, j, k} + a_{i, 3})。

对三个组的人数判断一下就可以了。

方程写了 5 分钟，写下写了 20 分钟，调试调了一下边界情况 20 分钟，测能过的样例 5 分钟到 10 分钟。

然后考虑干掉 i 这一维，于是 j 和 k 要倒着枚举，像 01 背包一样。

然后还做了特殊性质 A（又写了 2 分钟），期望得分 60 pts。（实际 60）

T2

一看就先把 n, m 的初始图跑一遍最小生成树，留下 n - 1 条边，剩下的舍去。记录添加的 n - 1 条边中，边权最大的边权为 maxdis。

然后，用 2^k 的复杂度枚举是否要振兴这个乡镇，对于每个乡镇添加 n 条边，然后再跑 kruskal 就行了，时间复杂度 O(2^k k n \log n \alpha(n))。难过。

于是，我们预处理这 kn 条边，与原来的 n - 1 条边一起排序，然后每次标记是否能选即可，O(nk \log (nk) + 2^k kn \alpha(n))。

还是有点容易被卡，于是我们将加的 kn 条边中，边权大于 maxdis 的舍去，加上原来的 n - 1 条共剩下 cnt 条边。

于是就是 O(cnt \log cnt + 2^k cnt\ \alpha(n))，小了很多。可以过去。

不过我打的 kn^2 点权还加重，分数玄学，敲出 kruskal 10 分钟，优化等等倒写了一个半小时多。

样例太水了，我的点权加重了就只有最后一个没过去，当时没发现，预计个玄学。（我考场上打的 kn^2 点权还加重，居然还有 64， CCF 小数据水）

然后花了 10 分钟去 linux 下编译，提交。

T3 T4

T3 字符串我本来也不熟，手里仅会的算法也解决不了这种从中间搞开，替换，又判断相不相等。用 5 分钟打了个 10 pts。（实际 25 布吉岛怎么多出来的）

T4 看到限制那么多，还是计数题，特殊性质写了一下但是样例都过不去，只能交一个瞎写的代码（写的 n! 白嫖 4 分）。