c/c++语言开发共享bzoj2093 Frog

题目链接 思路 非常有趣的一道题。 先考虑如何找出第K远的位置。 因为给出的序列是单调的,所以对于位置$i$的前$K$远位置肯定是一个包含位置$i$的长度为$k+1$的区间。我们用$l$表示这个区间的左端点,$r$表示这个区间的右端点。那么当$i+1$时,$l$和$r$都只会往右挪。而且往右挪的条件 …

题目链接

思路

非常有趣的一道题。
先考虑如何找出第k远的位置。
因为给出的序列是单调的,所以对于位置(i)的前(k)远位置肯定是一个包含位置(i)的长度为(k+1)的区间。我们用(l)表示这个区间的左端点,(r)表示这个区间的右端点。那么当(i+1)时,(l)(r)都只会往右挪。而且往右挪的条件是第(r+1)个点与(i+1)的距离比第(l)个点与第(i+1)个点的距离小。
这样就可以找出每个位置的第k远位置。然后就得到了一个置换。
(m)次也就相当于把这个置换循环(m)次。依据倍增的思想只要(nlogm)的复杂度就可以完成了。

代码

#include<cstdio> #include<iostream> using namespace std; typedef long long ll; const int n = 1000000 + 100;  ll read() {     ll x = 0,f = 1;     char c = getchar();     while(c < '0' || c > '9') {         if(c == '-') f = -1;         c = getchar();     }     while(c <= '9' && c >= '0') {         x = x * 10 + c - '0';         c = getchar();     }     return x * f; } ll a[n]; int b[n],n,k; ll m; int tmp[n],c[n]; void calc() {     for(int i = 1;i <= n;++i) c[i] = tmp[i];     for(int i = 1;i <= n;++i) tmp[i] = c[tmp[i]]; } int main() {     n = read(),k = read(),m = read();     for(int i = 1;i <= n;++i) a[i] = read();     int l = 1,r = min(k + 1,n);     for(int i = 1;i <= n;++i) {         while((l < i && r < n && a[r + 1] - a[i] < a[i] - a[l]) || r < i) {             ++l;++r;         }         if(a[i] - a[l] >= a[r] - a[i]) tmp[i] = l;         else tmp[i] = r;         b[i] = i;     }     for(;m;m >>= 1,calc()) {         if(m & 1) for(int i = 1;i <= n;++i) b[i] = tmp[b[i]];     }          for(int i = 1;i <= n;++i)      printf("%d ",b[i]);     return 0; } 
www.ctvol.com true Article c/c++语言开发共享bzoj2093 Frog

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/602868.html

(0)
上一篇 2021年5月11日 下午2:14
下一篇 2021年5月11日 下午2:18

精彩推荐