CSP游记

· · 生活·游记

Day-12

SCP-J 挂 T1，不会 T4，何意味。

Day0

考前不颓何时颓。凹幽境去了，n5 用时 310s，还是太有手法了。

Day1

上午 J 组。太难了，30min 切完前4题，后面的就不会了，坐牢 3h。甚至还被鼠标故障硬控 30min。

下午 S 组。T1 贪心秒了，想 T2。

这个 trick 还是去年备战NOIP时做这个题会的，于是从 O(nk\log n2^k) 开始想。然后不会了。

后来想怎么卡常的时候想到，分讨 n+1 选不选，如果选就把 n+1 的那 n 条边与原来那 n-1 条边做一下 mst，然后发现对 k 个点 dfs 时这么做就是正解了。

然后 T3。想想想（中间不想写），弄出个神秘做法，先写了 O(qn) 的代码，此时码长已经有2k，80行了。

开始优化到 O(L_2\log n)，保存 O(qn) 的代码以防正解调不出。结果写一半发现不知为何 O(qn) 的代码不见了（可能是我ctrl+z覆盖掉了），于是只能硬着头皮写。好在最后调出来了，码长 3k，120 行。不过大样例跑了 2.5s，希望ccf神机能过。

最后剩 20min，糊了个 T4 状压的 20 分，然而当时太着急导致把过面试的和没过面试的弄混了，最后也没调出。

于是 J [0,400]，S [0,300]。

Day2

考后不颓何时颓。把 ys6.1 主线过完了。

UPD：仔细计算一下复杂度发现：由于 T2 没写归并，并查集没按秩合并，于是是 O(n\log^2n2^k) 的。T3 其实是正解，是 O(26L+(n+q)\log L) 的，然而大样例跑了 2.5s，还是不太能过。

于是 J [0,400]，S [0,250]。T2T3 都不一定过我还去写 T4 暴力干什么啊！！如此成绩如何去厕所。