CSP-S 又寄

· · 生活·游记

最后一场 CSP-S，寄。

前言

作为 OI 生涯的最后一场 CSP-S，其实压力也不算大，反正不保龄就行。之前也曾 AK 过，所以算不上留下遗憾。（再次证明自己越学越菜了啊）

打了很多模拟赛，具体可以看训练小记。

比赛日

在积建楼门口集合，然后看到了“持之以恒”。怎么看怎么不对劲。

发了解压密码，但并没有急着看题，不慌不忙的把手里的 IO 敲完，然后检查了两遍。感觉就是打 CSP 的话如果心态先慌了才是真的完蛋了。
看了下 T1，发现是签到题，过大样例的时候大概 30\min。（还在适应跷跷板键盘ing）
去看 T2，第一眼看完居然没有秒掉，看上去很奇怪啊。往下翻数据范围，哦原来 k\le10 啊，那没事了。感觉只会暴力每次求生成树的做法，可以把排序的 \log 预处理掉，但不太会剩余的优化了。此时的复杂度为 O(nk2^k\alpha)，想了下发现那个 \alpha 不应该与边数乘起来，因为边数远大于点数，且带一个很小常数。外加对 CCF 少爷机的信任，决定就写这个做法。耗时约 40\min，写完之后发现会爆掉，把 N = 1e5 + 10 改成了 N = 1e5 + 20，避免了悲剧的发生。

上面算是开胃小菜，接下来才算正式开始比赛。
看 T3，发现是不太擅长的字符串题，思考一小会儿无果。看 T4，发现是神秘 DP 计数题，依然没啥直接的思路。开始奇怪：以前的 CSP 感觉至少有 300 分都是白送，感觉今年的题目有点小难。
冷静一下，吃点东西先。这次考试带了很多吃的，爽！

发现 T3 的关键是去匹配 LCP 与 LCS。换句话说，对于 s,t 都可以找出中间有差异的极长区间，那么这个极长区间的内容必须完全一致。这样分类之后，对于同组的 s,t 是一个类二维数点问题。脑抽了一下，居然没有迅速反应过来可以在 trie 树上类扫描线，一直在想对每个 t 扫描线的话复杂度可能达到 O(n)。当然唐了 10\min 过后还是反应过来了，赶紧写完了这道题，并且因为写的时候比较仔细（指的是判掉了 s_1=s_2 和 |t_1|\ne|t_2|），直接一遍过了样例。耗时约 1\rm h。

这个时候想着 2\rm h 足够做出 T4 了，于是开始在草稿纸上大战起来，胡了一个容斥做法，写上去发现过不了大样例，仔细一看怎么是 O(n^2) 的。找出问题之后发现不会修，但是感觉就差一点点，不想去上厕所，导致越来越上头。决定帮自己换换脑子，打开 linux 虚拟机，测试了一下前三道的代码，又目测了几遍，造数据测了一点 corner，确定无误之后继续做 T4。但是就当时的状态，也不太能硬钢出来，遂投身暴力，发现每一档特殊性质都不太会，只打了一个 24\texttt{pts} 的暴力分跑路。

终究是大败而归了。

后记

听说 T2 很多人忘了把上限开到 N+K，T3 很多人忘了判 |t_1|\ne|t_2|。什么 FST 大战啊，不过 CCF 不开子任务捆绑。
听说 T4 是原？不太会，糖丸了。

Acoipp：感觉打完 CSP 之后，整个人都养胃了。