題意：

有一個(gè)駱駝，n個(gè)綠洲遍布在數(shù)軸上，第i個(gè)綠洲的坐標(biāo)為x[i]，保證x[i]單增。駱駝的駝峰有體積初始值V。當(dāng)駝峰的體積變?yōu)関的時(shí)候，駝峰中至多只能夠存儲(chǔ)v L的水。駱駝希望走完所有的綠洲，并且可以向下面這樣來(lái)走：
1.走距離d，消耗駝峰中d L的水，但是駝峰的體積不會(huì)減少。任意時(shí)候駝峰中的水的體積均不能夠?yàn)樨?fù)數(shù)；
2.跳躍到任意一個(gè)位置，消耗完所有的水，并且讓駝峰的體積變?yōu)関/2。該操作在v=0的時(shí)候是不能夠進(jìn)行的。
駱駝能夠在綠洲將水補(bǔ)滿至v。且一個(gè)綠洲可以多次訪問(wèn)并進(jìn)行補(bǔ)給。最后要求你輸出從每個(gè)位置出發(fā)，能否走完所有的綠洲。

數(shù)據(jù)范圍：

N,V<=2*1e5 ,-1e9<=x[i]<=1e9 ,且x是單增的。

思路：

首先看完題目，我們可以發(fā)現(xiàn)v/2這個(gè)操作是十分玄學(xué)的。這意味著只會(huì)減少log(V)+1次，就不能夠再進(jìn)行任何的移動(dòng)了。也說(shuō)明了v的取值只會(huì)有l(wèi)og(V)+2種，這個(gè)數(shù)量級(jí)是很小的。
那么對(duì)于某一個(gè)v而言，駱駝能夠在一些連續(xù)的綠洲之間任意的穿梭，也就形成了一些線段。具體而言就是假如說(shuō)x[i+1]-x[i]<=v，那么這兩個(gè)綠洲就是聯(lián)通的，就可以讓i和i+1處于一條線段中。我們可以發(fā)現(xiàn)，當(dāng)v從V變換到0的時(shí)候，每一條線段的長(zhǎng)度是在逐漸變短的，而線段的數(shù)量在逐漸增多。也就是說(shuō)，v越小，駱駝的移動(dòng)能力越差。現(xiàn)在這個(gè)問(wèn)題就變成了強(qiáng)迫你選擇了第一層（也就是v=V的那一層）中的某一條線段，在剩下的每一層當(dāng)中，選出至多一條線段，能否存在一種方式使得最后選出來(lái)的所有的線段能夠覆蓋完所有的綠洲。
對(duì)于這個(gè)問(wèn)題而言，瞬間就簡(jiǎn)化了不少。可以定義f1[state]，表示在選擇state（第i位為0表示第i層沒(méi)有選擇線段，第i位為1表示第i層選擇了一條線段）的時(shí)候，（線段從最左邊開始選）能夠覆蓋完全的最靠右的位置；定義f2[state]，表示在選擇state的時(shí)候，（線段從最右邊開始選）能夠覆蓋完全的最靠左的位置。最后再掃一遍第一層中的所有的線段，表示強(qiáng)行選擇其中的某一條線段，然后找是否有一個(gè)state，滿足第0位不為1（第一層已經(jīng)被確定了），且f1[state]，f2[全集-state-1]，加上這條線段，使得能夠覆蓋完所有的綠洲。
這樣子看上去似乎問(wèn)題已經(jīng)解決了，但是當(dāng)V奇小的時(shí)候，第一層最壞可能有n條線段（一個(gè)點(diǎn)一條），然后就變成了\(O(n2^{log_n})=O(n^2)\)的狀態(tài)。仔細(xì)分析之后，我們可以發(fā)現(xiàn)，假如第一層的線段數(shù)量大于了logV+2，那么由于接下來(lái)的線段只會(huì)越來(lái)越短并且越來(lái)越多，就算是選擇第一層的所有線段也需要>logV+2條線段，而一共才能夠選擇log(V)+2條線段線段，那就顯然不可能有解了。全部輸出Impossible即可。
這樣子就變?yōu)榱薕(logV * n)的時(shí)間復(fù)雜度了。

代碼：

#include<cstdio> #include<cstring> #include<algorithm> #define MAXN 1000000 #define INF 2000000000 using namespace std; int n,V,x[MAXN+5]; int cnt[25];//cnt用于計(jì)算每一層所有的線段數(shù) int l[25][MAXN+5],r[25][MAXN+5];//l表示線段的左端點(diǎn),r表示的則是右端點(diǎn) int f1[MAXN*5+5],f2[MAXN*5+5];//如思路中的定義 bool ans[MAXN+5];//ans記錄的是對(duì)于某一條線段的答案，不是某個(gè)綠洲的答案 void Init() {for(int i=0;i<=MAXN*5+3;i++)f1[i]=0,f2[i]=INF; } int UpFind(int id,int pos)//找l在pos+1的左邊的線段，也就是能夠向右擴(kuò)展的最靠右的線段 {pos++;int p=upper_bound(l[id]+1,l[id]+cnt[id]+1,pos)-l[id];p--;if(p<=0)return pos;return max(r[id][p],pos-1); } int LowFind(int id,int pos)//找r在pos-1的右邊的線段，也就是能夠向左擴(kuò)展的最靠左的線段 {pos--;int p=lower_bound(r[id]+1,r[id]+cnt[id]+1,pos)-r[id];if(p>=cnt[id]+1)return pos;return min(l[id][p],pos+1); } int main() {Init();scanf("%d %d",&n,&V);int logV=0;for(logV=0;(1<<logV)<=V;logV++);//求出來(lái)的實(shí)際上是logV+1for(int i=1;i<=n;i++)scanf("%d",&x[i]);x[n+1]=INF;x[0]=-INF;//便于操作for(int LG=0;LG<=logV;LG++){int d=V/(1<<LG);cnt[LG]=1;l[LG][1]=1;//求線段for(int i=1;i<=n;i++){r[LG][cnt[LG]]=i;if(x[i+1]-x[i]>d){cnt[LG]++;l[LG][cnt[LG]]=i+1;}}cnt[LG]--;}if(cnt[0]>logV+1)//特判{for(int i=1;i<=n;i++)printf("Impossible\n");return 0;}int all=(1<<(logV+1));f1[0]=0,f2[0]=n+1;//預(yù)處理兩個(gè)f數(shù)組for(int s=0;s<all;s+=2)for(int i=0;i<=logV;i++){if(!(s&(1<<i)))continue;f1[s]=max(f1[s],UpFind(i,f1[s-(1<<i)]));f2[s]=min(f2[s],LowFind(i,f2[s-(1<<i)]));}for(int i=1;i<=cnt[0];i++)//枚舉第一層的每一條線段{int ln=l[0][i],rn=r[0][i];for(int s1=0;s1<all;s1+=2){int s2=all-1-s1-1;int lpos=f1[s1];int rpos=f2[s2];if(lpos>=ln-1&&rpos<=rn+1)//看能否覆蓋所有的綠洲{ans[i]=true;//存的是線段的答案break;}}}int pos=1;for(int i=1;i<=n;i++){if(ans[pos]==true)printf("Possible\n");elseprintf("Impossible\n");if(x[i+1]-x[i]>V)pos++;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/T-Y-P-E/p/10176157.html

總結(jié)

以上是生活随笔為你收集整理的【AtCoder】【模拟】【模型转化】Camel and Oases（AGC012）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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