终章 CSP S

Star_sea_eternal · 2026-11-01 20:32:01 · 生活·游记

前言

@TP2010 的神仙 游记，好游记要顶！！！sto 神 Wxb。

以前懒得写游记了，最后一次 CSP-S 了，还是来写一篇。

正常发挥，100+100+[40,48]+[15,20]=[255,268]，应该是不留遗憾了，毕竟我确实切不了紫。

Day 0

学校体测，由于个人原因并没有参加跑步等项目，非常庆幸。据同机房反应，跑步后身体状态不是很好。

晚上 6:30 出发，8:00 左右到达华科校内酒店。晚上随机做事，不是很想复习，11:30 才睡觉。

Day 1

上午

早上因为生物钟，7:00 就醒了，7:30 起床，去食堂吃了碗热干面（感觉并不好吃，没吃完就吃不下了），豆浆味道常规。

强迫自己复习了可并堆等不是很熟悉的内容，再大致看了一眼写的学习笔记和技巧之类的。

11:30 前又早早吃饭去了，避免人多。中午也不是很好吃，油比较多，点了个鸭腿味道也不是很好。

回去准备了一下东西，两瓶水、两个橘子、两个巧克力和文具卫生纸，万事俱备！又大致看了眼笔记，不知不觉发现 J 组出来了，难度红橙黄绿，当时断言 S 组也不是很难，认为和去年差不多 T_T。

1:00 退了房，坐在前台外面新开的面包店里（类似于咖啡厅），感觉环境氛围挺不错的。

当时不想看 J 组题目，避免被影响心态。听同学说 T3 秒了，而且题目不长，遂看了一眼，显然也秒了。然后他又说 T4 没一眼秒，我一看标签是神秘树论，就没看。

下午

全军列阵！出发！和神 Wxb 一个考场，rp++。

下发了开机密码，终于没像以前那样鬼畜了（虽然还是输入错了好几次）。

敲了快读模板，发现键盘不是很习惯，\ 的位置不对！只能凑合着用了。赛时因为这个打错了好几次。

下发压缩包密码，这次直接发到了选手桌面上，非常良心。

扫了一眼所有题目，发现题目类型和我预测的一模一样！？！

T1

开干，第一眼二分。考虑二分答案，发现不具有可二分性。再考虑 O(n) 枚举变成的值，二分求出可以这时的答案，去 \min 即可，15 min 过了。

T2

慢慢读题ing，w_i 显然来搞笑的，然后花费较长时间读懂题意。这个数据范围有点复杂，猜一下需要用 Dij，再猜时间复杂度为 \mathcal O((m+q)d) 状物（\log 省去），但是 n 的数据范围有点诡异。

发现询问是多次给定 x,y，这个 Dij 能做？难不成是生成树之类的？后者显然假了，Dij 此时也没啥思路，很慌呀，吃个巧克力。

找些性质，在最短路上，一个点只会经过一次。令 i 为换乘的点，只需要计算 t_{x,i}+t_{y,i} 的贡献。在最短路上，一条线路也只会经过一次。突然一拍脑袋就会正解了，n 是关键呀。

对于询问，枚举初始和末尾的地铁站，那么只需要求出两个地铁站之间的最短路即可。

显然初始边就是枚举每个节点作为换乘点，做个 Floyd 就好了，没想到今年考 Floyd。差不多又用了 1 h 过这题。

T3

心态稳了很多，但理想情况还是做出 T3，背水一战！

一眼 DP，恰好只有两条的限制很紧，但很不好做啊。

感觉 \mathcal O(n^3) 并不困难，想想后发现 \mathcal O(n^2) 也可以做，转攻特殊性质。

特殊性质 A 显然可做（埋下伏笔）。特殊性质 B 也很强啊，但死活没想到怎么做，想了很久没想出来。于是决定看 T4。

从 T4 回来后拼命想，然后貌似胡出来一点东西，大概率是对的。此时时间不多了，赶紧写代码。

先写 A 性质，调整一下思路迅速写完。再写 B 性质，感觉是一坨，强制自己写完了。

赶紧思考一下 \mathcal O(n^2) 怎么写，想了个差不多的 DP，但是是 \mathcal O(n^3) 的啊，实在不行只能硬着头皮写了。

这时考察一下最短的限制，发现从能到达的最左边的转移而来就是最短路，再考察它右边的三个点就可以转移了，成功做到 \mathcal O(n^2)。

并不难写，调了一下就过了小样例。然后挂着跑一下样例四，去写 T4 暴力了。（我感觉此时调特殊性质 B 是划不来的，并不能保证 100\% 能拿到手）

写完 T4 暴力后代码也跑出来了，有惊无险地过了。

再测一下特殊性质 A，此时时间不多了，预计特殊性质 B 没时间写了。样例四就是特殊性质 A。

一测吓一跳，发现差了十万八千里，此时没有任何头绪啊，已经开始倒计时了，赶紧对着样例猜做法啊。

发现答案均 <n，估计可以 \mathcal O(1)，而且是 n-y 这种。然后 x=d/(a_2-a_1) 肯定要用上，发现有 3 个 n=10 的点，后两个本质相同。前两个的 x 只相差了 1，但答案相差 2，再根据一个很大的数据，我的输出是答案的差不多 2 倍，猜了猜就过了。

T4

指数是简单的，15 分有了。考虑挖掘性质，分成两份一定不劣，然后就倒闭了。发现只有特殊性质 A，这该如何入手！发现有 k=2 的，感觉肯可做，回去做 T3 吧。

指数轻松写完了，没调过样例一，非常高兴，随后就被样例二卡了。扫了一遍代码发现没有什么低级错误，赶紧手模样例，再调试一下代码，发现忘记判是否形成了 \le 2 个连通块了 /yun。