【迁徙】解题报告

Cocoly1990 · 2026-11-05 17:55:13 · 题解

【题目大意】

给定序列 \{x_n\}，以此构建一张图 G，u,v 之间有边当且仅当 |x_u-x_v|\leq d。问 G 中有多少无序点对 (u,v) 满足 u,v 之间的最短路恰有两条。

【解法】

考虑 l_i 为 i 最左侧能直接到达的点，r_i 为 i 最右侧能直接到达的点。

考虑判定 (u,v) 是否合法，假设其最短路为 K，考虑 k=1,\dots,K-1，考察 [l^{K-k}(v),r^{k}(u)]，这个区间内包含的点的个数称作第 k 层的大小。那么我们断言 (u,v) 合法当且仅当他所有层大小的积为 2（也就是恰有一个大小为 2 的层）。这个结论是容易证明的。

考虑记 c_i 为所有满足 j<i,r_j=i 的 j 的个数，d_i 同理。

令 F_i 表示从某个左端点出发，经过若干个层后，以层 \{i\} 结尾的路径数。

那么考虑 \{i\} 是不是第一层，有如下递推式：

同理我们定义并计算 G_i。

由于每层内的点一定是连续的区间，因此我们可以枚举这个唯一的二层内的点 a,a+1。

考虑左侧的路径数，如果 {a,a+1} 是第一层，那么起点的个数是 c_{a+1}-[r_a=a+1]。如果他不是第一层，那么左侧的层必须是 \{l_a\}，且它必须同时满足 r_{l_a}=a+1，然后把 F_{l_a} 加进来。

右侧的方案数同理，那么答案就是每个 a,a+1 左右两侧的方案数的积。可以证明这是不重不漏的的。

时间复杂度 \mathcal{O}(n)。期望得分 100。

【总结】

题出的好！难度适中，覆盖知识点广，题目有着切合实际的背景，解法比较自然。给出题人点赞 ！

本题解法多样，在发现了最开始的核心性质后，有足够多的办法在多项式时间复杂度内完成后续的计数。通过对做法或题目的进一步分析，也几乎都能得到比较容易实现的线性或小常数线性对数做法，均可以通过全部数据。

出题人赛前预设并准备了接近两位数种可能错误的解法，并做了针对性的构造。但很遗憾仍然有非常多意想不到的错误做法取得了不符合预期的高分。虽然客观上本题数据准备难度较高，但数据过水仍然是不可推脱的失误。在这里向所有受到本题数据或大样例影响的选手道歉。