题解 P3422 【[POI2005]LOT-A Journey to Mars】

oscar

2017-09-14 14:12:03

Solution

【POI补全计划#6 POI2005 LOT】 先考虑从1号点开始时如何判定能否绕一圈 发现只要对油量和路程的差求一下前缀和看一下2~n+1号空间站中有没有剩余油量小于0的位置(假设走到n+1号空间站自动瞬移到1号空间站) 又发现从第k个空间站出发相当于不管前面k-1个空间站,查询 k+1~n+1号空间站剩余油量 和 (1~k号空间站剩余油量 + n+1号空间站剩余油量) 是否有小于0的 这个信息可以通过一开始1号点出发的信息和k号空间站的前缀和处理出来,于是预处理一下从1号空间站开始时的那个前缀和的前缀min和后缀min就可以O(1)查询了 条件大概长这样 ```cpp mins[i+1]-delta>=0&&sum[n+1]-delta>=0&&sum[n+1]-delta+minp[i]>=0 ``` (其中mins为前缀和的后缀min,minp为前缀和的前缀min,delta为第i个空间站的前缀和,sum[n+1]是所有油量总和减去所有路程总和) 最后反向处理一遍,判断沿编号减小方向走能不能回来就好了 ~~不要忘了第i行的那个距离代表的是i~i+1间的距离,如果像我一样变换坐标算的话要重排一下距离~~ 最后照例贴代码 ```cpp #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN=1000010; int len[MAXN],fuel[MAXN],sum[MAXN],minp[MAXN],mins[MAXN],ans[MAXN]; int n; int main() { scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d%d",&fuel[i],&len[i]); memset(minp,0x7f,sizeof(minp)); memset(mins,0x7f,sizeof(mins)); for(int i=1;i<=n;++i) { sum[i+1]=sum[i]+fuel[i]-len[i]; if(minp[i]>sum[i+1])minp[i+1]=sum[i+1]; else minp[i+1]=minp[i]; } for(int i=n+1;i>1;--i) { if(mins[i+1]>sum[i])mins[i]=sum[i]; else mins[i]=mins[i+1]; } int delta; for(int i=1;i<=n;++i) { delta=sum[i]; if(mins[i+1]-delta>=0&&sum[n+1]-delta>=0&&sum[n+1]-delta+minp[i]>=0)ans[i]|=1; } int tmp=len[n]; for(int i=n;i>=1;--i) len[i]=len[i-1]; len[1]=tmp; for(int i=1;i<n-i+1;++i) { swap(fuel[i],fuel[n-i+1]); swap(len[i],len[n-i+1]); } memset(minp,0x7f,sizeof(minp)); memset(mins,0x7f,sizeof(mins)); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;++i) { sum[i+1]=sum[i]+fuel[i]-len[i]; if(minp[i]>sum[i+1])minp[i+1]=sum[i+1]; else minp[i+1]=minp[i]; } for(int i=n+1;i>1;--i) { if(mins[i+1]>sum[i])mins[i]=sum[i]; else mins[i]=mins[i+1]; } for(int i=1;i<=n;++i) { delta=sum[i]; if(mins[i+1]-delta>=0&&sum[n+1]-delta>=0&&sum[n+1]-delta+minp[i]>=0)ans[n-i+1]|=1; } for(int i=1;i<=n;++i) { if(ans[i])printf("TAK\n"); else printf("NIE\n"); } return 0; } ``` [email protected] 增加标题,增加部分详细描述