CSP-S2025 游记

· · 生活·游记

文后附简要题解。

看完 t1 就胡了一个做法，写，过样例。

看完 t2 感觉要 O(n2^kk\log (nk))，好像过不去。要用一些麻烦的方法实现。最后 sort 还要换成桶排。感觉自己胡的做法【】。但是也能写，写，卡常，手搓本机极限数据 700ms，感觉不同数据效率差别不大就扔了。一看表发现竟然已经过了一个小时。

看完 t3 发现是串串题，由于串长不变，容易转化成 Trie 树二维数点，写之。写完了，调了一会过了大样例。发现大样例不满，赶紧造了点数据，感觉跑得有点慢。把 map 换成了 gp_hash_table。好像还是挺慢（我删了剪枝测的）。但是感觉卡不满，毕竟字符串题数据不好造。加了剪枝跑飞快。此时又过了五十分钟，而且机器逐渐变得卡顿，卡常最多失去三四十，开 t4 是一个更加稳妥的选择。

于是乎开 t4。先考虑 dp。发现同时有成功和失败的限制难以刻画。容斥之后，限制都是 \le 且值不断递增，这正好符合问题『共 n 个变量赋互不相同的值从 1 到 n，要求第 i 个变量 \le t_i』的考虑顺序，就做完了。

继续给 t3 卡常。最后也没卡过去。信仰一下，相信 ccf 的评测机速度，并相信我的做法卡不满。

t1：先贪心选择最大值，最后把超出的部分选择增量最小的那些换掉。显然不会同时有两个社团不满足条件，因此做法正确。时间复杂度 O(n\log n)。

t2：由于边集为 E 时若存在最优方案不选择边 e，则边集为 E 的超集时仍然存在最优方案不选择边 e。因此可以将 m 规约到 n-1。但是直接 2^k 搜索后新边有 O(nk) 条，不能全部取出做 Kruskal。因为此时图的结构特殊，直接对每个原来的点贪心选边权最小的连接，最后将图大小规约到 O(k) 量级时再跑 Kruskal，这样得到的新的可能边只有 O(n+k) 条。使用桶排替代 sort。最后再归并边集然后跑 Kruskal。时间复杂度视实现 O(n2^k(k+\alpha(n))) 至 O(n2^k(k+\log n)) 不等。

t3：特判串长不相等的情况。剩余情况找到第一个不对的位置和最后一个不对的位置，相当于中间匹配，两边分别是前缀的限制。可以建出 Trie 树，用树状数组计算二维数点问题。时间复杂度 O((L_1+L_2)|\Sigma|+(n+q)\log (L_1+L_2))。

t4：考虑容斥。注意到从前向后加人时放弃的限制在不断削弱。于是令 f_{i,j,k} 表示选了前 i 个人，有 j 人失败，钦定 k 人 \le c_i。转移容易 O(1)。实现时需要将第一维滚掉。时间复杂度 O(n^3)。