[AGC012E] Camel and Oases 题解

题目链接

题目链接

题目解法

可能并没有那么难（？

首先 \(V\) 的取值只有 \(\log V\) 种，即 \(\lfloor \frac{V}{2^k}\rfloor\)
称 \(\lfloor \frac{V}{2^k}\rfloor\) 为第 \(k\) 层，先预处理出每一层的极大连通区间
我们可以把问题抽象成：每一层中选一个区间，要求覆盖 \([1,n]\)，且第 \(0\) 层的区间是固定的

我们不考虑第 \(0\) 层
因为层数比较少，所以考虑状压
令 \(fl_S\) 表示只考虑集合 \(S\) 中的层，能从头开始覆盖到的最远位置
同理定义 \(fr_S\)
转移是简单的

加上第 \(0\) 层，考虑枚举每一段计算结果
如果段数 \(>\log V\) 就无解

时间复杂度 \(O((V+n)\log V)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=200010,M=18,inf=1e9;
int n,V,x[N],lay[M];
int rngl[M][N],rngr[M][N],fl[1<<M],fr[1<<M];
bool ans[N];
int main(){
    read(n),read(V);
    F(i,1,n) read(x[i]);
    lay[0]=V/2;
    int mxd=0;
    while(lay[mxd]) mxd++,lay[mxd]=lay[mxd-1]/2;
    F(i,0,mxd)
        F(j,1,n){
            int k=j;
            while(k<n&&x[k+1]-x[k]<=lay[i]) k++;
            rngl[i][j]=k,rngr[i][k]=j,j=k;
        }
    int full=(1<<(mxd+1))-1;
    fl[0]=0;
    F(S,0,full)
        F(j,0,mxd) if(!(S>>j&1)&&rngl[j][fl[S]+1])
            chkmax(fl[S^1<<j],rngl[j][fl[S]+1]);
    F(S,0,full) fr[S]=inf;
    fr[0]=n+1;
    F(S,0,full) if(fr[S]!=inf)
        F(j,0,mxd) if(!(S>>j&1)&&rngr[j][fr[S]-1])
            chkmin(fr[S^1<<j],rngr[j][fr[S]-1]);
    int tot=0;
    F(i,1,n){
        int j=i;
        while(j<n&&x[j+1]-x[j]<=V) j++;
        tot++;
        if(tot>mxd+2){ F(i,1,n) ans[i]=0;break;}
        bool flg=0;
        F(S,0,full) if(fl[S]>=i-1&&fr[S^full]<=j+1){ flg=1;break;}
        if(flg) F(k,i,j) ans[k]=1;
        i=j;
    }
    F(i,1,n) if(ans[i]) puts("Possible");else puts("Impossible");
    return 0;
}