百度之星复赛Astar Round3

拍照

树状数组(SB了)。求出静止状态下，每个点能看到多少个向右开的船c1[i]，多少个向左开的船c2[i]。

max{c1[i] + c2[j], (满足i <= j) }即为答案。从后往前枚举i即可。

注意要离散化，否则会Tle。

 1 #include <bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 
 5 const int maxn =2e4;
 6 //c1 向右开的船
 7 int c1[maxn<<2], c2[maxn<<2];
 8 int s1[maxn<<2], s2[maxn<<2];
 9 
10 int lowbit(int x){ return x&-x;}
11 void add(int x, int d, int* c){//c[x]++;
12     while(x <= (maxn<<2)){
13         c[x] += d;
14         x += lowbit(x);
15     }
16 }
17 void Add(int l, int r, int* c){
18     add(l, 1, c);
19     add(r+1, -1, c);
20 }
21 int sum(int x, int* c){
22     int ret = 0;
23     while(x > 0){
24         ret += c[x];
25         x -= (x&-x);
26     }
27     return ret;
28 }
29 
30 int n;
31 int ope[maxn], tot;
32 struct p{
33     int l, r, d;
34     p(){}
35     p(int l, int r, int d):l(l), r(r), d(d){}
36 };
37 p pp[maxn];
38 
39 int main(){
40     int t, ca = 1;scanf("%d", &t);
41     while(t--){
42         scanf("%d", &n);
43         memset(c1, 0, sizeof(c1));
44         memset(c2, 0, sizeof(c2));
45         int l, r, x, y, z, d;
46 
47         tot = 0;
48         for(int i = 0; i < n; i++){
49             scanf("%d%d%d%d", &x, &y, &z, &d);
50             l = y-z+maxn, r = x+z+maxn;
51             ope[tot++] = l, ope[tot++] = r;
52             pp[i] = p(l, r, d);
53         }
54 
55         sort(ope, ope+tot);
56         //tot = unique(ope, ope+tot)-ope;
57         for(int i = 0; i < n; i++){
58             int l = lower_bound(ope, ope+tot, pp[i].l)-ope+1;
59             int r = lower_bound(ope, ope+tot, pp[i].r)-ope+1;
60             int d = pp[i].d;
61             if(l <= r)
62                 Add(l, r, (d == 1? c1 : c2));
63         }
64 
65         for(int i = 0; i < (maxn<<2); i++)
66             s1[i] = sum(i, c1);
67         for(int i = 0; i < (maxn<<2); i++)
68             s2[i] = sum(i, c2);
69 
70         int ans = 0;
71         for(int i = (maxn<<2)-2; i > 0; i--){
72             s2[i] = max(s2[i], s2[i+1]);
73             ans = max(ans, s1[i]+s2[i]);
74         }
75         printf("Case #%d:
%d
", ca++, ans);
76     }
77     return 0;
78 }

View Code

更新：SB了，要树状数组干什么用。。反正是要求出每个点能看到的船只数，直接做一遍前缀和累加一下就可以了。。。树状数组都省了。

代码如下：

 1 #include <bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 
 5 const int maxn =2e4;
 6 int c1[maxn<<2], c2[maxn<<2];
 7 
 8 void Add(int l, int r, int* c){
 9     c[l]++, c[r+1]--;
10 }
11 
12 int n;
13 int ope[maxn], tot;
14 struct p{
15     int l, r, d;
16     p(){}
17     p(int l, int r, int d):l(l), r(r), d(d){}
18 };
19 p pp[maxn];
20 
21 int main(){
22     int t, ca = 1;scanf("%d", &t);
23     while(t--){
24         scanf("%d", &n);
25         memset(c1, 0, sizeof(c1));
26         memset(c2, 0, sizeof(c2));
27         int l, r, x, y, z, d;
28 
29         tot = 0;
30         for(int i = 0; i < n; i++){
31             scanf("%d%d%d%d", &x, &y, &z, &d);
32             l = y-z+maxn, r = x+z+maxn;
33             ope[tot++] = l, ope[tot++] = r;
34             pp[i] = p(l, r, d);
35         }
36 
37         sort(ope, ope+tot);
38         //tot = unique(ope, ope+tot)-ope;
39         for(int i = 0; i < n; i++){
40             int l = lower_bound(ope, ope+tot, pp[i].l)-ope+1;
41             int r = lower_bound(ope, ope+tot, pp[i].r)-ope+1;
42             int d = pp[i].d;
43             if(l <= r)
44                 Add(l, r, (d == 1? c1 : c2));
45         }
46 
47         for(int i = 1; i < (maxn<<2); i++)
48             c1[i] += c1[i-1], c2[i] += c2[i-1];
49 
50         int ans = 0;
51         for(int i = (maxn<<2)-2; i > 0; i--){
52             c2[i] = max(c2[i], c2[i+1]);
53             ans = max(ans, c1[i]+c2[i]);
54         }
55         printf("Case #%d:
%d
", ca++, ans);
56     }
57     return 0;
58 }

View Code