AGC012E - Camel and Oases

AGC012E - Camel and Oases

​​ Problem Statement There are N oases on a number line. The coordinate of the i-th oases from the left is xi.

Camel hopes to visit all these oases. Initially, the volume of the hump on his back is V. When the volume of the hump is v, water of volume at most v can be stored. Water is only supplied at oases. He can get as much water as he can store at a oasis, and the same oasis can be used any number of times.

Camel can travel on the line by either walking or jumping:

Walking over a distance of d costs water of volume d from the hump. A walk that leads to a negative amount of stored water cannot be done. Let v be the amount of water stored at the moment. When v>0, Camel can jump to any point on the line of his choice. After this move, the volume of the hump becomes v⁄2 (rounded down to the nearest integer), and the amount of stored water becomes 0. For each of the oases, determine whether it is possible to start from that oasis and visit all the oases.

Constraints 2≤N,V≤2×105 −109≤x1< x2< …< xN≤109 V and xi are all integers. Input Input is given from Standard Input in the following format:

N V x1 x2 … xN Output Print N lines. The i-th line should contain Possible if it is possible to start from the i-th oasis and visit all the oases, and Impossible otherwise.

Sample Input 1 Copy 3 2 1 3 6 Sample Output 1 Copy Possible Possible Possible It is possible to start from the first oasis and visit all the oases, as follows:

Walk from the first oasis to the second oasis. The amount of stored water becomes 0. Get water at the second oasis. The amount of stored water becomes 2. Jump from the second oasis to the third oasis. The amount of stored water becomes 0, and the volume of the hump becomes 1. Sample Input 2 Copy 7 2 -10 -4 -2 0 2 4 10 Sample Output 2 Copy Impossible Possible Possible Possible Possible Possible Impossible A oasis may be visited any number of times.

Sample Input 3 Copy 16 19 -49 -48 -33 -30 -21 -14 0 15 19 23 44 52 80 81 82 84 Sample Output 3 Copy Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Impossible Impossible Impossible Impossible

围观金牌爷秒题 这不状压dp吗

题目思路leoly讲完后都忘差不多了 从jpy的题解中 重新认识这题

首先啊 这个骆驼 一共只能飞logV次 所以 jpy就想到状压了%%%

我们把每一个v所对应的每个点 如果能在v内 为所欲为的走 的 全部都给他连起来

然后我每次从每一层里选出一条线段 判断他们是否可以连起来覆盖我整个区间

设f1[s]表示 我选择了 s种行走距离 我从左数第一个开始走 最多走多远

f2[s]表示我选择s种行走距离 我从右数第一个开始走 最多走多远

然后设st[i]表示针对每一个点i 表示我用我log种方案中的v覆盖1~i时 我右端x~n的x最靠左的位置在哪里 最后算答案就是 每次检查这个区间 然后判断这个区间的右端点是否覆盖我st[l]的最靠左的位置即可

题意简述 沙漠中有n(n≤2×105)个排成一条直线的绿洲，一头储水量为V(V≤2×105)的骆驼。 骆驼有两个操作：

走到距离在V以内的一个绿洲。 飞到任意一个绿洲，但V减少一半。V=0时不能飞。 问骆驼依次从每个绿洲出发，能否一次性遍历所有绿洲。

分析 首先预处理出 V=V0 时哪些绿洲之间是可以随便走的，对于每个V0扫一遍即可。时间复杂度为O(nlog2V)。

每飞一次相当于下一层。题目转化成钦定第一条线段，然后从每一层选一条线段，问能否覆盖整个区间。 万万没想到，这道题居然是状压DP！！！

抄了一部分jpy大佬的题解 但他的复杂度多了个log 直接贪心做就可以了

#include#includeusing namespace std;#define N 220000inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}#define S 1<<19inline int read(){ int x=0,f=1;char ch=gc(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}int f1[S],f2[S],n,num,bin[20],st[N],a[N],right[N][20],left[N][20],v;int main(){ freopen("agc.in","r",stdin); n=read();v=read();int Log=0; for (int i=1;i<=n;++i) a[i]=read(); while ((1<v) num++; for (int j=0;j(v>>j)) left[i][j]=i;else left[i][j]=left[i-1][j]; for (int i=n-1;i>=1;--i) if (a[i+1]-a[i]>(v>>j)) right[i][j]=i;else right[i][j]=right[i+1][j]; } /*for (int j=0;j=1;--i) printf("%d,left[i][j]);printf("\n"); }*/ if (num>Log){ for (int i=1;i<=n;++i) printf("Impossible\n");return 0; } for (int s=0;s<=bin[Log]-1;++s) {f1[s]=0,f2[s]=n+1;} for (int s=0;s<=bin[Log]-1;++s){ for (int i=0;i=0;--i) st[i]=min(st[i],st[i+1]); //for (int i=0;i<=n;++i) printf("%d,st[i]);printf("\n"); for (int i=1;i<=n;++i){ int l=left[i][0],r=right[i][0]; if (st[l-1]<=r+1) printf("Possible\n");else printf("Impossible\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。