我是靠谱客的博主 风中花生，这篇文章主要介绍2019杭电多校第9场1002 Rikka with Cake HDU66812019杭电多校第9场1002 Rikka with Cake HDU6681解法1：红黑树+思维+贪心解法2：树状数组+思维+贪心，现在分享给大家，希望可以做个参考。
2019杭电多校第9场1002 Rikka with Cake HDU6681
题意：给你若干个点按上下左右切割平面，最后问平面内有几块被切割开来。
解法1：红黑树+思维+贪心
A：根据欧拉定理可以得出（具体参照题解），平面内有多少个交点，那么就有这么多个+1的平面被分割出来，所以这题目就是找点。
B：将U,D,L,R分开来存在四个结构体中，然后分类讨论U和L相交的点数，U和R相交的点数，D和L相交的点数，D和R相交的点数，最后相加再+1就是答案。
C：在讨论的时候。举例(U和L相交）。按着l[i]的x从小到大排序，u[i]的x从小到大排序，然后遍历l，找l[i]能和几条向上的线相交。我们可以知道相交必然意味着，u[j]的x比l[i]的小，同时我们要找在这几个中有几个u[j]的y坐标小于l[i].y，最后全部相加。这样就讨论完了一处情况。
D：关于上面C黄字的处理，利用红黑树，正好插入一个值与查询有几个小于的复杂都是log(n)，然后不停插入，然后比较相加就完事了。
解法2：树状数组+思维+贪心
A：早上看了一下题解发现树状数组也能做，贴一个树状数组的解法吧，其实和上面的解法很像，就是把(D过程）红黑树改成树状数组就OK了。
B：两者代码的不同也很明显，我直接在我的红黑树上改了一下，具体可以看代码2。
闲话123：关于红黑树，我这里偷懒使用超级STL库来实现了。比赛的时候，想了很久主席树该怎么实现，写到吐血。。最后发现了有pb_ds这个神奇的东西，最后花了30分钟写题目，WA了三发。。。最后赛后刚把题目放出来就A了，真赛后三分钟A题，谢队友不杀。
PS：超级STL库只能在clion里面运行，辣鸡VS2019
解法1代码1：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/hash_policy.hpp> #include <ext/pb_ds/priority_queue.hpp> #include <functional> #include <algorithm> #include <iostream> #include <cstdio> using namespace __gnu_pbds; using namespace std; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> rbtree; typedef long long ll; ll n,m,k; const int mx = 3e5+7; struct node { ll x, y; }u[mx],d[mx],l[mx],r[mx]; bool cmp(node a,node b) { return a.x < b.x; } int main (){ ios_base::sync_with_stdio(false); rbtree stlnb; int t; cin >> t; while (t--) { cin >> n >> m >> k; ll cnt[6] = { 0 }; for (int i = 1; i <= k; i++) { ll x, y; char s; cin>>x>>y>>s; if (s == 'U') u[++cnt[1]].x = x, u[cnt[1]].y = y; else if (s == 'D') d[++cnt[2]].x = x, d[cnt[2]].y = y; else if (s == 'L') l[++cnt[3]].x = x, l[cnt[3]].y = y; else if (s == 'R') r[++cnt[4]].x = x, r[cnt[4]].y = y; } sort(u + 1, u + 1 + cnt[1], cmp); sort(d + 1, d + 1 + cnt[2], cmp); sort(l + 1, l + 1 + cnt[3], cmp); sort(r + 1, r + 1 + cnt[4], cmp); ll sumn = 0; ll f = 1; for (int i = 1; i <= cnt[3]; i++) { for (int j = f; j <= cnt[1]; j++) { f = j+1; if (l[i].x >= u[j].x) stlnb.insert(u[j].y); else { f = j; break; } } sumn += stlnb.order_of_key(l[i].y); } stlnb.clear(); f = cnt[1]; for (int i = cnt[4]; i >= 1; i--) { for (int j = f; j >= 1; j--) { f = j-1; if (r[i].x <= u[j].x) stlnb.insert(u[j].y); else { f = j; break; } } sumn += stlnb.order_of_key(r[i].y); } stlnb.clear(); f = 1; for (int i = 1; i <= cnt[3]; i++) { for (int j = f; j <= cnt[2]; j++) { f = j+1; if (l[i].x >= d[j].x) stlnb.insert(d[j].y); else { f = j; break; } } sumn += stlnb.size() - stlnb.order_of_key(l[i].y); } stlnb.clear(); f = cnt[2]; for (int i = cnt[4]; i >= 1; i--) { for (int j = f; j >= 1; j--) { f = j-1; if (r[i].x <= d[j].x) stlnb.insert(d[j].y); else { f = j; break; } } sumn += stlnb.size() -stlnb.order_of_key(r[i].y); } stlnb.clear(); cout<<sumn+1<<endl; } return 0; }
解法2代码：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159#include <functional> #include <algorithm> #include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; ll n,m,k; const int mx = 3e5+7; const ll wa = 1e9+7; struct node { ll x, y; ll qx,qy; }u[mx],d[mx],l[mx],r[mx]; ll ssx[mx],ssy[mx]; bool cmp(node a,node b) { return a.x < b.x; } int bit[mx]; int lowbit(int x) { return x&(-x); } void add(int i,int x) { while(i<=k) { bit[i]+=x; i+=lowbit(i); } } void sub(int i,int x) { while(i<=k) { bit[i]-=x; i+=lowbit(i); } } int sum(int i) { int s=0; while(i>0) { s+=bit[i]; i-=lowbit(i); } return s; } int main (){ ios_base::sync_with_stdio(false); #ifdef ACM_LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int t; cin >> t; while (t--) { cin >> n >> m >> k; ll cnt[6] = { 0 }; for (int i = 1; i <= k; i++) { ll x, y; char s; cin>>x>>y>>s; if (s == 'U') u[++cnt[1]].x = x, u[cnt[1]].y = y; else if (s == 'D') d[++cnt[2]].x = x, d[cnt[2]].y = y; else if (s == 'L') l[++cnt[3]].x = x, l[cnt[3]].y = y; else if (s == 'R') r[++cnt[4]].x = x, r[cnt[4]].y = y; ssx[i] = x; ssy[i] = y; } sort(ssx+1,ssx+1+k); sort(ssy+1,ssy+1+k); sort(u + 1, u + 1 + cnt[1], cmp); sort(d + 1, d + 1 + cnt[2], cmp); sort(l + 1, l + 1 + cnt[3], cmp); sort(r + 1, r + 1 + cnt[4], cmp); ll sumn = 0; ll f = 1; for (int i = 1; i <= cnt[3]; i++) { for (int j = f; j <= cnt[1]; j++) { f = j+1; if (l[i].x >= u[j].x) { int sr = lower_bound(ssy+1,ssy+1+k,u[j].y)-ssy; add(sr,1); //stlnb.insert(u[j].y); } else { f = j; break; } } //sumn += stlnb.order_of_key(l[i].y); sumn+=sum(lower_bound(ssy+1,ssy+1+k,l[i].y)-ssy); } //stlnb.clear(); memset(bit,0,sizeof(bit)); f = cnt[1]; for (int i = cnt[4]; i >= 1; i--) { for (int j = f; j >= 1; j--) { f = j-1; if (r[i].x <= u[j].x) add(lower_bound(ssy+1,ssy+1+k,u[j].y)-ssy,1);//stlnb.insert(u[j].y); else { f = j; break; } } // sumn += stlnb.order_of_key(r[i].y); sumn += sum(lower_bound(ssy+1,ssy+1+k,r[i].y)-ssy); } //stlnb.clear(); memset(bit,0,sizeof(bit)); f = 1; ll ssr = 0; for (int i = 1; i <= cnt[3]; i++) { for (int j = f; j <= cnt[2]; j++) { f = j+1; if (l[i].x >= d[j].x) add(lower_bound(ssy+1,ssy+1+k,d[j].y)-ssy,1),ssr++;//stlnb.insert(d[j].y); else { f = j; break; } } //sumn += stlnb.size() - stlnb.order_of_key(l[i].y); sumn += ssr - sum(lower_bound(ssy+1,ssy+1+k,l[i].y)-ssy); } //stlnb.clear(); memset(bit,0,sizeof(bit)); ssr = 0; f = cnt[2]; for (int i = cnt[4]; i >= 1; i--) { for (int j = f; j >= 1; j--) { f = j-1; if (r[i].x <= d[j].x) add(lower_bound(ssy+1,ssy+1+k,d[j].y)-ssy,1),ssr++;//stlnb.insert(d[j].y); else { f = j; break; } } //sumn += stlnb.size() -stlnb.order_of_key(r[i].y); sumn += ssr - sum(lower_bound(ssy+1,ssy+1+k,r[i].y)-ssy);; } //stlnb.clear(); memset(bit,0,sizeof(bit)); cout<<sumn+1<<endl; } return 0; }
最后
以上就是风中花生最近收集整理的关于2019杭电多校第9场1002 Rikka with Cake HDU66812019杭电多校第9场1002 Rikka with Cake HDU6681解法1：红黑树+思维+贪心解法2：树状数组+思维+贪心的全部内容，更多相关2019杭电多校第9场1002内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复