CSP-S 2026 游寄

SegmentTree_ · 2026-10-31 23:22:03 · 生活·游记

啥啊？

10.30

不知道干啥了，下午打了一下 COCI 2026/2027 #1 Unofficial Mirror，T5 写了 6kb 的单侧递归板子（？）

10.31

不知道为啥早上自己起床了，打了会蔚。
入场前打了两把 ATHAZA At，aeiou 进行了神秘点评（？）
我怎么又是在十五楼打？复刻了去年的操作，爬楼梯爬上去了。
尝试把奥利奥带进去，失败了。很伤心。
开场。看 T1，怎么是简单题。
看 T2，题面怎么这么长？读了若干遍后读懂了，感觉是简单题。
在半个小时内，过掉了前两题，优势在我啊（并非
看 T3，感觉这个恰好两条很严格啊？拼尽全力只会 O(n^2)，有点寄。
大致思路是，设 a_i 表示 i 最远跳到哪，f_{i,j} 表示从 i 跳到 j 的最短路条数是 1,2,>2。感受一下，f_{i,j} 可以从 f_{a_i,j},f_{a_i-1,j},f_{a_i-2,j} 转移。
中间在草稿纸上感受了一下合法条件，好像是感觉到了一些对的东西，但是没感觉完/ll
看 T4，感觉好怪啊。尝试做到 O(nk)，发现不会，开始想 poly 做法。
设 u,v 为两个联通块的 \operatorname{lca}，好像写依托东西可以 O(n^3k)？？
感受一下，我不会做 u,v 有祖先关系，可以枚举根，做 \operatorname{lca}(u,v) 为根的情况。
最后一小时的时候狂写 5k+ 给这一坨写完了，测了一下前三个大样例，竟然都过了。希望别挂啊/kk
为防止挂完，还写了一个 O(2^n\operatorname{poly}(n)) 的东西上去，也就是保底 15pts。