欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

bzoj2093 Frog

程序员文章站 2022-05-15 16:34:11
题目链接 思路 非常有趣的一道题。 先考虑如何找出第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;
}