P3509 [POI2010]ZAB-Frog 题解
TonyYin
·
·
题解
题意
数轴上有 n 个点，坐标分别为 p_1, p_2, \cdots, p_n 在这些点上按照某些规则跳。
规则是：每次向距当前点第 k 小的点跳，如果有相同距离则向下标较小的跳；
求从每个点出发跳了 m 次后在哪里.
## $\rm{Part}$ $\rm{1}
首先，注意到 k 是固定的，所以可以先预处理，对于每个点 i，跳一次之后的位置\operatorname{next}_i.
这部分使用单调队列处理。
我们知道，对于每个点，距离其前 k 小的点分布在其两侧，可以用一段完整区间覆盖。
所以我们想到，当单调队列枚举到 i 时，单调队列中维护的区间，就是覆盖距离 i 前 k 小的点的区间。这样找到区间内距离最大的点就是我们要求的 \operatorname{next}_i，下面考虑考虑如何维护。
对于区间 [l, r] 中的一个点 i，距离他最远的点一定是 l 和 r 这两个点中的一个。如果 r+1 到 i 的距离小于了 l 到 i 的距离，说明区间应当向右滑动，如下图，n=7, k=3 的例子：
绿色区间是距离点 C 前 k 小的点，考虑距离点 D 前 k 小的点。
又因为 $\rm{Dis(D, E)<Dis(D, B)}$，所以区间要再右移一个单位，变成：
至此，我们能够求出每个点，距离其第 $k$ 小的点的下标。
```cpp
head = 1, tail = k + 1;
for(int i = 1; i <= n; i++) {
while(tail + 1 <= n && x[tail + 1] - x[i] < x[i] - x[head]) head++, tail++;
if(x[tail] - x[i] > x[i] - x[head]) nxt[i] = tail;
else nxt[i] = head;
}
```
## $\rm{Part}$ $\rm{2}
题目要求跳 m 次之后的答案，我们使用类似快速幂的方法，倍增处理即可。
for(int i = 1; i <= n; i++) pos[i] = i;
while(m) {
if(m & 1) {
for(int i = 1; i <= n; i++) pos[i] = next[pos[i]];
}
m >>= 1;
for(int i = 1; i <= n; i++) next2[i] = next[i];
for(int i = 1; i <= n; i++) next[i] = next2[next2[i]];
}
代码
最终代码在上面两部分的基础上加上 \rm{I/O} 即可。