题目大意:有$n$个点,每个点有一个距离(从小到大给出),从第$i$个点跳一次,会跳到距离第$i$个点第$k$远的点上(若有两个点都是第$k$远,就跳到编号小的上)。问对于从每个点开始跳,跳$m$次,最后会到哪个点
题解:难点主要在处理第$k$远上(跳只需要一个类似快速幂的东西就好了,也就是倍增)。
可以维护两个指针,一个是$l$,一个是$r(r=l+k)$,且到$i$这个点时$lleqslant ileqslant r$。刚开始时$l=1,r=k+1$,若$p_{r+1}-p_i<p_i-p_l(p_i为第i个点的位置)$,就把$l$和$r$都加一
则第$i$个点跳到的点就是$l,r$中较远的一个,若相同就是$l$(当$r==n$时就是$l$)。
卡点:无
C++ Code:
#include <cstdio> #define maxn 100010 int n, k, l, r; long long m; struct _ { int to[maxn]; _ operator * (const _& rhs) { _ res; for (int i = 1; i <= n; i++) { res.to[i] = rhs.to[to[i]]; } return res; } } base, ans; long long p[maxn]; int main() { scanf("%d%d%lld", &n, &k, &m); for (int i = 1; i <= n; i++) scanf("%lld", p + i); l = 1, r = k + 1; for (int i = 1; i <= n; i++) { ans.to[i] = i; while (r < n && p[i] - p[l] > p[r + 1] - p[i]) l++, r++; if (p[i] - p[l] >= p[r] - p[i]) base.to[i] = l; else base.to[i] = r; } for (; m; m >>= 1, base = base * base) if (m & 1) ans = ans * base; for (int i = 1; i <= n; i++) printf("%d ", ans.to[i]); puts(""); return 0; }