BZOJ1533: [POI2005]Lot-A Journey to Mars

1533: [POI2005]Lot-A Journey to Mars

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 174 Solved: 76
[Submit][Status]

Description

Byteazar 决定去火星参加一个空间站旅行. 火星的所有空间站都位于一个圆上. Byteazar 在其中一个登陆然后变开始饶圈旅行. 旅行需要耗费油料,一升油料只能跑1米,每个空间站可以补给的油料都有所不同. Byteazar 每到一个空间站便可以把该空间站的油料全部拿走.(他的油箱是没有容量限制的) 但是如果走到某个时候突然没油了那么旅行便失败了. Byteazar 需要决定要在哪个地方登陆使得他能顺利访问完所有的空间站后回到他当初登陆的地方. 一个细节是他登陆后可以选择两个方向中的任意一个进行旅行.

Input

第一行是一个数N (3 <= N <= 1 000 000). 表示空间站的总数. 空间站从1 到 N标号. 接下来N 行每行两个数pi 和 di (pi<= 0, di > 0). 表示第i个空间站所储存的油料以及第i个到第i + 1个空间站之间的距离( dN 表示第N个空间站到第1个空间站的距离). 所有的油料以及所有的距离的和保证不超过2 000 000 000.

Output

输出n行,如果从第i个空间站登陆可以走遍所有的空间站那么打印TAK (YES is Polish), 否则打印NIE (NO in Polish).

Sample Input

5
3 1
1 2
5 2
0 1
5 4

Sample Output

TAK
NIE
TAK
NIE
TAK

HINT

Source

题解：

苦尽而后甘来。。。

如果总油量<总路程显然全部输出no

否则若总油量==总路程，构造前缀和s[i]=sigma(p[j]-d[j]) j<i 。

把(i,s[i])画在平面直角坐标系上，则选择最下方的一个点记为k开刀

因为从k出发，这条折线总是上升的，转一圈回到k，不会往下说明不会出现油量不够，所以该点可行。

继续将其推广若总油量>总路程，则仍像上面一样构造一条折线。

记 res=sigma（p[i]-d[i])

则i 可行的充要条件是：

1）i 点之后没有在 i 点下方的点

2）i 点之前点j满足 s[j]+res<s[i]

想一下如何转一圈就可以理解了

然后就可以前缀最小值乱搞了。。。

