题解：P17833 [CSP-S 2026] 迁徙 / migrate（民间数据）

· · 题解

:::warning[警告]{open} 本篇题解在写完后使用了 GPT 进行润色，润色前的内容放在了文末。因为我感觉自己写的不太像是人话，就用 AI 润色了一下。 ::: 为方便描述，我们把岛屿看作数轴上的点，向右为正方向，只考虑从左边的岛屿出发，前往右边的岛屿。

首先，最短路一定不会往回跳。否则，在路径转向的位置，前后两座岛屿可以直接到达，跳过中间的岛屿就能少飞一次。

求最短路的长度也很简单：每次都尽量往右跳，能直接到终点时就跳到终点。因为跳相同的次数，贪心能到达的位置一定最靠右，所以这样得到的飞行次数最少。

接下来，考虑恰好有两条最短路时，这两条路径长什么样。

从起点开始，找到两条路径第一次不同的位置，设它们在这里分别经过 a,b，且 a<b。我们把经过 a 的那条路径中的 a 换成 b：

这里，b 必须在下一座岛屿的左边。否则，共同的前一座岛屿就能直接跳到这座岛屿，省掉一次飞行，与原路径最短矛盾。

因此，替换后仍然是一条最短路。如果原来的两条路径在后面还有不同，那么替换得到的路径就同时不同于原来的两条路径，成了第三条最短路。

所以，两条最短路只能在一个位置不同。

而且，这个位置上的两座岛屿必须相邻。否则，选一座夹在它们中间的岛屿替换这个位置，又能得到第三条最短路。

于是，两条路径一定形如：

u\to\cdots\to p\to i\to q\to\cdots\to v u\to\cdots\to p\to i+1\to q\to\cdots\to v

只有中间选择了 i 还是 i+1 的区别，其余部分完全相同。

我们可以枚举这对相邻岛屿 (i,i+1)，分别统计左边有多少个起点、右边有多少个终点可以与它们组成这样的两条路径。

先看左边。一个起点 u<i 需要满足：

第二个条件也不能少。如果同样的次数还能到更右边，就能用更右边的岛屿替换中间的落点，或者直接跳过这一段，产生第三条最短路或更短的路径。

右边的要求完全对称：从终点 v>i+1 出发，到 i、i+1 的最短路都唯一、长度相同，并且向左贪心后，最远恰好到达 i。

满足条件的左右两边可以任意组合。设左边需要跳 k 次，右边需要跳 l 次：

所以，第 k 次飞行后只能落在 i 或 i+1。这两种选择的前后路径都唯一，恰好得到两条最短路。

因此，枚举 (i,i+1) 后，把左右两边的方案数相乘即可。

下面考虑如何在线性时间内算出左边的贡献。

先用双指针求出：

维护两个状态：

其中，g_i 就是枚举相邻岛屿 (i,i+1) 时，左边的贡献。代码中，f_i,g_i 分别对应 dpl[i][1]、dpl[i][2]。

这里有一个性质：一条最短路如果唯一，那么除最后一步外，每一步都必须向右贪心。

否则，把某一步的落点换成更右边的岛屿，要么仍能接上下一步，得到另一条最短路；要么可以直接跳到下一座岛屿，少飞一次。两种情况都不符合要求。

因此，我们只需要从 f 状态出发，考虑再跳一步，就能完成所有转移。

按 i 从小到大处理，记 r=rp_i。

首先，把 i 本身作为一个新的起点：

然后，考虑把 f_i 中的路径再延长一步。

新的贪心落点是 r，所以只需要考虑更新 f_r 和 g_{r-1}。关键是：延长以后，最短路还必须唯一。

设新的落点为 j。在此前的飞行次数内，贪心最远只能到 i，所以最后一步不可能从 i 右边出发。要让最后一步只有一种选择，就需要 lp_j=i，即能跳到 j 的岛屿中，最左边恰好是 i。

如果 lp_j<i，那么 i-1 也能跳到 j，就会出现另一条最短路。因此，转移为：

