CSP-S2026游记

· · 生活·游记

大概也是非常的爆炸，考前听说YN一堆半脱产搞信竞的高中生，压力好大……

直接跳到开考的部分吧.

很幽默的是去年省选 Day 2 由于试题直接放在桌面上我们提前 10 分钟就可以开始做了，于是今年 CSP-S 14：30 才开始发题目，CCF 给的总共几十 M 的大样例加上机房的乌龟传输速度也是让我在 14：38 才拿到题，算是把省选偷的时间补上了吧（雾）

拿到 T1 不出意料的读错了，以为是要相邻才能合并，然后对着题想了半天只会 O(n^2)，非常难受于是去阅读样例发现看错了，如果可以随意组合的话那不就是个板子双指针嘛！在大概 14：52 通过了所有大样例。

看完 T2 感觉有点懵，然后手算了一下发现每条铁路可以缩成一个点，建完模以后我草这不是CF1301F吗？刚好 CSP 之前在 dmy 集训做过这题，dmy 立大功。然后就是复写了一遍代码就直接过了所有大样例，最慢的跑了 1.9 s，考虑到 sf 机房老年机感觉问题不大。这题是 15：25 过的。

然后就是 T3 啊，看完等差数列的样例把后面几组小的数据拿出来手玩，发现是不是符合条件的 u,v 一定恰好 2 步可达，那不是一个双指针秒了吗。四点多写完一测假完了。

没办法只好写个 O(n^3) 暴力，枚举 u，转移所有 i>u 的点跳的最小步数和方案数，方案数刚好为 2 的算进答案里。写的也是很快啊。考虑优化，发现转移的时候可以从前往后枚举而不是从后往前，这样一个点最多从 2 个前面的点转移，那就是 O(n^2) 的了，于是 40 pts 到手，此时 17：19。

继续思考，感觉不是很能做啊，显然对于固定的 u，合法的 v 一定是连续的一段，看起来可以双指针但我好像没法 O(1) 判断给定 u,v 它们满不满足要求。特殊性质好像也不太会（当时再推推那个等差数列应该是能写的）

那就开 T4 吧，我首先想到的是枚举两个连通块的最上层的那个点，不过想了想暴力还要枚举很多。然后突然看见最小值最大，那先二分吧。二分完了 k=2 的应该就很好做了，显然是两个点中间连着 mid\times 2 的链，两个点下分别连一些 mid 长的链。

然后我也是对着这个非常好做的东西写到结束也没调出来。因为大样例全部偏小，我甚至还怀疑这个是不是没有单调性。

不管了倒闭， 100+100+40+0，出来一看蒙自那边全是 250 以上的。CCF 下次能不能出点有区分度的比赛啊我服了。

另：