題目大意：一排點(diǎn)，兩點(diǎn)間有距離。?初始你有一個(gè)行走值$v$，如果相鄰兩點(diǎn)距離不超過$v$你可以自由在這兩點(diǎn)行走。?
當(dāng)$v$大于$0$時(shí)，你可以選擇某一時(shí)刻突然飛到任意點(diǎn)，這樣做后$v$會(huì)減半（下取整）。?問從每個(gè)位置初始出發(fā)能否到達(dá)所有位置。

點(diǎn)的數(shù)量$≤2*10^5$，$v≤2*10^5$，$|兩點(diǎn)距離|≤10^9$。

?

我們令$l[i][j]$表示從$i$出發(fā)，一路往左走，經(jīng)過所有長度不超過$v>>j$（此處的$>>$表示右移，以下都是）的邊，能走到最左的點(diǎn)的編號(hào)。

令$r[i][j]$表示從$i$出發(fā)，一路往右走，經(jīng)過所有長度不超過$v>>j$的邊，能走到最右的點(diǎn)的編號(hào)。

令$n$表示點(diǎn)的數(shù)量，$m=\lceil log_2v\rceil$。

我們不難得出：從$u$號(hào)點(diǎn)出發(fā)，是否可以遍歷完所有點(diǎn)的判斷條件，可以轉(zhuǎn)化為：

是否可以將點(diǎn)集分成$m+1$個(gè)塊，且第$i$（從$0$到$m$）個(gè)塊內(nèi)邊的長度均不超過$v>>i$，且第$u$號(hào)點(diǎn)需要在第$0$個(gè)塊內(nèi)。

?

那么，對(duì)于$[1,2^m)$中的每一個(gè)$i$（$i$是一個(gè)二進(jìn)制狀態(tài)，$i$的第$j$（$j$從$1$到$m$）位為$1$表示選擇了圖中第$j$個(gè)塊）

求一個(gè)最大的$f[i]$，滿足區(qū)間$[1,f[i]]$中的點(diǎn)能分成由狀態(tài)i表示的若干個(gè)塊。

同理，求一個(gè)最小的$g[i]$，滿足區(qū)間$[g[i],n]$中的點(diǎn)能分成由狀態(tài)i表示的若干個(gè)塊。

求這個(gè)可以通過l和r的值+狀壓$dp$實(shí)現(xiàn)，時(shí)間復(fù)雜度是$O(v\ log\ v)$。

我們令$o=2^m-2$。

我們發(fā)現(xiàn)，若存在$i$，使得$r[f[i]][0]>=l[g[o$^$i]][0]$，那么從區(qū)間$[\ l[g[o$^$i]][0]\ ,\ r[f[i]][0]\ ]$中出發(fā)的點(diǎn)，顯然可以遍歷玩所有點(diǎn)。

我們可以$O(1)$打上一個(gè)標(biāo)記，求答案的時(shí)候$O(n)$掃一遍，判斷某個(gè)點(diǎn)是否被打了標(biāo)記即可。

總時(shí)間復(fù)雜度：$O(n\ log\ v+v\ log\ v)$。

1 #include<bits/stdc++.h> 2 #define M 400005 3 #define YXQAK printf("Possible\n") 4 #define XFZBL printf("Impossible\n"); 5 using namespace std; 6 7 int a[M]={0},n,m,v,l[20][M]={0},r[20][M]={0}; 8 int f[M]={0},g[M]={0},p[M]={0}; 9 10 int main(){ 11 scanf("%d%d",&n,&v); 12 for(int i=1;i<=n;i++) scanf("%d",a+i); 13 sort(a+1,a+n+1); 14 for(int j=0,V=v;V;j++,V>>=1){ 15 m=max(m,j); 16 for(int i=1;i<=n;i++){ 17 int I=i+1; 18 while(I<=n&&a[I]-a[I-1]<=V) I++; 19 I--; 20 for(int ii=i;ii<=I;ii++) 21 l[j][ii]=i,r[j][ii]=I; 22 i=I; 23 } 24 } 25 m++; 26 for(int i=1;i<=n;i++) l[m][i]=r[m][i]=i; 27 for(int i=0;i<(1<<m);i++) g[i]=n; f[0]=1; 28 for(int i=1;i<(1<<m);i++){ 29 int now=1; 30 for(int j=m-1;~j;j--) 31 if((1<<j)&i) 32 f[i]=max(f[i],r[j+1][f[i^(1<<j)]]+1); 33 34 now=n; 35 for(int j=m-1;~j;j--) 36 if((1<<j)&i) 37 g[i]=min(g[i],l[j+1][g[i^(1<<j)]]-1); 38 } 39 40 for(int i=0;i<(1<<m);i++){ 41 if(r[0][f[i]]+1>=l[0][g[(1<<m)-i-1]]) 42 p[l[0][g[(1<<m)-i-1]]]++,p[r[0][f[i]]+1]--; 43 } 44 for(int i=1;i<=n;i++){ 45 p[i]+=p[i-1]; 46 if(p[i]) YXQAK; 47 else XFZBL; 48 } 49 }

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

總結(jié)

以上是生活随笔為你收集整理的【AGC012E】 Camel and Oases ST表+状压dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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