P9447 [ICPC 2021 WF] Spider Walk 题解

zrl123456 · 2025-11-20 21:15:05 · 题解

:::::info[闲话] 尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。 ::::: :::::info[题目基本信息] 考察：STL，整体转移（省选/NOI-）。
题目简介：
有 n 条直线和 m 个桥，第 i 个桥连接了 (t_i,d_i) 和 (t_i\bmod n+1,d_i)，初始时你在 (k,0)，你可以不花费任何代价地向右行走任意实数长度，直到你的位置是一座桥的端点，这时你必须沿着桥走到另一端，但是在一开始的时候你可以花费 1 的代价任意钦定 t 和 d 建一座桥（t\in[1,n]，同时 d 可为任意实数），问最终抵达 (s,+\infty) 最小代价，你需要对于每一个 k 满足 k\in[1,n] 求解答案。
数据范围：

• 3\le n\le 2\times 10^5
• 1\le s\le n
• 0\le m\le 5\times 10^5
• \forall i\in[1,m],1\le d_i\le 10^9,1\le t_i\le n
• \forall i,j\in[1,m],i\ne j,d_i\ne d_j

  ::::: 首先 n 个起点 1 个终点看起来就很怪，我们把移动的过程倒过来变成 1 个起点 n 个终点看起来就很对了。
  存在 \Theta(nm) 的 01bfs 的暴力做法，但是对正解没有启发性，但是存在有启发性的 DP 做法。
  将桥按 d_i 降序排序，设 f_{i,j} 为考虑完前 i 个桥后位置 j 的答案，初始时 \forall i\in[1,n],f_{0,i}=\min(|s-i|,n-|s-i|)，考虑如何转移。
  看图（为方便画图我们断环为链的画）：
  
  这时我们要在 G 点和 H 点间建一座桥，首先先交换这两点的答案，然后：
  注意到 H 点和 I 点间差距大于等于 2 了，我们可以从 I 点建桥到达 H 点，这样答案会更小，那么我们就有了思路：

• 先交换两个建桥位置的答案。
• 再对这个序列更新减小答案，具体地，找到这个序列最小值然后向两侧更新，不断递归这个过程即可。

复杂度不重要，重要的是思想。
注意到两个相邻的数之间只能相差 -1,0 或 1，但是然后怎么办？
然后我们看刚刚的那两步：

• 交换建桥位置的答案，这个容易直接跑，接下来会产生相差的值不为 -1,0,1 的相邻数对，怎么办？
• 我们不妨以交换的位置的差分类讨论，当两数相等时交换没有影响，现在只剩后面的数比前面的数大 1 或小 1 的情况，这两种情况类似，可以互相轴对称得出，不妨以后面的数比前面的数大 1 讨论。
  如图，黑线是原来的答案构成的序列，红线是交换 B 点和 C 点后的答案序列，后面这一段被连续的拉下来一段（因为一直存在相差值超过 1 的相邻数对，直到 H 点）注意到中间这一段相邻数对前后都相差 1，所以我们可以考虑维护差分序列，同时维护序列中不为 1 的位置序列，这个可以使用 set 维护，更新差分序列时同时更新 set 即可。
  至于细节处理仔细分讨一下也能推出（但是一坨），需要根据建桥的两个位置以及后方第一个不是 1 的位置（或前方第一个不是 -1 的位置）分类讨论，讨论不清楚的话细节见代码。

这样我们就做完了这道题。

时间复杂度为 \Theta(n+m\log n)，空间复杂度为 \Theta(n+m)。

code