CSP-S 2026 C题迁徙题解（9个解法）

零、背景

之前已经分享了历年 CSP-J/S 的比赛题解与《CSP-J 2026 的题解》。

这几天开始分享 CSP-S 2026 比赛题解。
为了避免四道题放在一篇导致文章过长，我计划每道题单独写一篇，最后再给出一个总结。

上篇文章分享了《CSP-S 2026 A题能量水晶（6个解法）》和《CSP-S 2026 B题地铁题解（8个优化）》。

这篇文章分享 CSP-S 2026 第三道题「迁徙 migrate」的题解。

PS：pdf 题目和源码已经上传网盘，后台回复 CSP-S-2026 获取题目与源码。

一、题目

海上有 n 座岛屿，自北向南排成一条直线，第 i 座岛屿的坐标是 x_i，严格递增。
海鸟每次飞行的距离不超过 d，所以坐标差不超过 d 的两座岛屿之间可以互相直飞。

两座岛屿之间的一条路径，就是一串首尾相接的直飞，路径长度是飞行次数。
海鸟只走长度最短的路径。
对于 u < v，如果从 u 到 v 的最短路径恰好有两条，就称 (u, v) 是双径岛屿对。
两条路径不同，指的是经过的岛屿序列不完全相同。

问一共有多少个双径岛屿对。

二、算法分析

先想清楚两个基础问题。

第一个，最短路会不会往回飞。
假设存在往回飞的路径，往回飞后还要再飞回来，这样反而多消耗一次直飞。
因此从 u 到 v（u < v）的最短路径，坐标一定是严格递增的。

第二个，题目只问路径数是不是 2。
路径数一旦到 3，后面不管怎么走都不可能再变回 2，所有大于 2 的值完全可以统一记成 3。

三、解法一：暴力 DP（24 分）

思路：最短路的坐标严格递增，所以可以按区间做动态规划，枚举右端点 r、左端点 l、上一跳 k。

step[u][v] 记 u 到 v 的最少飞行次数，path[u][v] 记对应的最短路径条数。

枚举 v 的上一跳 k，k 要满足 x_v - x_k <= d。
转移就是取最小的 step[u][k] + 1，把所有达到最小值的 path[u][k] 加起来。

复杂度 O(n^3)。

得分：24 分。
前 6 个测试点 N <= 300 能过。
N <= 5000 开始就超时。

核心代码如下：

ll ans = 0;
vector<vector<ll>> dpStep(n, vector<ll>(n, INFL / 2));
vector<vector<ll>> dpPath(n, vector<ll>(n, 0));
for (int r = 0; r < n; r++) {
  dpStep[r][r] = 0;
  dpPath[r][r] = 1;  // 自己到自己，0 次飞行，1 条路径
  for (int l = 0; l < r; l++) {
    for (int k = r - 1; k >= l; k--) {
      if (nums[r] - nums[k] > d) break;
      if (dpStep[l][k] + 1 < dpStep[l][r]) {
        dpStep[l][r] = dpStep[l][k] + 1;
        dpPath[l][r] = dpPath[l][k];
      } else if (dpStep[l][k] + 1 == dpStep[l][r]) {
        dpPath[l][r] += dpPath[l][k];
      }
    }
    if (dpPath[l][r] == 2) ans++;
  }
}
printf("%lld\n", ans);

四、解法二：利用 step 单调性，两次二分（24 分）

思路：二分。

枚举 v 的上一跳 k 时，k 越大离 l 越远，最少飞行次数只可增减。
所以固定 l 时 step[l][k] 关于 k 单调不减。

于是最优的上一跳，一定是 r 向左能直飞到的最靠左那个点，记作 minKFirst。
由于只增不减，意味着还有连续相等的点。
与它 step 相同的 k 必然也连成一段，右端记作 minKLast。
路径数就是这一段上 path[l][k] 的和。

minKFirst 是第一个满足 x_k >= x_r - d 的位置，直接 lower_bound。
复杂度 O(log n)。

用 upper_bound 找第一个大于 step[l][minKFirst] 的位置，然后再减一，就是最后一个与 minKLast 值相等的位置。复杂度也是 O(log n)。

区间逐项求和，复杂度会退回到 O(n)。
所以需要维护前缀和 dpPathSum[l][*]，即 path[l][*] 的前缀和。
区间和复杂度： O(1)。

对于每个 (l, r)，状态转移的复杂度是 O(log n)。
总复杂度为 O(n^2 log n)。
得分：24 分。

核心代码如下：

for (int r = 0; r < n; r++) {
  dpStep[r][r] = 0;
  dpPath[r][r] = dpPathSum[r][r] = 1;
  if (r > 0 && nums[r] - nums[r - 1] > d) continue;  // 不可达
  for (int l = r - 1; l >= 0; l--) {
    if (dpPath[l][r - 1] == 0) break;
    int minKFirst = lower_bound(nums.begin() + l, nums.end(), nums[r] - d) - nums.begin();
    ll minStep = dpStep[l][minKFirst];
    int minKLast = upper_bound(dpStep[l].begin() + minKFirst, dpStep[l].begin() + r, minStep)
                   - dpStep[l].begin() - 1;
    dpStep[l][r] = minStep + 1;
    dpPath[l][r] = dpPathSum[l][minKLast] - (minKFirst ? dpPathSum[l][minKFirst - 1] : 0);
    dpPathSum[l][r] = dpPath[l][r] + dpPathSum[l][r - 1];
    if (dpPath[l][r] == 2) ans++;
  }
}

五、解法三：双指针消掉一个二分（24 分）

思路：双指针可以代替二分。

固定 r 让 l 从 r-1 递减，x_r - x_l 越来越大。
只要它还没超过 d，minKFirst 就等于 l；
一旦超过，往后的 l 只会更远，minKFirst 就再也不动了。
这种单调性用一个游标就能维护，不需要每次二分。

找 minKLast 的二分消不掉。
minKLast 由 step[l][minKFirst] 决定，l 减小时这个值可能不变也可能变大，minKLast 可能变大也可能变小，没有单调性，只能继续二分。

复杂度 O(n^2 log n)。
得分 24 分。

核心代码如下：

for (int r = 0; r < n; r++) {
  dpStep[r][r] = 0;
  dpPath[r][r] = dpPathSum[r][r] = 1;
  int minKFirst = r - 1;
  for (int l = r - 1; l >= 0; l--) {
    if (dpPath[l][r - 1] == 0) break;
    if (nums[r] - nums[l] <= d) minKFirst = l;  // 游标只减不增
    ll minStep = dpStep[l][minKFirst];
    int minKLast = upper_bound(dpStep[l].begin() + minKFirst, dpStep[l].begin() + r, minStep)
                   - dpStep[l].begin() - 1;
    dpStep[l][r] = minStep + 1;
    dpPath[l][r] = dpPathSum[l][minKLast] - (minKFirst ? dpPathSum[l][minKFirst - 1] : 0);
    dpPathSum[l][r] = dpPath[l][r] + dpPathSum[l][r - 1];
    if (dpPath[l][r] == 2) ans++;
  }
}

六、解法四：路径数剪枝（40 分）

思路：答案只关心路径数是不是 2，大于 2 的肯定都不是答案。

从 minKFirst 开始往后累加 path[l][k]，超过 3 就肯定没有答案。
每个 path 至少是 1，最多加三个位置。
这样 minKLast 不用二分，前缀和也不用维护，O(1) 均摊就能算出 path[l][r]。

复杂度 O(n^2)。得分 40 分。

核心代码如下：

ll minStep = dpStep[l][minKFirst];
ll sum = 0;
int minKLast = minKFirst;
while (minKLast < r && dpStep[l][minKLast] == minStep && sum <= 2) {
  sum += dpPath[l][minKLast];
  minKLast++;
}
dpStep[l][r] = minStep + 1;
dpPath[l][r] = min(sum, 3LL);
if (dpPath[l][r] == 2) ans++;

八、解法六：性质 A，等差数列（48 分）

思路：性质 A 保证岛屿坐标成等差数列，可以直接推出公式。

