「 游记 」CSP-S 2022

CSP-S 2022 比赛时间 \(2022.10.29 - 14:30 \sim 18:30\)

赛时

\(14:30 \sim 14:40\)
把题目看完了，觉得 \(T1, T2\) 有点思路，\(T3\) 只会暴力，\(T4\) 对题意有点懵。

\(14:40 \sim 15:00\)
把 \(T1\) 打完，过了大样例。

\(15:00 \sim 15:05\)
害怕 \(T1\) 大样例太水了，又检查了几分钟代码，确保无误后再去做后面的题。

\(15:05 \sim 15:25\)
把 \(T2\) 打完，过了大样例。

\(15:25 \sim 15:50\)
一直在想 \(T3\)，发现特殊性质可做，大约有 \(60\) 分可得，不过我觉得还有时间，就先去看 \(T4\) 了。

\(15:50 \sim 17:35\)
耐心地看完题目后，发现 \(k \leq 3\)，直接把树剖中的线段树用来维护 \(\texttt{dp}\) 就行了。

刚开始觉得跳的点只会在两点之间的链上，打完后发现第 \(2\) 个大样例过不了，看它比较小就手算了一下，发现 \(k = 3\) 时是有可能往链外跳的，不过最多跳一步，所以预处理下往外跳的最小值，把线段树上的初值改一下就行了。

由于以为某些情况下 \(\texttt{LCA}\) 处会算 \(2\) 次，调了半个小时左右，改着改着觉得不对，就回到以为没有去重时的代码，发现它过了所有的大样例，于是想了大约 \(15\) 分钟为什么没有算重才理解。

时间复杂度大约是 \(\mathcal O (3^4 n \log^2 n)\) 的，优化到 \(\mathcal O (3^3 n \log^2 n)\)，也想不出其它做法了，想着 \(\texttt{CCF}\) 的评测机比较快就没管了。

\(17:35 \sim 18:10\)
想 \(T3\)，但一直想不出来，于是只打了那 \(60\) 分，刚开始认为特殊性质的代码可能过不了暴力的测试点 \(\mathcal O (10^8)\)，但觉得跑不满并且 \(\texttt{CCF}\) 的评测机比较快，就没有加小暴力。

\(18:10 \sim 18:30\)
一边想 \(T3\) 一边检查，直到结束。

赛后

T3 星战

后来看洛谷讨论区里有人说 \(\mathcal O (q \log n)\) 的做法 \(\texttt{(hash + set)}\)，自己想了想觉得不需要 \(\texttt{set}\)，只用 \(\texttt{hash}\) 就可以做到 \(\mathcal O (n + q)\)。\((\) 其实本质不应该叫 \(\texttt{hash}\)，应该叫随机化 \()\)

\(\texttt{2022-10-31}\) 打了一下自己的想法，发现可以过，可惜考试的时候没想到 啊啊啊 \(\sim\)

后来也看到讨论区里有和我差不多的做法。

自我评价

觉得过了大样例加上检查了几遍，而后面也一直再想 \(T3\)，所以没有打对拍。\((\) 可能这样不太好 \()\)

预估 \(100 + 100 + 60 + 100 = 360\)