首页 > 代码库 > BZOJ 2093: [Poi2010]Frog
BZOJ 2093: [Poi2010]Frog
Description
从一个点到达与他距离第 \(k\) 小的点,问从每个点跳 \(m\) 次到达那个点.
Sol
队列+倍增.
保持队列里的元素个数为 \(k\) ,从前往后扫不难发现左右端点都是单调的.
求跳 \(m\) 次就是倍增了,滚一下数组.
Code
/************************************************************** Problem: 2093 User: BeiYu Language: C++ Result: Accepted Time:7256 ms Memory:20832 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; typedef long long LL;const int N = 1e6+50;const int M = 65; LL n,k,m,l,r,lm;LL a[N],pow2[M];int f[2][N],g[N]; inline LL in(LL x=0,char ch=getchar()) { while(ch>‘9‘ || ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; }int main() { n=in(),k=in(),m=in(),lm=log2(m)+1; for(int i=1;i<=n;i++) a[i]=in(); l=1,r=k+1; for(int i=1;i<=n;i++) { while(r<n && a[r+1]-a[i] < a[i]-a[l]) r++,l++; f[0][i]=(a[r]-a[i] > a[i]-a[l] ? r : l); } pow2[0]=1;for(int i=1;i<=lm;i++) pow2[i]=pow2[i-1]<<1; if(m&1) for(int i=1;i<=n;i++) g[i]=f[0][i]; else for(int i=1;i<=n;i++) g[i]=i; r=1; for(int j=1;j<=lm;j++) { for(int i=1;i<=n;i++) f[r][i]=f[r^1][f[r^1][i]]; if(m&pow2[j]) for(int i=1;i<=n;i++) g[i]=f[r][g[i]]; r^=1; } for(int i=1;i<=n;i++) printf("%d%c",g[i]," \n"[i==n]); return 0;}
BZOJ 2093: [Poi2010]Frog
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。