先看一个答案长什么样。
假设 (u, v) 的最短路径要走 2 步，中间点是 k。
k 既要满足 u 一步能飞到，也要满足 k 一步能飞到 v。
前者给 k <= RD[u]（u 一步能到的最靠右点），后者给 k >= LD[v]（能一步飞到 v 的最靠左点）。
两条路径，等价于 [LD[v], RD[u]] 这个交集里恰好只有两个岛屿，换成坐标就是 [x_v - d, x_u + d] 这一段。
所以，需要先判断等差数列是否满足这个条件。

设公差为 dis，一跳最多跨 cnt = d / dis 个间隔。
于是按下标算 RD[u] = u + cnt，LD[v] = v - cnt。
中间点个数是 RD[u] - LD[v] + 1 = u - v + 2cnt + 1。
令它等于 2，得到 v - u = 2cnt - 1，这是一个固定间距。

所有间距为 2cnt - 1 的二元组的最短路都有两个路径。
这样的二元组工 n - (2cnt - 1)个。

复杂度 O(1)。
得分 48 分。

核心代码如下：

ll SolverA() {
  ll dis = nums[1] - nums[0];
  if (dis * 2 > d) return 0;
  ll cnt = d / dis;         // 一跳最多跨 cnt 个间隔
  ll minCnt = 2 * cnt;
  if (n < minCnt) return 0;
  return n - minCnt + 1;
}

九、解法七：性质 B，任意两点最多两跳（56 分）

思路：性质 B 说存在一座岛屿能直飞到任意其他岛屿。
它到首尾的距离都不超过 d，所以 x_n - x_1 <= 2d。

这时任意两座岛屿之间最多两跳可达，最短路只可能是 1 跳或 2 跳。
1 跳的路径只有一条，所以答案只能是 2 跳。

先找出所有能同时直飞到首尾的岛屿，左右边界记作 L、R。
显然，这样的岛屿只能有2个，否则最短路路径上就会大于 2。

然后枚举左端点 u，二分出右侧最远可到达点 RD[u]。由于要覆盖两个点，所以还需要覆盖 j=RD[u]-1，得到这个点可以覆盖的最远距离 RD[j]。

同时，还需要保证只覆盖两个点，不能覆盖三个点。
所以，再往前的一个点 k可以到达的区域 RD[k]，都不能是答案。

由此计算出答案 RD[j] - RD[k]。

复杂度 O(n log n)，得分 56 分。
第 13、14 组靠这个特判拿下。

核心代码如下：

int L = n, R = 0;
for (int i = 0; i < n; i++) {
  if (nums[i] - nums.front() <= d && nums.back() - nums[i] <= d) {
    L = min(L, i);
    R = max(R, i);
  }
}
if (R - L + 1 > 2) return 0;

ll ans = 0;
for (int i = 0; i < n; i++) {
  int Ri = upper_bound(nums.begin() + i, nums.end(), nums[i] + d) - nums.begin();
  if (Ri - L > 2) break;  // 后续都不会有答案
  if (Ri - i < 3) continue;
  int j = Ri - 2;
  int Rj = upper_bound(nums.begin() + j, nums.end(), nums[j] + d) - nums.begin();
  int k = Ri - 3;
  int Rk = upper_bound(nums.begin() + k, nums.end(), nums[k] + d) - nums.begin();
  ans += Rj - Rk;
}

十、解法八：贪心构造 + 二分（100 分）

思路：枚举。

根据性质 A 和性质 B，已经可以看出来，要构造恰好有2条最短路路径的图，这两条路径必须是相邻的点。

如果我们枚举这两个关键点，就可以构造出满足要求的长度为 3 的双路径最短路。

如下图，枚举点是 (L,R)，右侧最后一个答案是 RD[L]，往前，直到 RD[L-1]+1 都是满足的。
也就是右侧 (RD[L-1], RD[L]] 区间内的点都可以形成长度为 3 的双路径最短路。

同理，左侧也可以计算出同样的满足双路径的区间。
左右区间大小相差，就是所有长度为 3 的双路径最短路。

