[??记录]AT2365 [AGC012E] Camel and Oases
command_block
2021-04-28 22:09:42
**题意** ： 给定 $n$ 个绿洲，坐标为 $x_{1\sim n}$ 。
初始背包容积为 $V$ 升且满水。每到达一个绿洲，可以将背包加满水。他拥有
可以利用下列两个操作来旅行：
$1.$ 走路，行走距离为 $d$ 时，需要消耗 $d$ 升水。任意时刻拥有的水的数量不能为负数。
$2.$ 跳跃，令 $v$ 为你当前拥有的水量，若 $v>0$，则你可以跳跃至任意一个绿洲，然后重置容积上界和所拥有的水量为 $\lfloor v/2\rfloor$ 。
对于每一个 $i$ ，判定当你在第 $i$ 个绿洲作为起点时，你能否遍历其他所有绿洲。
$n,v\leq 2\times 10^5$ ，时限$\texttt{2s}$。
------------
- 跳跃只能进行 $O(\log v)$ 次。
- 给定背包容积时，从某点 $u$ 出发能到达的绿洲是一段连续区间。
各个点的区间要么不交，要么相同。
于是，对 $O(\log v)$ 类背包容积，分别求出从每个点出发能到达的区间。
然后问题变为 ：
在每类区间集合中各选出一个，且第一种的区间必选 $u$ ，能否覆盖全集。
考虑状压 $\rm DP$ ，记 $f_s$ 表示在类 $s$ 中选了区间，覆盖的最长前缀。
转移时，枚举某一类，然后取左端点在 $[1,f[s]+1]$ 内的最靠右的区间。
复杂度为 $O(2^{\log_2v}\log v)=O(v\log v)$。
但题目要求钦定第一类所选的区间，那就要加一维，复杂度变为 $O(v^2\log v)$ ，无法承受。
我们发现，若第一类有超过 $\log_2v$ 个本质不同的区间，则必然无解。故实际上加上的那一维大小只需要为 $O(\log v)$。
复杂度 $O(v\log^2v)$。
还有一个复杂度更好的做法，先不考虑第一类，计算出 $f_s,g_s$ 分别表示最长前缀 / 后缀。
然后枚举第一类的区间，再枚举前缀集合 $s$ ，后缀则取补集。
这样复杂度就是 $O(v\log v)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 200500
using namespace std;
const int INF=2000000000;
int n,v,x[MaxN],tr[20][MaxN],tl[20][MaxN],f[270000],g[270000];
int main()
{
scanf("%d%d",&n,&v);
for (int i=1;i<=n;i++)
scanf("%d",&x[i]);
for (int i=n;i;i--)x[i]-=x[i-1];
x[1]=x[n+1]=INF;
int m=1;
for (;v>>m;m++){
for (int i=2,las=1;i<=n+1;i++){
if ((v>>m)<x[i]){
for (int k=las;k<i;k++){
tr[m-1][k]=i-1;
tl[m-1][k]=las;
}las=i;
}
}
tr[m-1][n+1]=n;
tl[m-1][0]=1;
}
for (int i=1;i<=n;i++)
tl[m-1][i]=tr[m-1][i]=i;
tl[m-1][n+1]=n;tr[m-1][0]=1;
for (int s=0;s<(1<<m);s++)g[s]=n+1;
for (int s=0;s<(1<<m);s++)
for (int i=0;i<m;i++)
if (!(s&(1<<i))){
f[s|(1<<i)]=max(f[s|(1<<i)],tr[i][f[s]+1]);
g[s|(1<<i)]=min(g[s|(1<<i)],tl[i][g[s]-1]);
}
for (int i=2,las=1;i<=n+1;i++)
if (v<x[i]){
bool fl=0;
for (int s=0;s<(1<<m);s++)
fl|=(f[s]>=las-1&&i>=g[((1<<m)-1)^s]);
for (int k=las;k<i;k++)
puts(fl ? "Possible" : "Impossible");
las=i;
}
return 0;
}
```