思路

非常有趣的一道题。

先考虑如何找出第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;

}

巴特西

bzoj2093 Frog

思路

代码

最新文章

热门文章