CSP-S 2026游记

· · 生活·游记

Day1

开场，秒 T1T2，看 T3，先把每次都往后跳到最远的点的路径拿出来，那么另外一条路径是有一步少走一个点然后后面全走 \max？有点神秘。先看 T4，没思路。先写题吧。

大概 1h 过了 T1T2，想 T3，那再把每次都往前跳到最远的点的路径拿出来，刻画一下，发现只能有一个点不同，设为

a_1 \to ... \to a_l \to i \to k \to j \to b_r \to ... \to b_1

和

a_1 \gets ... \gets a_l \gets i \gets k-1 \gets j \gets b_r \gets ... \gets b_1

设 i 往右能到的最远点是 nx_i，往左能到的最远点是 pr_i，那么第一条路径除了 b_2\to b_1 都是 nx 边，第二条路径除了 a_1\gets a_2 都是 pr 边，把 a_1 \sim i 和 j \sim b_1 拆出来算，然后枚举 i,j 应该能优化。先写个 n^2 试试。

调调调，怎么一车细节。如果 nx_{nx_i}=j 才能有 b，如果 pr_{pr_j}=i 才能有 a。现在看起来是对的，然后发现，如果 nx_{nx_i}=j \lor pr_{pr_j}=i，那么能线性枚举，否则贡献的系数为 1，直接数 nx_i-pr_j=1 数量即可，调调调，写个拍子，调调调。

剩 1.5h，优势在我吗？先猜一个连通块全在直径上，然后二分，把直径扣掉的树中树高 \ge mid 的点选上，然后把直径拿出来，变成若干个形如：某个区间内必须有选的点的限制。先考虑枚举左区间的右端点和右区间的左端点，那么可以知道两边至少选多少。显然，中间的枚举可以优化成双指针，那么要求：对于 l<i<r，有 L_i\le l \lor R_i\ge r，按 L_i 排序即可。

剩 20min 调完。感觉没啥时间拍了，瞪一会儿吧。

结束了。

Day 2

T4 假了 /ll，只有 40 了。