第二条转移还要求到 r 的最短路唯一，不过这不需要额外判断：当 lp_{r-1}=i 时，由于 i 能跳到 r，必然也有 lp_r=i。

右边的贡献完全对称，从右往左处理，把“向右贪心”换成“向左贪心”即可。

代码中的 dpr[i+1][2]，恰好表示相邻岛屿 (i,i+1) 右边的贡献。因此，答案为：

\displaystyle \sum_{i=1}^{n-1} dpl_{i,2}\times dpr_{i+1,2}

双指针和两遍 DP 都只需扫描一遍数组，每组数据的时间复杂度为 O(n)，空间复杂度为 O(n)。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll pos[2000005],lp[2000005],rp[2000005];
ll dpl[2000005][3],dpr[2000005][3];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int _id,T;
    cin>>_id>>T;
    while(T--){
        int n;
        ll d;
        cin>>n>>d;
        for(int i=1;i<=n;i++)cin>>pos[i];
        int p=1;
        for(int i=1;i<=n;i++){
            while(p<=n&&pos[p]-pos[i]<=d)p++;
            rp[i]=p-1;
        }
        p=n;
        for(int i=n;i>=1;i--){
            while(p>=1&&pos[i]-pos[p]<=d)p--;
            lp[i]=p+1;
        }
        for(int i=1;i<=n+1;i++)for(int j=1;j<=2;j++)dpl[i][j]=dpr[i][j]=0;
        for(int i=1;i<=n;i++){
            if(rp[i]>i)dpl[rp[i]][1]++;
            if(rp[i]-1>i)dpl[rp[i]-1][2]++;
            for(int j=1;j<=2;j++){
                if(rp[i]-j+1<=i)break;
                if(lp[rp[i]-j+1]!=i)break;
                dpl[rp[i]-j+1][j]+=dpl[i][1];
            }
        }
        for(int i=n;i>=1;i--){
            if(lp[i]<i)dpr[lp[i]][1]++;
            if(lp[i]+1<i)dpr[lp[i]+1][2]++;
            for(int j=1;j<=2;j++){
                if(lp[i]+j-1>=i)break;
                if(rp[lp[i]+j-1]!=i)break;
                dpr[lp[i]+j-1][j]+=dpr[i][1];
            }
        }
        ll ans=0;
        for(int i=1;i<n;i++)ans+=dpl[i][2]*dpr[i+1][2];
        cout<<ans<<'\n';
    }
}

:::info[AI 润色前的内容] 为了方便，把坐标看作数轴，正方向为右。首先，最短路的长度显然是尽量贪心往右跳，至少跳的次数。

然后，最短路恰好有两条，说明两条最短路必须只有一个不同点，而且这两个点要是相邻的。因为如果不相邻，考虑取中间的点显然满足条件。如果不同点不止一个（假设有两个），考虑如果这两个位置不相邻，则把一个换成另一条最短路中的对应点显然还是合法的最短路。如果相邻，则化简后有两种大小关系：1\to 2\to 4\to 6 和 1\to 3\to 5\to 6，或者 1\to 2\to 5\to 6 和 1\to 3\to 4\to 6。这两种情况显然都不止两条最短路。

因此我们枚举这两个相邻的不同点，考虑计算左右两边的贡献。不难发现要求是两边的点，贪心跳的过程中，跳到这相邻两个点的最短路都只有一条（且长度相等），且其中一个点是贪心跳的端点（即不能跳的再远了）。显然可以分开计算左右两边的贡献然后乘起来。

然后我们以左边的贡献为例，维护 f_i 表示选择一个点出发每次选最右边的点可以跳到 i 的方案数，g_i 表示从某个点出发每次选最右边的点可以跳到 i+1，且到 i 和 i+1 都只有一条最短路的方案数，转移显然是随便转移。右边的贡献同理，最后每个位置左右的贡献乘起来即可。时间复杂度 O(n)。