bzoj2093 Frog
2019-08-16 07:43:54来源:博客园 阅读 ()
bzoj2093 Frog
题目链接
思路
非常有趣的一道题。
先考虑如何找出第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;
}
原文链接:https://www.cnblogs.com/wxyww/p/bzoj2093.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- kuangbin专题专题四 Frogger POJ - 2253 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash