CSP-S 爆炸寄

· · 生活·游记

感觉整体来说，做题速度慢导致了整场没有发挥好。

T1 第一眼想到了个贪心，小样例没过，后来发现需要反悔，花费 30min。

T2 第一反应想到了最小生成添加一个点后，新的最小生成树的边除了新加的点一定是原最小生成树边的子集，但却往 kruscal重构树 方向想了，第一版枚举选的点集，写了个贪心，假了，30min，第二版写了个 状压dp，1h25min，假了，最后发现枚举点集后直接跑最小生成树即可，10min，O(2^knk \log(nk))，考场降智，没想到可以直接归并，先去做后面的。

T3，第一反应 AC自动机，然后就不是很会，先看 T4，发现可以拿到 24pts，写完后，因为各种读错题，浪费了 0.5h，最后剩 40min 冲 T3 的 O(Ln) 的做法，hash 没调出来，遗憾离场。

赛后 T3 秒会......

总分：100+[80,100]+0+24。

整场打下来，最主要的就是 T2 一开始想歪了，做的太慢，以致于后半场心态都不是很稳，接下来一方面要训练做题速度，另一方面就是比赛最后一个小时的心态，我太容易红温，心理素质还是需要练的。

upd 11/06 ：实际得分 100+80+0+0，T4 因空间过大，导致 MLE。

警钟长鸣！要算空间！