CSP-S2025 游记

风物长宜放眼量，心胸要开阔。

Day -2 (10.29)

Day 1 (11.1)

• $14:30\sim 14:40$：读了 T1 的题面，然后想了一小会，会了。
• $14:40\sim 14:50$：读了 T2 的题面，然而想错题意了，以为自己会了。
• $14:50\sim 15:00$：写 T1，接着写出来了。
• $15:00\sim 15:40$：写了一点，发现自己假完了。重新开始做 T2，然后发现乡村的边，只用到最小点和其余点所构成的边，但是又想错了，以为乡村每次都有 $c_i$ 的代价。然后，才发现需要 $2^k$ 枚举激活哪些乡村，感觉前面浪费了很多时间。
  后面其实还挺顺的，首先暴力是 $O(2^k m\log m)$ 的。这里想了一会，发现只有最小生成树的边有用，会了 $O(2^k k n\log n)$，但是这个包过不了的。想了想优化，发现我可以把最小生成树整个全记下来，这样就不带 $k$ 了，同时还可以归并排序做到不带 $\log$。
• $15:40\sim 16:00$：写 T2（其实前面写过了，只是都是假的），调了一会过了。
• $16:00\sim 16:15$：看 T3，想到每个对的格式为 $\text{LCP} + (X \to Y)+\text{LCS}$ 的形式，中间 $(X,Y)$ $s,t$ 必须相等，$\text{LCP}$ 和 $\text{LCS}$ 发现需要满足前后缀，然后是经典二维数点，秒了。
• $16:15\sim 17:30$：写 T3，发现虽然思路简单，但是巨难处理。需要先把 $\text{LCP} + (X \to Y)+\text{LCS}$ 格式处理出来，然后还要找出前后缀区间，由于长度有足足 $5\times 10^6$，没敢上 Trie，写的二分。总之，写了好久，不过最后没调就过大样例了，爽（虽然，中间停下来运行了一次，那次 好像写错了一点点）。
• $17:30\sim 18:00$：想 T4，时间太紧张了，一开始胡了个假做法。然后，想了好久啥也不会，最后，终于想到可以延迟计算贡献，会了 $O(n^4)$ 做法。
• $18:00\sim 18:15$：写 $O(n^4)$ 做法，写完了但是发现好像调不出来了。于是，果断放弃，写了更好写的 $O(2^n n^2)$ 做法。
• $18:15\sim 18:25$：极限写出来了。

Day 2 (11. 2)