代码待UPD(我不会说我写了但是WA了）

发现了更简单的方法T_T

jcvb:(+p[i]-d[i])自复制一遍接在后面，求前缀和。然后能用单调队列搞出每个点往右走的最远距离，>=n则可行。逆时针同理再做一遍。

话说和我的做法差不多一样啊，只不过思考难度小一点。。。

UPD：单调队列做法已A

 1 #include<cstdio>
 2  
 3 #include<cstdlib>
 4  
 5 #include<cmath>
 6  
 7 #include<cstring>
 8  
 9 #include<algorithm>
10  
11 #include<iostream>
12  
13 #include<vector>
14  
15 #include<map>
16  
17 #include<set>
18  
19 #include<queue>
20  
21 #include<string>
22  
23 #define inf 1000000000
24  
25 #define maxn 2000000+100
26  
27 #define maxm 500+100
28  
29 #define eps 1e-10
30  
31 #define ll long long
32  
33 #define pa pair<int,int>
34  
35 #define for0(i,n) for(int i=0;i<=(n);i++)
36  
37 #define for1(i,n) for(int i=1;i<=(n);i++)
38  
39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
40  
41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
42  
43 #define mod 1000000007
44  
45 using namespace std;
46  
47 inline int read()
48  
49 {
50  
51     int x=0,f=1;char ch=getchar();
52  
53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
54  
55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
56  
57     return x*f;
58  
59 }
60 struct rec{int x,y;}a[maxn];
61 int b[maxn],sta[maxn],r[maxn],res,n;
62 bool can[2][maxn];
63 void work(int k)
64 {
65     b[0]=0;
66     for1(i,n)b[i]=b[i-1]+a[i].x-a[i].y;
67     for1(i,n)b[n+i]=b[n+i-1]+a[i].x-a[i].y;
68     int top=0;b[2*n+1]=-inf;
69     for0(i,(n<<1)+1)
70     {
71         while(top&&b[i]<b[sta[top]])r[sta[top--]]=i-1;
72         sta[++top]=i;
73     }
74     for0(i,n-1)if(r[i]-i+1>=n)can[k][i+1]=1;
75 }
76  
77 int main()
78  
79 {
80    freopen("input.txt","r",stdin);
81    freopen("output.txt","w",stdout);
82     n=read();
83     for1(i,n)a[i].x=read(),a[i].y=read(),res+=a[i].x-a[i].y;
84     if(res<0){for1(i,n)printf("NIE
");return 0;}
85     work(0);
86     for1(i,n>>1)swap(a[i],a[n+1-i]);
87     int t=a[1].y;
88     for1(i,n-1)a[i].y=a[i+1].y;
89     a[n].y=t;
90     work(1);
91     for1(i,n)if(can[0][i]||can[1][n+1-i])printf("TAK
");else printf("NIE
");
92     return 0;
93  
94 }

View Code

我的做法未A 不知为何调了半天cena没调好目测一些数据是对的

 1 #include<cstdio>
 2  
 3 #include<cstdlib>
 4  
 5 #include<cmath>
 6  
 7 #include<cstring>
 8  
 9 #include<algorithm>
10  
11 #include<iostream>
12  
13 #include<vector>
14  
15 #include<map>
16  
17 #include<set>
18  
19 #include<queue>
20  
21 #include<string>
22  
23 #define inf 1000000000
24  
25 #define maxn 1000000+100
26  
27 #define maxm 500+100
28  
29 #define eps 1e-10
30  
31 #define ll long long
32  
33 #define pa pair<int,int>
34  
35 #define for0(i,n) for(int i=0;i<=(n);i++)
36  
37 #define for1(i,n) for(int i=1;i<=(n);i++)
38  
39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
40  
41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
42  
43 #define mod 1000000007
44  
45 using namespace std;
46  
47 inline int read()
48  
49 {
50  
51     int x=0,f=1;char ch=getchar();
52  
53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
54  
55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
56  
57     return x*f;
58  
59 }
60 struct rec{int x,y;}a[maxn];
61 int b[maxn],c[maxn],res,n;
62 bool can[2][maxn];
63 void work(int k)
64 {
65     for1(i,n)b[i]=b[i-1]+a[i].x-a[i].y;
66     c[0]=inf;can[k][1]=1;
67     for1(i,n-1)
68     {
69         c[i]=min(c[i-1],b[i]);
70         can[k][i+1]=c[i]+res>=b[i]?1:0;
71     }
72     c[n]=inf;
73     for3(i,n-1,0)
74     {
75         c[i]=min(c[i+1],b[i]);
76         if(can[k][i+1])can[k][i+1]=c[i]>=b[i]?1:0;
77     }
78 }
79  
80 int main()
81  
82 {
83     freopen("input.txt","r",stdin);
84     freopen("output.txt","w",stdout);
85     n=read();
86     for1(i,n)a[i].x=read(),a[i].y=read(),res+=a[i].x-a[i].y;
87     if(res<0){for1(i,n)printf("NIE
");return 0;}
88     work(0);
89     for1(i,n>>1)swap(a[i],a[n+1-i]);
90     int t=a[1].y;
91     for1(i,n-1)a[i].y=a[i+1].y;
92     a[n].y=t;
93     work(1);
94     for1(i,n)if(can[0][i]||can[1][n+1-i])printf("TAK
");else printf("NIE
");
95  
96     return 0;
97  
98 }

View Code

发现错误是逆时针转的时候必须把路的方向转过来，也就是从 i 出发走的是 d[i-1] T_T

还有我的做法中只要一个条件不满足就不行。。。