爱是难驯鸟，哀乞亦无用

· · 生活·游记

CSP-S 游记。

初赛记不到多少分了 /xk，反正过了。

Day 0

补了一下之前的试题，复习了几个感觉不太熟的模板，然后和 Turkey_VII 一起口胡了几道黄绿。晚上一个人在宿舍复习（颓废）了一会儿。

感觉压力好大、这个不能是我的退役文吧……

Day 1

昨晚睡的非常难受，一直处于“躺在床上睡不着 \rightarrow 浅睡了一小会儿 \rightarrow 醒来”的循环，从 23 点到 7 点一共只睡了 3 个小时左右，深度睡眠时间为 0。

早上点了一杯瑞幸拿铁、本来想继续口胡几道题却发现自己完全静不下心来、想颓废但却越颓越焦虑。明明只要不爆零就可以晋级下一轮的，但感觉像是自己最后一场 OI 比赛了一样……

于是浑浑噩噩的度过了一个短暂的上午。

就好像闭眼再睁眼、就已经开始进考场了。

吐槽一下座位的这个诡异电脑、不知道是哪个可爱的小朋友把 F11 换成了 F10 的按钮样式、然后 Dev 每编译一次就要未响应一会儿、我真不行了。

开始考试，密码晚了 5 分钟才下发。

T1 签到题、看完题就做出来了，排序后双指针即可，14:40 的时候代码写完。

T2 抽象题面，一开始看错题了以为线路内的移动也有代价，白白消耗了 20 多分钟。之后手模了第一个样例，想到了由于 n\le500 且 d\le20 所以可以以线路为起点跑最短路，询问时枚举起点终点进入哪条线路，但是这样就算跑单源最短路也是 O(n(n+m)\log(n+m)+qd^2) 的，然后考场上犯傻死活想不到怎么优化，于是只好在 15:30 前写完了这份 68\text{pts} 的部分分。

然后把 T3 和 T4 的题都先读了。玩了会儿 T3 发现答案好像是形如 (a,b,b+1,c) 的四元组，其含义为：x_a,x_c 均可到达 x_b,x_{b+1} 且 x_a\sim x_b 之间的点无法到达 x_c、x_{b+1}\sim x_c 之间的点无法到达 x_a，然后这个东西貌似可以预处理之后计数。进一步发现 x_a 向左扩展貌似也有可行情况，右侧同理，但是扩展条件一直没有推出来。

改看 T4，最大值最小显然在 [0,n) 内二分答案。单个连通块貌似是好做的，但是没有想到如何推广。思考了一会儿无果。

额额然后又跳回 T3，可能推出了左侧的扩展条件是存在 x_p 可以到达 x_a 但无法到达 x_b，继续扩展就是 x_q 可以到达 x_p 但无法到达 x_a，类推、右侧同理。还是没有想到如何计数，稳妥起见写了一个较简单的 O(n^2) DP。此时应该已经 17:00 左右。

于是求稳先把 T4 的 O(2^n) 朴素做法以及特殊性质写了。后续的 T4 思路非常混乱，最终较成型的只有将单连通块的点标记，以直径中心为根从叶节点的 \left \lfloor \frac{V}{2} \right \rfloor 祖先开始做树上 DP 的 O(n^2\log n) 思路，但是只过了部分样例，不敢交。就这样绝望的度过了剩下的时间。

おわった。

估分只有 100+68+40+25=233\text{pts}，挂分另说。考的好烂好烂、这是退役前兆吗……

晚上和同学在学校旁吃烧烤 & 打台球。可能这是 -S 专属吧，打完 NOIP 应该就没有这个心情了。回家时非常幸运的赶上了地铁的末班车（我的 RP 就天天用到这种地方 /ll）。

希望 NOIP 可以考好一点吧……