路径长度如果要再增加，这些路径就必须是只有一跳的，不能产生冗余的路径。
故，其他边必须选择最远的端点，否则就会产生冗余路径，从而得到大于2的路径。

如下图，(L,R)的下一跳必须选择最远的可到达的 P，然后 P 的下一跳可选择就多了。
与前面的类似，需要 P 可到达，但是 P-1 不可到达。
共有 RD[P] - RD[P-1] 种情况。

一次递推，对于确定的 (L,R)，右侧的答案也是确定的，分别如下

第一跳：RD[L] - RD[L-1]
第二跳：RD[P] - RD[P-1], P=RD[R]
第三跳: RD[Q] - RD[Q-1], Q=RD[P]=RD[RD[R]]
...

如果从后到前算，就可以利用后缀和，把每一跳的答案都计算出来。
复杂度：O(n log(n))

下面几段代码里，nums 存坐标，ans 累加答案，四个 dp 数组初值都是 0。
核心代码如下：

// 右侧：从右往左，把「延伸 0 跳、1 跳…」累加进 dpRightSum
for (int R = n - 2; R > 0; R--) {
  int RRightMax = upper_bound(nums.begin() + R, nums.end(), nums[R] + d) - nums.begin() - 1;
  if (RRightMax == R) continue;
  const int L = R - 1;
  if (nums[L] + d >= nums[RRightMax]) continue;  // 不存在下一跳
  int LRightMin = upper_bound(nums.begin() + L, nums.end(), nums[L] + d) - nums.begin();
  LRightMin = max(LRightMin, R + 1);
  if (LRightMin <= RRightMax) dpRightMost[R] = RRightMax - LRightMin + 1;
  dpRightSum[R] = dpRightMost[R] + dpRightSum[RRightMax];
}

// 左侧：从左往右，对称处理
for (int L = 1; L < n - 1; L++) {
  int LLeftMin = lower_bound(nums.begin(), nums.end(), nums[L] - d) - nums.begin();
  if (LLeftMin == L) continue;
  const int R = L + 1;
  if (nums[R] - d <= nums[LLeftMin]) continue;
  int RLeftMin = lower_bound(nums.begin(), nums.end(), nums[R] - d) - nums.begin() - 1;
  RLeftMin = min(RLeftMin, L - 1);
  if (LLeftMin <= RLeftMin) dpLeftMost[L] = RLeftMin - LLeftMin + 1;
  dpLeftSum[L] = dpLeftMost[L] + dpLeftSum[LLeftMin];
}

// 枚举核心的相邻对，左右相乘
for (int L = 1, R = 2; R + 1 < n; L++, R++) {
  int LRightMax = upper_bound(nums.begin() + L, nums.end(), nums[L] + d) - nums.begin() - 1;
  int RRightMax = upper_bound(nums.begin() + R, nums.end(), nums[R] + d) - nums.begin() - 1;
  if (LRightMax <= R || nums[LRightMax] - d <= nums[L - 1]) continue;
  int RLeftMin = lower_bound(nums.begin(), nums.end(), nums[R] - d) - nums.begin();
  int LLeftMin = lower_bound(nums.begin(), nums.end(), nums[L] - d) - nums.begin();
  if (RLeftMin >= L || nums[RLeftMin] + d >= nums[R + 1]) continue;
  ll leftSum = dpLeftMost[R];
  if (LLeftMin == RLeftMin) leftSum += dpLeftSum[LLeftMin];
  ll rightSum = dpRightMost[L];
  if (RRightMax == LRightMax) rightSum += dpRightSum[LRightMax];
  ans += leftSum * rightSum;
}

十一、解法九：双指针预处理（100 分，推荐）

思路：LD 和 RD 不用逐个二分，一次扫就能全算出来。

如上图，随着 i 的增加，LD 和 RD 也都是单调不减的。
所以这个可以使用双指针来代替二分。

总复杂度 O(n)。
得分 100 分。

核心代码如下：

vector<ll> LD(n, -1), RD(n, -1);
for (int i = 0, L = 0, R = 0; i < n; i++) {
  while (L >= 0 && nums[i] - nums[L] > d) L++;
  while (R < n && nums[R] - nums[i] <= d) R++;
  LD[i] = L;
  RD[i] = R - 1;
}

