CSP 2022 游记

T1 看错了题意，以为是最短路模板，写完发现看错题意已经浪费了 40 分钟；

然后重新想了个做法，写一半卡壳了，此时已经过去 $1h$。心态有点小崩，满脑子都是一题没过爆蛋的场景。决定先看 T2。

T2 一眼就感觉是毒瘤数据结构，暴力打满 $80$ 跑人。

回头看 T1 这不傻逼题，马上写完过大样例。这时过去了 $2h$ 多。心态稍微好点了。接下来准备求稳，T3 T4 尽量写暴力。

花了一段时间整理 T3 的题意。准备先把 $40pts$ 的 $\tt{Tarjan}$ 加拓扑写了。这玩意比我想象的长，约莫一百行，写完挺顺利地过了大样例，此时还剩 $1h$。

T4 先写了 $k=1$ 的倍增 $\tt{LCA}$。调完又过了 $0.5h$。写完冷静下来发现可以直接把链拎出来 $\tt{dp}$，$O(n^2)$ 可以拿好多分。赶紧写了一波，发现大样例 2 过不去，这时还是 $10min$，手模了一下发现可以跳到链外面去，md 假了。直接自闭。

---

出考场听 cqh, zyy 都过了 T2，一想秒了。焯。

T3 的条件相当于出度都为 $1$，这么显然的结论居然他妈没想出来，我是什么品种的智障。

T4 听巨佬们说可以直接倍增，把转移写成矩阵的形式，处理一下 $k=3$ 的情况，就可以过了。。。

不过还好考场上没删 $\tt{dp}$，在 $k=2$ 的时候是正确的可以多骗很多分。

预计是 $100+80+40+40=260$？

感觉策略有大问题。想题的时间很少，几乎所有时间都在写部分分，感觉是 T1 写了好久被吓住了 /qd，不然 $300$ 肯定能上。

要多想。

---

交了一波：

• INFOJ $100+85+40+48=273$
• LUOGU $100+85+40+48=273$

没有挂分，T4 比现象的高，民间数据排名一百出头，还行。