题解：P17833 [CSP-S 2026] 迁徙

· · 题解

解题思路

记 l_i,r_i 为从 i 一步可达的最左、最右岛屿，包含自身。

最短路严格递增，起点右侧各层按坐标分离。两路若至少两层不同，逐层取最大、最小路径再由大转小拼接，可得第三路；同层两点不相邻时，夹点也产生第三路。故恰好两路仅有单个相邻菱形：

p\to\set{a,a+1}\to q,p<a<a+1<q,r_p=a+1,l_q=a

记 f_i 为到 i 的最短路唯一且每步均跳至最右可达点的起点数，包含 i；g_i 为反向对称量。直接起点数与递推为：

\begin{aligned} b_i & =\min(i,l_{i+1})-l_i \\ c_i & =r_i-\max(i,r_{i-1}) \\ f_i & =1+b_i+[b_i>0](f_{l_i}-1) \\ g_i & =1+c_i+[c_i>0](g_{r_i}-1) \end{aligned}

其中 [P] 为指示函数，l_{n+1}=n+1,r_0=0；非直接起点要求前驱唯一，才可继续延伸。

固定 q，令 a=l_q<q-1。此时 l_{a+2}\le a，可选前驱为 [l_{a+1},l_{a+2})；额外左延伸仅来自 p=l_a=l_{a+1}。相等时，直接前驱与额外延伸恰好合成 f_{a+1}-1，故：

s_a= \begin{cases} f_{a+1}-1 & l_{a+1}=l_a \\ l_{a+2}-l_{a+1} & l_{a+1}>l_a \end{cases}

右延伸要求 r_{a+1}=q，等价于 l_{q+1}>a+1，因此：

R_q=1+[l_{q+1}>a+1](g_q-1)

两侧边界被强制后，路径最短且仅在菱形处分叉，左右独立，答案为：

A=\sum_{\substack{1\le q\le n\\l_q<q-1}}s_{l_q}R_q

利用 l 的单调性逆向恢复 r；逆扫时 a+1<q，可在同一数组中以 g 覆盖 f。时间、空间复杂度均为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=2000005;
ll x[N];
int l[N],f[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int c,T;
    cin>>c>>T;
    while(T--)
    {
        int n;
        ll d;
        cin>>n>>d;
        for(int i=1;i<=n;i++)cin>>x[i];
        int j=0;
        for(int i=1;i<=n;i++)
        {
            while(j<n&&x[j+1]-x[i]<=d)
            {
                j++;
                l[j]=i;
            }
            f[i]=1+(j>i?l[i+1]:i)-l[i];
            if(f[i]>1)f[i]+=f[l[i]]-1;
        }
        l[n+1]=n+1;
        ll ans=0;
        for(int i=n;i>=1;i--)
        {
            int k=j;
            while(l[j]==i)j--;
            f[i]=1+k-max(i,j);
            if(f[i]>1)f[i]+=f[k]-1;
            int a=l[i];
            if(a<i-1)ans+=1ll*(l[a+1]==l[a]?f[a+1]-1:l[a+2]-l[a+1])*(l[i+1]>a+1?f[i]:1);
        }
        cout<<ans<<'\n';
    }
    return 0;
}