CSP-S 2026 migrate 题解

· · 题解

场上被这个题击败，WC 梦断。赛时暴力都没拼明白，以下有效思考均在场外进行。

怎么没人讲怎么拼包。补一篇。

24pts，n \le 300

枚举起点 L，f_{i,j} 表示 L \to j 跳了 i 步的方案数，转移为

f_{i,j}=\sum_{\substack{k<j \\ x_j-x_k \le d}} f_{i-1,k}

前缀和优化一下，注意到 DP 值可能很大，每次算完对 3 取个 \min 就完事了，前缀和最大是 3n，可以接受。\mathcal O(n^3)。

40pts，n \le 5000

考虑怎么刻画路径最短。

令 x 往左往右跳到的最远点分别为 \text{pre}(x), \text{nxt}(x)。

枚举起点 L，可以发现 L+1 \sim \text{nxt}(L) 是要一步跳到的，nxt(L)+1 \sim \text{nxt}(\text{nxt}(L)) 是要两步跳到的……这样简单把点分层，每一层的点只能跳到下一层的点，就是最短路的充要条件。

有了这个结论再 DP 就能做到 \mathcal O(n^2)。

48pts，性质 A：等差数列

设公差为 D，d<2D 只能老老实实一格一格跳，这个时候方案数恰好为 1；否则设 t=\lfloor \frac{d}{D} \rfloor，如果两个点恰好相差 t 的倍数个格子那么跳的方案也唯一了。

这个时候我们进行一些微调，把终点往左移动一格，会发现多了一些每次跳的长度形如 t \to t \to \cdots \to t-1 \to \cdots \to t 的路径，当且仅当取一段长度为 2t-1 的格子时方案数恰好为 2；终点继续往里面移方案数只会更多，所以答案就是 \max(0,n+1-2t)。

正解

这个题做法很多，对着上面的 DP 继续优化似乎也能做；这里提一下顺着我考场思路的做法。

固定起点、终点 u,v，若 u,v 可达，考察两条最极端的最短路径：

  1. 从 u 开始贪心地往后跳 \text{nxt}，能够到 v 就停下来，设这条路径为 a_1 \dots a_m；
  2. 从 v 开始贪心地往前跳 \text{pre}，能够到 u 就停下来，设这条路径为 b_1 \dots b_m。

形式化地，有

显然有 \forall i, a_i \ge b_i。

如果这两条路径实际是同一条，显然方案唯一。否则画出来可能长这个样子：

证明：假设存在 w 满足 b_i < w < a_i，如上图绿色的点，由于 w>b_i 且 b_i 可以一步跳到 b_{i+1}，w 也可以一步跳到 b_{i+1}；同理 a_{i-1} 可以一步跳到 w。于是可以构造出一条新的 ab 交替的路径 a_1 \to \dots \to a_{i-1} \to w \to b_{i+1} \to \dots \to b_m，矛盾。

证明：考虑一个长这样子的结构。

你发现这个结构至少出现一次时才能区分 ab 两条路径；如果出现两次就会有两处分别走 aa,bb,ab,ba 的情况，与题意不符。

我们已经证明了满足题目条件时，a,b 两条路径几乎重合。

接下来证明必要性：假设存在第三条路径，令其最早不与 a_i/b_i 重合的落点在第 i 步 c_i 处，则 a_{i-1} < c_i < b_i。既然 c 在第 i 步已经落后于 a/b，那么需要存在一个更大的 j 使得 c 在第 j 步处赶上 a/b；由于 \text{pre}(b_{i+1})=b_i，如果 c_i 能直接跳到 b_{i+1} 则与 \text{pre}(b_{i+1}) 的最小性矛盾，所以 c 永远赶不上 a/b，至少需要多花一步才能跳到 v。

以上分析了结构，考虑如何计数。

看上去枚举 (a_i,b_i)=(x,x+1) 这个唯一的位置 x 会比较方便，不妨先分析右边的结构，左边同理。

  1. b_{i+1}=v

需要满足 \text{pre}(v)=x, v \le \text{nxt}(x+1)，由于 v \le \text{nxt}(x) 那么后面一个条件已经满足，统计 \text{pre}(v)=x, v\neq x+1 的个数即可。记这个个数为 cr(x)。

  1. b_{i+1}=\text{nxt}(b_i)

后面会接上 \text{pre}=\text{nxt} 的若干段，末尾需要有 \text{pre}(v)=b_{m-1}。考虑一个递推，g_i 表示从 i 开始这种结构的方案数，一开始 g_i = \#\{\text{pre}(v)=i\}，从右到左扫一遍算就行了。这个个数就是 g_{\text{nxt}(x+1)}。

左边也处理一个 cl(x+1), f_{\text{pre(x)}}，对于 (x,x+1) 答案就为

[cl(x+1)+f_{\text{pre(x)}}] \times [cr(x)+g_{\text{nxt}(x+1)}]

这个做法想清楚了就没啥细节，只要注意一下往左往右是否没法跳就行了。

void solve(){
    scanf("%d%lld",&n,&d);
    F(i,1,n) scanf("%lld",&x[i]), f[i]=g[i]=cntp[i]=cntn[i]=0;
    for(int i=1,j=1;i<=n;++i){
        while(x[i]-x[j]>d) j++;
        pre[i]=j;
        if(j!=i) cntp[j]++;
    }
    for(int i=n,j=n;i;--i){
        while(x[j]-x[i]>d) j--;
        nxt[i]=j;
        if(j!=i) cntn[j]++;
    }
    F(i,1,n){
        if(nxt[i]!=i) f[nxt[i]]++;
        if(pre[i]!=i) g[pre[i]]++;
    }
    F(i,1,n)
        if(pre[i]!=i&&nxt[pre[i]]==i) f[i]+=f[pre[i]];
    rf(i,n,1)
        if(nxt[i]!=i&&pre[nxt[i]]==i) g[i]+=g[nxt[i]];
    ll ans=0;
    F(i,1,n-1){
        ll R=cntp[i]-(pre[i+1]==i)+(pre[nxt[i+1]]==i)*g[nxt[i+1]];
        ll L=cntn[i+1]-(nxt[i]==i+1)+(nxt[pre[i]]==i+1)*f[pre[i]];
        ans+=L*R;
    }
    printf("%lld\n",ans);
}

https://www.luogu.com.cn/record/307770026。