CSP-S 2025 游记

· · 生活·游记

中午睡了 1.5h，非常舒适。

进考场发现座位在柱子正后面，这下更牛了，根本看不到压缩包密码，比别人晚了 3 分钟开题。/ng

T1 被吓到了，发现可以建费用流模型，进而发现贪心，10 min 通过了。

T2 发现有 O(m2^k\alpha(n)) 的暴力做法，然后观察了一个小时，最后发现，m 条原图边只有 MST 上的 n-1 条有用。

然后 O(nk2^k\alpha(n)) 似乎可以通过就不管了。

T3 发现空间高达 2\mathrm{GB}，大胆猜测有 O(L|\Sigma|) 的数组，trie 或者 ACAM。

尝试一波 ACAM，发现可以变成 L 次查询失配树上两个点的祖先中对应字符串长度 \ge 某个值的个数。

发现 $L$ 开到 $5\times 10^6$ 不符合 CCF 一贯数据范围，然后发现有自然根号 $O(L\sqrt L)$ 的做法。 最后神秘观察出需要中间不相同的一段完全相等，哈希一波变成两个前缀匹配。 建 trie，转化为两个子树内，dfn 转二位数点，扫描线，$O(L|\Sigma|+n\log L)$。 此时剩余大约 1.5h，直接开 T4，发现恐怖 $998244353$。 对于一个是否聘用的 $01$ 序列，记 $p_i$ 为 $i$ 之前的 $0$ 的数量，发现 $01$ 对应 $c\le p_i$ 和 $c>p_i$。 然后发现一个位置 $p_i$ 只会 $+1$，开桶之后状态为前 $i$ 个人，$p=j$，还要选 $k$ 个 $c>j$ 的数。 发现是典的延后钦定（见 CF1608F），直接写出来，挂样例 2。 样例 2 这么大调啥，手搓 ？ 个小样例最后成功通过样例 2。 然后直接通过所有大样例，非常痛快。 这时候我以为复杂度是 $O(n^4)$ 就没管，反正分是够的。（赛后发现桶和是 $n$，复杂度就是 $O(n^3)$） 还剩大半个小时，谨慎起见开了 3 次虚拟机取编译。 估分：$100+[64,100]+100+100$。