從左往右維護兩個指針l,r表示離i最近的k個點的區間，預處理出每個點出發的后繼，然后倍增。

?

#include<cstdio> typedef long long ll; const int N=1000010,BUF=20000000,OUT=8000000; int n,k,i,l=1,r,f[N],g[N],t[N],Outn[20],Outcnt;ll m,a[N];char Buf[BUF],*buf=Buf,Out[OUT],*ou=Out; inline ll read(){ll a=0;while(*buf<48)buf++;while(*buf>47)a=a*10+*buf++-48;return a;} inline void write(ll x){for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;while(Outcnt)*ou++=Outn[Outcnt--];*ou++=32; } int main(){fread(Buf,1,BUF,stdin),n=read(),k=read(),m=read();for(i=1;i<=n;a[i++]=read());for(r=f[t[1]=1]=k+1,i=2;i<=n;i++){while(r<n&&a[r+1]-a[i]<a[i]-a[l])l++,r++;f[i]=a[r]-a[i]>a[i]-a[l]?r:l,t[i]=i;}while(m){if(m&1){for(i=1;i<=n;i++)g[i]=f[t[i]];for(i=1;i<=n;i++)t[i]=g[i];}m>>=1;for(i=1;i<=n;i++)g[i]=f[f[i]];for(i=1;i<=n;i++)f[i]=g[i];}for(i=1;i<=n;i++)write(t[i]);return fwrite(Out,1,ou-Out-1,stdout),0; }

　　

?

轉載于:https://www.cnblogs.com/clrs97/p/4403143.html

總結

以上是生活随笔為你收集整理的BZOJ2093 : [Poi2010]Frog的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。