CSP-S 2026 邮寄

· · 生活·游记

前情提要:CSP2024 302,CSP2025 157。

提前了 40min 到考场,就打了一个线段树板子熟悉键盘,之后在玩一个我写的随机化游戏。14:29 拿到密码,Oct31==Dec25?

看 A,以为相等区间要连续,写了一个单调队列,发现大样例过不去?结果发现需要排序(注意到小样例都是初始就有序的,可见如果没有大样例就完了),这样就不用单调队列了。居然做了 15min.

看 B,题面怎么如此之长。稍微想了想才发现是 floyd 板子。写啊写,15:15 通过大样例。一开始怀疑是 O(md^2),想了想发现其实是 O(md)。其实当时是想到了不带 d<=20 限制的 O((m+q)n) 做法的。(所以为什么要加 d<=20 的限制,不加的话还是个题)

接下来把 C 和 D 都看了一下。C 注意到只能是中间一个位置有两种可能,其余位置都只有一种可能。枚举这个位置,然后随便递推,感觉只能 O(n),不存在其他复杂度。写完发现大样例不过,调啊调,发现漏一种情况。终于在 16:32 过了全部大样例,当时体感青到蓝。

还有不到两个小时,感觉可以冲一下正解。D 感觉和直径有关啊,一个连通块肯定和直径有交,那两个连通块感觉也与直径有交啊(埋下伏笔)。抽出树的直径,二分答案,确定了两个直径上的点(即左部分交的最右端 i +右部分交的最左端 j)后,令 mid=\frac{i+j}{2},r 为当前二分半径,len 为直径长度,mxd_i 表示直径上第 i 个点延伸的最大深度,则合法的条件如下:

用双指针维护 i,j,前两条限制可以单调队列维护,第三条可以预处理,还有挺多 corner case。从思路到通过大样例,已经 18:23 了。感觉有可能会被卡常,但也管不了了,检查了一下前面三题。当时感觉难度略低于去年,估分 [385,400]。

赛后似乎认识的几位同年级 OIer 都没到 300,dyf 说 t4 两个连通均与直径有交的结论不确保正确,但仍未找到反例。晚上 Ericwan 指出结论假了,提供了反例,luogu 只有 40。又发现赛时代码中,双指针 j 移动到 >len 时会出问题,这样最坏情况下只有 15 了,早知道该打暴力的)。dyf 对我做法的优化也写假了,而且多测一个地方没清空,最坏 10 分。另外 t3 怎么是紫,t4 怎么是黑?

whk 期中考试复习期间出分,100+100+100+80=380,错了四个随机分布的点。好几个同学 t3 反向挂分,dyf 400 Orz。要是直径做法写对就是 95,换种选直径的方式可以 100(所以官方数据连这都不卡吗)。现在看来不该打暴力,不过如果再多一点时间,拼上暴力就能 AC 官方数据了。

JS rk8,还行,肯定有厕所去了,或许是 CSP2026 - CSP2025 最高的选手。NOIP 加油!