CSP-S 2026游记

_liukelin_ · 2026-11-01 19:30:12 · 生活·游记

:::info[省流] :::

Day -0.5

在机房写模板赛,发现怎么字符串这么差劲,连夜看了KMP,manacher,AC自动机期望不考容斥原理那些.考了绝对不会

然后感觉颓废了半个上午,剩下半个上午在看一些考前n问,有点紧张.

中午和@pap_han,@fantasticjimmy一起吃余割函数.然后坐地铁去CQBZ,和去年一样,CQBZ的厕所高度严格小于 1.2m 上厕所时特别没有安全感.

Day 0

进场了,很紧张,可能是因为我已经高二了,有些心理压力.

• 14:25 发压缩包密码了,密码很搞笑,好像有什么 DEC 31 之类的东西.
• 14:26 开始看T1,感觉有点困 早知道中午睡午觉了,早知道前一天晚上不干了,感觉这题有点东西啊,怎么合并还要+1的???

P.S. 有人第一次看错题了

• 14:34~14:40 怎么周围人都写完了,哦原来是我看错题了,重新思考发现,考虑最后的答案应该是取到一个 a_i 的值,如果卡在 a_i 和 a_{i+1} 中间可以选择把多的部分给到比它们小的数上可能会产生新的答案.所以我们可以考虑枚举最后的这个数是哪个 a_i 画出图来发现只需要统计比它小的前缀和,然后要补的部分数值对于每个 i 一定是单调的,于是我们可以二分,时间复杂度 \mathcal{O(n \log n)} 应该可以通过.

• 14:40~15:00 我写写写,写完了,嗯,大样例也过了内心OS:应该没问题吧,由于一直在喝水,所以直接去上了一个WC

• 15:10 上完了发现对于T1的 m=0 有点小问题,简单修改一下

• 15:13~16:00 开始看T2发现这个应该是和 n 有关的floyd 因为这样才能处理询问,不然就只能是每次询问跑一次dijkstra显然不可接受.考虑怎么才能归到和 n 有关的复杂度,看样例的时候发现同一条地铁线上的点互相到达的时间为0,这个就可以使用类似于缩点的方法解决,每个线路之间最短的换乘的时间就是对应线路上的站点的最短时间.又注意到每个点最多只被 d 个线路覆盖所以这样是很优秀的,询问只需要暴力枚举 x 和 y 所在的线路,找最短路再加上进入站台的和的最小值即可,总时间复杂度 \mathcal{O(qd^2 \log d+md^2+n^3)} 多了个 \log d 是因为我写的是 map,一鼓作气写完居然直接过了所有样例,开心了直接去上了个撤硕.

• 16:00~17:40 死磕T3发现怎么都不是我可做的题,考虑写暴力,定义一个 f_i 表示 (u,i)(u < i) 的满足条件的对数,发现其实是倒着一直找就行了,先看那些可以一步到的,这种的一定不是答案,然后看一步到里面的最后两个 j 和 j+1,向前找离这两个距离 \le m 分别作为 l 和 r,这样 [l,r] 内的数到 i 这个点就只能要么直接去 j 然后直接去 i 要么只能去 j+1 然后直接去 i 一定是两种,并且这个是一直往前递推的每个 j 都可以一直这么找直到 j\le 1,又 x_i 单调上升,于是可以直接二分一下来找,但是这个代码巨tm难写,写了很久给我时间写完了.还不知道对不对,只验证了小样例...

• 17:40~18:20 狂写T4准备直接 n\times 2^n 枚举再判断联通块是不是 \le 2 个然后用 倍增LCA 计算距离,但是没有时间了,只能先开始检查了.剩余 10\min 完全写不完.

• 18:20~18:30 检查freopen,long long,以及数组大小去年因为这些在CSP-S挂了 60 分,在NOIP挂了 10 分.

• 18:30~18:45 签字确认,厚礼蟹对面那哥们怎么做出T3了,WTFdp套dp没学怎么说,拜拜了, liukelin 小弟👋👋👋

Day 1

不是怎么大样例这么水啊,我不会挂分吧???如果挂了只能🤬🤬🤬然后再🥵🥵🥵了啊啊啊啊啊啊啊啊啊啊!!!!!

然后骨粉,感觉不是很高啊话说洛谷居然评价的是 \color{yellow}{黄}\color{green}{绿}\color{purple}{紫}\color{black}{黑} 啊有点colorful

最终股份: