CSPS2025退役祭

pig1121 · 2025-11-02 12:13:16 · 生活·游记

Day -114514

教练和我们说 300pts 就能去 WC。

Day -3413

SCP，虽然没按时打，但 5min 胡出 A/C，又用 30min 胡了个 B。

看起来前途一片光明。

Day -1

诶我数学怎么什么也不会，exgcd 都半年没写了。

诶我字符串怎么什么也不会，先去看一下 ac自动机？？（懂得都懂）。

Day 1

-5min

怎么又是 GDFZ 特色排排坐+防窥膜，不过这次贴的还算紧，但为什么只有中间，为了方便看到邻座在写什么题？

我怎么一直在咳嗽？

1min

监考员：密码还在路上。

2min

监考员写密码漏了一个 4。

5min

写缺省源，建文件。诶我快读怎么读不进东西。然后写了个拍子的模板，命名成了 cheker.cpp。

10min

发现 A 是智障贪心，直接每个都选最优，然后对超员的组按最优减次优排序撤去次优即可。

不是我怎么少套了一层 id？不是我怎么次大值维护错了？

20min

通过 A 的全部大样例。

用自己写的 cheker.exe 拍了几组。

25min

B。

这个 n\leq 10^4,m\leq 10^6,k\leq 10 有点不太对劲，貌似允许 O(nk2^k) 类似物。

考虑状压 k，枚举选了哪几个村进行城市化。直接做是 O(2^k\times (m+nk)\log(m+nk))。

30min

注意到原图是固定的，则原图中有用的只有原图 MST 上的边，先求出原图 MST 在删去其他边就能做到 O(m\log m+2^k\times nk\log nk)。

35min

发现枚举时每次会加入多组固定的 n 条边，那么先对 k+1 组（算上原图）分别排序再归并貌似可以做到 O(m\log m+nk\log nk+2^k\times nk\times\alpha(nk))，而且跑不满，应该能过。

80min

写完才发现可以直接全排一遍序然后忽略不在当前枚举集合中的边，貌似更好写。但懒得改了。

大样例 55ms。

到现在前途依然一片光明……

85min

C。

ML 给了 2048MB，长度 5\times 10^6，多串，考虑 Trie 相关算法。

100min

注意到一个必要条件是去除 LCP、LCS 后能匹配。

头好疼。

120min

考虑 B 性质，可以将中间不同的部分相同的串放到一组匹配。

150min

用哈希比较串来分组，然后上 AC 自动机。

因为已经保证中间能匹配了，两边一定是一样的，直接查有多少模式串出现即可。

对 s_0,s_1 同时用一个状态表示，转移边就设成 s_{0,i}\times|\Sigma|+s_{1,i}，字符集大小 676，感觉直接复制 fail_i 的转移会和暴力同分。主席树常数巨大，感觉也过不了。主要还是码不动了？

180min

考虑上持久化分块维护转移边，常数较小，复杂度 O(L\times|\Sigma|)。

然后这个时候脑子发力了，写一半 AC 自动机然后卡住了。

然后我不知道为什么认为 1\log 过不去 5\times 10^6，而 |\Sigma|=26>\log_2(5\times10^6)。

然后我弃题了。

为什么不先把特殊性质和 O(q\times len) 写了？

220min

D 拿了 8pts 跑路，然后监考员下来检查文件，结果下发的文件检察器也叫 cheker.exe，而 Dev-C++ 编译时没有替换文件提示……

然后突然发现自己 C 还什么都没写，匆忙补了个 B 性质，挂了。

238min

没时间了，最后看了一眼 T1、T2。

发现自己 T2 并查集没有写启发式合并，多一个 \log……

发现自己归并写成了 O(nk^2)……