CSP-S 2026 游记

· · 生活·游记

最后一舞吗。

我要去 WC!!!!

Day -?

其实我没有参加初赛,如果有人在初赛考场看到了我,那大概是看错了。至于我为啥没参加初赛还能进复赛这个事,我还没想好怎么编。

Day -1

自由复习。随机开了几个真题,把种树和星战秒了,与树上的数搏斗十个小时未能战胜。

Day 0

尝试宣传面积失败,我的考场小众又独特/ll

下午太无聊了随机打了几个板子,然后就是颓颓颓颓到了回家。

晚上也没啥复习的欲望了,练了一道串串睡觉去了。

Day 1

起得比较早,吃完午饭很快就出发了。

去到的时候没啥人,在考场外面刷了会儿手机陆续看到很多同学都进来了,和同学进行了一些信息熵为零的对话。

呃呃啊啊就准备进考场了,感觉还是有点紧张啊。到了座位上对自己进行了一些鼓励,钦定了自己必须把 T3 冲出来。

开考。

用 10\text{ min} 敲了模板并秒掉了 T1。这也太唐了。

看 T2,题面怎么又臭又长/tuu。进行了仔细的阅读后理解了题意。看了一眼怎么感觉不会,又看了一眼,哎是不是求出线路的全源最短路就好了。这也太唐了,我也太唐了,这个 w 又是何意味。

调完代码大概是 15:10,前两题也太蠢了,这下不得不猛冲 T3 了。

看 T3,好奇怪,感觉没啥想法。再看一眼 T4,怎么感觉这个也这么难。

还是冲 T3 吧。

把两条路径不同的位置取出来好像就变成了路径唯一的限制,那路径唯一咋做来着?玩了一会儿感觉不太会,怎么这么倒闭。又对着贪心跳出来的树分析了一会儿,感觉还是不会。

这会儿毛估估应该玩了 30\text{ min} 了。有点生气。

集中了一下注意力,哎这个路径唯一是不是等价于向左跳和向右跳得到的路径一样!那向左跳和向右跳不同的位置只能差 1,会不会这个就是对的!

写了个暴力 check,挂了 migrate3。

更加生气了,哎哟这个咋能是错的来着。尝试换思路无果。

这会儿毛估估应该又花了 30\text{ min},有点慌,难道我真是彩笔?

感觉我这个左右跳的思路很对啊,再想想。尝试让自己冷静下来又推了一会儿。哎,好像只能有一个不同的位置啊!

改了一下暴力 check,把 migrate3 过了!

这下优势在我了。那我枚举一下不同的点,再枚举一下前驱后继,两边可以化成 DP 状物。这个不是对完了!改了个暴力 DP。唉这个暴力 DP 用桶优化一下就好了,改改改,怎么改错了,调调调,哎终于调对了!

这时候大概已经 17:10 了。感觉如释重负,这个 T3 大抵不是很简单的题。

感觉状态上来了,来看一下 T4。

显然可以断边分成两个连通块来做吧。这个 n,k 这么大肯定不能是树形背包之类的,所以要往别的方向想。

思考了一下 k=1,这不是我们直径中点吗?哦那这个连通块肯定要包含直径中点,这就好做很多了!那我二分一下答案,以直径中点为根,深度为 d 的点要求它的深度为 d-mid 的祖先被选中,这样直接就能求出选出的最少点数了。这个直接就是 \mathcal{O}(n^2\log{n}) 的了,好像有 40 分。

这个时候大概 17:30 了。想了一下能不能继续优化,感觉没啥想法。

是不是该写暴力了?感觉我没有能冲出这个题的时间和精力,还是写暴力吧。

我写写写。怎么挂 hub3 了,这我调你马。监考员又催着比赛快结束了,草啊好慌,300 真的够用吗?努力让自己冷静下来观察了一遍代码,哎这个两个中点的情况是不是写错了,我改改改,呃啊终于过了。

压哨调出来了属于是。这也太吓人了。

出考场遇到了 @Louis_lxy,说是 300 分,没调出来 T4 部分分。这也太牛了!!!

人多的要死。车多的要死。好烦。在喜悦和烦躁的情绪中走到了比较远的地方打了个车回家了。

水群,感觉说 T3 简单的和被 T3 创飞的都大有人在。

若干认识的人都打得不是很好,呜呜,好遗憾。

复现了考场代码。唉这个 \mathcal{O}(n^2\log{n}) 为啥 50 分?不管了,摆。

我要去 WC!!!!