// 右侧递推，LD/RD 直接查表，不再二分
for (int R = n - 2; R > 0; R--) {
  int RRightMax = RD[R];
  if (RRightMax == R) continue;
  const int L = R - 1;
  if (nums[L] + d >= nums[RRightMax]) continue;
  int LRightMin = RD[L] + 1;
  LRightMin = max(LRightMin, R + 1);  // 有可能左边很远，需要保证在 R 右侧
  if (LRightMin <= RRightMax) dpRightMost[R] = RRightMax - LRightMin + 1;
  dpRightSum[R] = dpRightMost[R] + dpRightSum[RRightMax];
}

// 左侧递推
for (int L = 1; L < n - 1; L++) {
  int LLeftMin = LD[L];
  if (LLeftMin == L) continue;
  const int R = L + 1;
  if (nums[R] - d <= nums[LLeftMin]) continue;
  int RLeftMin = LD[R] - 1;
  RLeftMin = min(RLeftMin, L - 1);  // 有可能右边很远，需要保证在 L 左侧
  if (LLeftMin <= RLeftMin) dpLeftMost[L] = RLeftMin - LLeftMin + 1;
  dpLeftSum[L] = dpLeftMost[L] + dpLeftSum[LLeftMin];
}

// 枚举核心的相邻对
for (int L = 1, R = 2; R + 1 < n; L++, R++) {
  if (RD[L] <= R || nums[RD[L]] - d <= nums[L - 1]) continue;
  if (LD[R] >= L || nums[LD[R]] + d >= nums[R + 1]) continue;
  ll leftSum = dpLeftMost[R];
  if (LD[L] == LD[R]) leftSum += dpLeftSum[LD[L]];
  ll rightSum = dpRightMost[L];
  if (RD[R] == RD[L]) rightSum += dpRightSum[RD[L]];
  ans += leftSum * rightSum;
}

十二、总结

这道题的难点不在代码，在于把「恰好两条最短路」这个条件想清楚。

最暴力的三维 DP 拿 24 分。
发现 step 单调后可以二分，但二维状态内存爆炸了，还是 24 分。
把路径数封顶到 3，消掉一次二分，做到 O(n^2)，40 分。

性质 A 是成等差数列，公式直接计算答案，得到 48 分。
性质 B 是存在一座岛屿能直飞到任意其他岛屿，找到一些规律，得到 56 分。

两个性质结合起来，发现正解：中间一对相邻点提供两条路径，左右每一跳都唯一且必须取最长一跳，左右独立所以可以相乘。

最后把 LD、RD 从二分换成双指针，从 O(n log n) 降到 O(n)，满分。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code

本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。

CSP-S 2026 C题迁徙题解（9个解法）

零、背景

一、题目

二、算法分析

三、解法一：暴力 DP（24 分）

四、解法二：利用 step 单调性，两次二分（24 分）

五、解法三：双指针消掉一个二分（24 分）

六、解法四：路径数剪枝（40 分）

八、解法六：性质 A，等差数列（48 分）

九、解法七：性质 B，任意两点最多两跳（56 分）

十、解法八：贪心构造 + 二分（100 分）

十一、解法九：双指针预处理（100 分，推荐）

十二、总结

关注公众号,接收最新消息

置顶文章

目录

CSP-S 2026 C题 迁徙 题解（9个解法）

零、背景

一、题目

二、算法分析

三、解法一：暴力 DP（24 分）

四、解法二：利用 step 单调性，两次二分（24 分）

五、解法三：双指针消掉一个二分（24 分）

六、解法四：路径数剪枝（40 分）

八、解法六：性质 A，等差数列（48 分）

九、解法七：性质 B，任意两点最多两跳（56 分）

十、解法八：贪心构造 + 二分（100 分）

十一、解法九：双指针预处理（100 分，推荐）

十二、总结

关注公众号,接收最新消息

置顶文章

目录

CSP-S 2026 C题迁徙题解（9个解法）