傳送門

題目大意

坐標(biāo)軸上有$n$個(gè)坐標(biāo)，第$i$個(gè)坐標(biāo)是$x_i$，初始你有一個(gè)容量$V$，當(dāng)兩個(gè)給定的坐標(biāo)距離不超過(guò)$V$時(shí)，你可以從一個(gè)坐標(biāo)到達(dá)另一個(gè)坐標(biāo)，同時(shí)你還可以令$V=\lfloor \frac{V}{2}\rfloor$，并到達(dá)一個(gè)任意一個(gè)給定的坐標(biāo)。

求對(duì)于每一個(gè)點(diǎn)是否存在一種方案使得從這個(gè)點(diǎn)出法能夠到達(dá)每一個(gè)點(diǎn)至少一次。

?

題解

首先$V$的值只有$\log V$種，對(duì)于每一種取值，會(huì)有若干段下標(biāo)連續(xù)的坐標(biāo)可以互相到達(dá)，要求在每一層取一段使得所有坐標(biāo)都被覆蓋，題意即為在強(qiáng)制選第一層的某一段，是否存在合法方案。

考慮先預(yù)處理每一層每一個(gè)坐標(biāo)能到達(dá)的最左和最右的坐標(biāo)，再在忽略第一層的意義下將每一層是否被選中的狀態(tài)壓縮起來(lái)，求出用了某些層所能覆蓋的最長(zhǎng)前綴和后綴。

設(shè)某一選中的狀態(tài)集合為$K$,全集為$S$，$K$所能覆蓋的最長(zhǎng)前綴為$Pre_K$，最長(zhǎng)后綴為$Suf_K$。

枚舉$K$，對(duì)于每一個(gè)$Pre_K$，求出它所對(duì)應(yīng)的最長(zhǎng)的$Suf$即為$F_{Pre_K}$，這個(gè)用$Suf_{S-K}$更新即可，要考慮$F_i+1$可以更新$F_i$。

所以最后枚舉每一個(gè)坐標(biāo)$i$，找到它第一層所在的段的左右端點(diǎn)$L,R$，看$F_{L-1}$是否能覆蓋到$R$即可。

由于狀態(tài)數(shù)是$2^{\log_2 V}$，所以它是嚴(yán)格小于$V$的，所以最終復(fù)雜度為$O(n\log V+V)$。

?

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define M 200020 #define INF 1000001000 using namespace std; const int BS=1<<19;char BF[BS],OT[BS],*SZ=OT,*HD,*TL; const char *ED=OT+BS-1; int Top; char Getchar(){if(HD==TL)TL=(HD=BF)+fread(BF,1,BS,stdin);return *HD++;} void flush(){fwrite(OT,1,SZ-OT,stdout);} void Putc(char c){*SZ++ =c;if(SZ==ED) flush(),SZ=OT;} int read(){int nm=0,fh=1; char cw=Getchar();for(;!isdigit(cw);cw=Getchar()) if(cw=='-') fh=-fh;for(;isdigit(cw);cw=Getchar()) nm=nm*10+(cw-'0');return nm*fh; } void TK(bool x){if(x) Putc('P'); else Putc('I'),Putc('m'),Putc('p'); Putc('o');Putc('s'),Putc('s'),Putc('i'),Putc('b'),Putc('l'),Putc('e'),Putc('\n'); } int tot,n,m,pos[M],L[M][21],R[M][21],V[40],rt; int RF[M<<3],LF[M<<3],G[M],D[M],MAXN; int main(){n=read(),m=read();for(int i=1;i<=n;i++) pos[i]=read(),D[i]=pos[i]-pos[i-1],G[i]=-(INF<<1);while(m) V[tot++]=m,m>>=1; tot++;for(int k=0;k<tot;k++){for(int i=1;i<=n;i++){R[i][k]=max(R[i-1][k]-1,1);while(i+R[i][k]<=n&&D[i+R[i][k]]<=V[k]) R[i][k]++;}for(int i=n;i;i--){L[i][k]=max(L[i+1][k]-1,1);while(i-L[i][k]>0&&D[i-L[i][k]+1]<=V[k]) L[i][k]++;}} MAXN=(1<<tot);for(int i=2;i<MAXN;i+=2){for(int k=1;k<tot;k++){int w=(1<<k); if(!(i&w)) continue;LF[i]=max(LF[i],LF[i^w]+R[LF[i^w]+1][k]);RF[i]=max(RF[i],RF[i^w]+L[n-RF[i^w]][k]);} LF[i]=min(LF[i],n),RF[i]=min(RF[i],n);}for(int k=0;k<MAXN;k+=2) G[LF[k]]=max(G[LF[k]],RF[(MAXN-2)^k]);for(int i=n-1;i>=0;i--) G[i]=max(G[i],G[i+1]);for(int i=1;i<=n;i++) TK(G[i-L[i][0]]+R[i][0]+i-1>=n); flush();return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/OYJason/p/9805019.html

總結(jié)

以上是生活随笔為你收集整理的Agc012_E Camel and Oases的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。