Portal --> agc012

Description

　　有一排點，兩點間有一定距離，初始的時候有一個行走值\(v\)，如果說兩點間距離不超過\(v\)，那么可以在這兩點間自由行走，如果當(dāng)前\(v>0\)那么可以選擇突然出現(xiàn)在任意一點，但是這樣做之后\(v\)會減半（下取整），問每個位置出發(fā)能否到達(dá)所有的位置至少一次

　　

Solution

　　額其實感覺關(guān)鍵還是模型的轉(zhuǎn)化

?　　其實我們可以比較形象地將每個\(v\)（就是不停除以\(2\)直到\(0\)，中途得到的那堆\(v\)），看成“一層”，具體舉個例子的話就是：當(dāng)\(v=4\)的時候，第一層為\(v=4\)，第二層為\(v=2\)，第三層為\(v=1\)，第四層為\(v=0\)，這樣

?　　然后每次突然出現(xiàn)其實就相當(dāng)于往上走了一層，而每層中，有一些區(qū)間是可以在區(qū)間內(nèi)隨便走的，我們將這些區(qū)間看成若干條線段，那么現(xiàn)在的問題就變成了，每層選一條線段，問是否能夠覆蓋整個區(qū)間

?　　想不到吧然后因為層數(shù)上限是\(19\)所以。。這是一道狀壓dp的題目==

?　　

?　　所以首先，我們先將每一層中的線段處理出來，將第\(i\)層的線段存在\(seg[i]\)數(shù)組里面，只用存右端點即可，左端點可以由前一條線段的右端點\(+1\)得到

?　　考慮一下大概要用什么樣的方式統(tǒng)計答案，我們可以考慮枚舉第一層的每條線段\((l_i,r_i)\)，如果說存在一種方案使得從\(1\)開始覆蓋到一個\(>=l_i-1\)的位置，從\(n\)開始覆蓋到一個\(<=r_i+1\)的位置，那么這段線段中的每一個點都是\(Possible\)的，否則就是\(Impossible\)

?　　那么所以，我們考慮維護(hù)兩個數(shù)組\(tol\)和\(tor\)，其中\(tor[i]\)表示線段選擇狀態(tài)（如果這層選了線段那么對應(yīng)的二進(jìn)制位為\(1\)否則為\(0\)）為\(i\)的情況下，從\(1\)開始往右最遠(yuǎn)能覆蓋到的位置，\(tol[i]\)表示從\(n\)開始往左最遠(yuǎn)能覆蓋到的位置，注意，因為最后統(tǒng)計答案的時候，第一層的線段是要枚舉的，所以我們在計算\(tor\)和\(tol\)的枚舉狀態(tài)的時候，不能包含第一層

?　　接下來定義兩個過程：\(expandReft(which,x)\)表示在第\(which\)層的線段中，嚴(yán)格大于\(x\)的第一個右端點，\(expandLight(which,x)\)表示在第\(which\)層的線段中，嚴(yán)格小于\(x\)的最靠近\(n\)的右端點

?　　那么我們可以得到轉(zhuǎn)移式子：
\[ \begin{aligned} tor[st|St(i)]&=max(tor[st|St(i)],expandRight(i,tor[st]))\\ tol[st|St(i)]&=min(tol[st|St(i)],expandLeft(i,tol[st]-1))\\ \end{aligned} \]
　　至于為什么要用\(tol[st]-1\)的話。。是因為如果直接找\(tol[st]\)的話，我們可能找到\(tol[st]\)，這就說明有一段以\(tol[st]-1\)為右端點的區(qū)間以及一段以\(tol[st]\)為左端點的區(qū)間，然而這個時候我們應(yīng)該找前者而不是后者會出些小問題==（不過也可能只是實現(xiàn)方式的問題。。具體都是看二分查找要怎么寫吧都是一些實現(xiàn)上的細(xì)節(jié)問題qwq）

　　那么最后一個小問題就是，如果說第一層有很多條線段的話那就很涼涼，然而實際上，我們發(fā)現(xiàn)如果說第一層的線段條數(shù)\(>logv+1\)的話。。就根本不可能覆蓋完了（層數(shù)不夠），所以我們可以在計算之前先判一下這種全部都是\(Impossible\)的情況

　　那所以我們的總復(fù)雜度就是\(O(nlogv+vlognlogv)\)了

　　

　　代碼大概長這個樣子

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int N=2*(1e5)+10,ST=1<<20,TOP=20,inf=2e9; int seg[TOP+1][N],d[N],tor[ST],tol[ST],a[N]; int n,m,v,lg,all; bool in(int st,int x){return st>>x-1&1;} int St(int x){return 1<<x-1;} void get_seg(){for (int i=1;i<=lg;++i){seg[i][0]=0;for (int j=1;j<=n;++j){if (j==1||d[j-1]>v>>i-1) ++seg[i][0];seg[i][seg[i][0]]=j;}} } bool firstcheck(){if (seg[1][0]<=lg) return true;for (int i=1;i<=n;++i) printf("Impossible\n");return false; } int expand_right(int which,int x){int l=1,r=seg[which][0],mid,ret=r;while (l<=r){mid=l+r>>1;if (seg[which][mid]>x) ret=mid,r=mid-1;else l=mid+1;}return seg[which][ret]; } int expand_left(int which,int x){int l=1,r=seg[which][0],mid,ret=l;while (l<=r){mid=l+r>>1;if (seg[which][mid]<x) ret=mid,l=mid+1;else r=mid-1;}return seg[which][ret]+1; } void dp(){all=1<<lg;for (int st=0;st<all;++st) tor[st]=0,tol[st]=n+1;for (int st=0;st<all;st+=2){for (int i=2;i<=lg;++i){if (in(st,i)) continue;tor[st|St(i)]=max(tor[st|St(i)],expand_right(i,tor[st]));tol[st|St(i)]=min(tol[st|St(i)],expand_left(i,tol[st]-1));}} } void get_ans(){int L,R;bool ok;for (int i=1;i<=seg[1][0];++i){L=i==1?1:seg[1][i-1]+1; R=seg[1][i];ok=false;for (int st=0;st<all&&!ok;st+=2)if (L-1<=tor[st]&&tol[(all-1)-st-1]<=R+1) ok=true;for (int j=L;j<=R;++j) printf(ok?"Possible\n":"Impossible\n");} }int main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin); #endifscanf("%d%d",&n,&v);for (int i=1;i<=n;++i) scanf("%d",a+i);d[n]=inf;for (int i=1;i<n;++i) d[i]=a[i+1]-a[i];lg=0;while ((v>>lg)>0) ++lg;++lg;get_seg();if (!firstcheck()) return 0;dp();get_ans(); }

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

總結(jié)

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

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