比较不错的一套题,很多题挺有意思的~
Strange Billboard
经典思路了,枚举第一行的使用方法(2^16),然后推后面的方案。
Cell Phone
以每个点为圆心,r为半径画圆,问题转化为求被覆盖次数最多的区域次数。可以在每个圆上将相交的圆弧求出来,排序扫描,复杂度O(n^2logn)
CEOI06 Antenna有一种解法就是二分半径然后用这个方法来求最多能覆盖多少个点。
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
CODE
1
// Central Europe 2007, Cell Phone
2
// Written By FreePeter
3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
#include <cstdio>
5
#include <cstring>
6
#include <iostream>
7
#include <cmath>
8
#include <complex>
9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
10
using namespace std;
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
typedef complex<double> Point;
13
const int MaxN = 2000 + 100, MaxEvent = 2 * 2 * MaxN;
14
const double eps = 1e-8, pi = 2.0 * acos(0.0);
15![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct Event
{
16
double arg;
17
bool add;
18![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void set(double arg, bool add)
{
19
this->arg = arg; this->add = add;
20
}
21
}e[MaxEvent];
22
Point p[MaxN];
23
int n, e_cnt;
24
double r;
25![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
26
void init();
27
void work();
28
void add_events(double a1, double a2);
29
bool operator<(const Event &a, const Event &b);
30![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (; ;)
{
33
scanf("%d%lf", &n, &r);
34
if (n == 0) break;
35
init();
36
work();
37
}
38
return 0;
39
}
40![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void init()
{
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int i = 0; i < n; ++i)
{
43
double x, y;
44
scanf("%lf%lf", &x, &y);
45
p[i] = Point(x, y);
46
}
47
r += 0.001;
48
}
49![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
50![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void work()
{
51
int ans = 0;
52![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int i = 0; i < n; ++i)
{
53
e_cnt = 0;
54![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int j = 0; j < n; ++j)
{
55
if (j == i) continue;
56
if (abs(p[i] - p[j]) + eps > 2.0 * r) continue;
57
double a = arg(p[j] - p[i]), dis = abs(p[j] - p[i]), delta = acos(dis / 2.0 / r);
58
double a1 = a - delta, a2 = a + delta;
59
add_events(a1, a2);
60
}
61
62
if (e_cnt < ans) continue;
63
sort(e, e + e_cnt);
64
int cnt = 0;
65![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int i = 0; i < e_cnt; ++i)
{
66
if (e[i].add) ++cnt;
67
else --cnt;
68
ans >?= cnt;
69
}
70
}
71
72
++ans;
73
printf("It is possible to cover %d points.\n", ans);
74
}
75![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
76![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void add_events(double a1, double a2)
{
77
e[e_cnt++].set(a1, true);
78
e[e_cnt++].set(a2, false);
79
}
80![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
81![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool operator<(const Event &a, const Event &b)
{
82
return a.arg < b.arg;
83
}
84![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
85![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Hexagonal ParcelsEuclid空间上的Steiner树有一个性质就是n个点,增加的点不超过n-2个。然后这道题有点Steiner树的感觉,然后我们就猜增加的点至多2个,求最小生成树。。。然后就对了。不会严密证明。
标程的另一种做法是基于状态压缩的DP好像,没看懂。。。
Key Task简单的BFS题。
Gates of Logic很麻烦的处理题,暂时没做。
Weird Numbers负进制转换。用类似于正进制的方法做,每次保证余数在[0,b)范围内即可。
证明如下:
设我们要转-b进制,先得到b进制表达式
N = an*b^n + an-1 * b^(n-1) + ... + a0*b^0
注意到p为偶数时,ap*b^p = ap * (-b)^p
p为奇数时,ap*b^p = 1*(-b)^(p+1) + (b - ap) * (-b)^p
~~~
Rectangular Polygon由于Polygon的特殊性,我们拉一条平行于x或y轴的直线,则上面一定经过偶数个顶点,并且连边一定是0-1, 2-3……
这样可以construct出边来,判断方向可以使用有向面积(即按照当前方向走一遍算面积,根据面积的正负号来判断是否需要reverse)
参见SGU 128, Snake
Reaux! Sham! Beaux!简单题
Robotic Sort需要支持定位某个数和将某一段reverse两种操作,可以使用分块处理或者splay_tree。
因为是按照从小到大的顺序把数依次归位的,所以我们可以理解为每次将这个数归位后就把这个数删掉,每次就是reverse从头开始的一段,这样可以减少常数 & 编程复杂度。
用splay_tree的主要想法就是利用树的中序遍历来表示序列。利用SplayTree的spaly操作,设当前要归位的元素为x,把x splay到根,标记根左边节点为reverse,并删除根。
SplayTree的节点需要维护cnt和rev域。在遍历树的时候需要应用父节点的rev状态(类似于线段树的处理方法)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
CODE
1
// Central Europe 2007, Robotic Sort
2
// Written By FreePeter
3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
#include <cstdio>
5
#include <cstring>
6
#include <iostream>
7
#include <algorithm>
8![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
9
using namespace std;
10![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
11
const int MaxN = 100000 + 100;
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct SplayTreeNode
{
13
SplayTreeNode *left, *right, *father;
14
int cnt;
15
bool deleted, rev;
16
}tree[MaxN];
17
int n;
18
int s[MaxN], seq[MaxN];
19![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
20
void init();
21
void work();
22
SplayTreeNode *make_tree(int begin, int end, SplayTreeNode *father);
23
void splay(SplayTreeNode *p);
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool my_cmp(int a, int b)
{
25
return s[a] < s[b] || (s[a] == s[b] && a < b);
26
}
27![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
28![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void update(SplayTreeNode *p)
{
29
p->cnt = (p->deleted ? 0 : 1);
30
if (p->left) p->cnt += p->left->cnt;
31
if (p->right) p->cnt += p->right->cnt;
32
}
33![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
34![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
SplayTreeNode *left_rotate(SplayTreeNode *p)
{
35
SplayTreeNode *t = p->right;
36
p->right = t->left;
37
if (t->left) t->left->father = p;
38
39
t->father = p->father;
40
t->left = p;
41
p->father = t;
42![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
43
update(p); update(t);
44
return t;
45
}
46![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
SplayTreeNode *right_rotate(SplayTreeNode *p)
{
48
SplayTreeNode *t = p->left;
49
p->left = t->right;
50
if (t->right) t->right->father = p;
51![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
52
t->father = p->father;
53
t->right = p;
54
p->father = t;
55![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
56
update(p); update(t);
57
return t;
58
}
59![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
60![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
SplayTreeNode *zigzag_left(SplayTreeNode *p)
{
61
SplayTreeNode *t = left_rotate(p->left);
62
p->left = t;
63
if (t) t->father = p;
64
65
return right_rotate(p);
66
}
67![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
68![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
SplayTreeNode *zigzag_right(SplayTreeNode *p)
{
69
SplayTreeNode *t = right_rotate(p->right);
70
p->right = t;
71
if (t) t->father = p;
72
73
return left_rotate(p);
74
}
75![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
76![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
SplayTreeNode *zigzig_left(SplayTreeNode *p, SplayTreeNode *fa, SplayTreeNode *grandfa)
{
77
p->father = grandfa->father;
78![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
79
grandfa->left = fa->right;
80
if (fa->right) fa->right->father = grandfa;
81![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
82
fa->right = grandfa; grandfa->father = fa;
83
84
fa->left = p->right;
85
if (p->right) p->right->father = fa;
86![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
87
p->right = fa; fa->father = p;
88![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
89
update(grandfa); update(fa); update(p);
90
}
91![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
92![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
SplayTreeNode *zigzig_right(SplayTreeNode *p, SplayTreeNode *fa, SplayTreeNode *grandfa)
{
93
p->father = grandfa->father;
94![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
95
grandfa->right = fa->left;
96
if (fa->left) fa->left->father = grandfa;
97![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
98
fa->left = grandfa; grandfa->father = fa;
99
100
fa->right = p->left;
101
if (p->left) p->left->father = fa;
102![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
103
p->left = fa; fa->father = p;
104![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
105
update(grandfa); update(fa); update(p);
106
}
107
108![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
109![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (; ;)
{
110
scanf("%d", &n);
111
if (n == 0) break;
112
init();
113
work();
114
}
115
return 0;
116
}
117![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
118![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void init()
{
119
for (int i = 0; i < n; ++i)
120
scanf("%d", &s[i]);
121
122
// Make the sequence to be a permutation
123
// Hence our goal is to change the permutation into (0, 1, 2,
n - 1)
124
for (int i = 0; i < n; ++i)
125
seq[i] = i;
126
sort(seq, seq + n, my_cmp);
127
for (int i = 0; i < n; ++i)
128
s[seq[i]] = i;
129
}
130![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
131![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void work()
{
132
make_tree(0, n, NULL);
133![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
134![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int i = 0; i < n; ++i)
{
135
splay(&tree[i]);
136
137
int relative_pos = (tree[i].left == NULL ? 0 : tree[i].left->cnt);
138
printf("%d", relative_pos + i + 1);
139
140
// Reverse the left internal & delete the node
141![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (tree[i].left != NULL)
{
142
tree[i].left->rev = !tree[i].left->rev;
143
}
144
tree[i].deleted = true; --tree[i].cnt;
145
if (i != n - 1) printf(" ");
146
}
147
printf("\n");
148
}
149![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
150![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
SplayTreeNode *make_tree(int begin, int end, SplayTreeNode *father)
{
151
if (begin == end) return NULL;
152
int mid = (begin + end) / 2;
153
tree[s[mid]].left = make_tree(begin, mid, &tree[s[mid]]);
154
tree[s[mid]].right = make_tree(mid + 1, end, &tree[s[mid]]);
155
tree[s[mid]].cnt = end - begin;
156
tree[s[mid]].father = father;
157
tree[s[mid]].deleted = false;
158
tree[s[mid]].rev = false;
159![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
160
return &tree[s[mid]];
161
}
162![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
163![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void apply_rev(SplayTreeNode *p)
{
164![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (p->rev)
{
165
swap(p->left, p->right);
166
if (p->left) p->left->rev = !p->left->rev;
167
if (p->right) p->right->rev = !p->right->rev;
168
p->rev = false;
169
}
170
}
171![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
172![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void splay(SplayTreeNode *p)
{
173![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (; p->father; )
{
174
SplayTreeNode *fa = p->father, *grandfa = fa->father;
175![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (!grandfa)
{
176
apply_rev(fa); apply_rev(p);
177
if (fa->left == p) right_rotate(fa);
178
else left_rotate(fa);
179
break;
180
}
181
182
apply_rev(grandfa); apply_rev(fa); apply_rev(p);
183![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
184
SplayTreeNode *ggrandfa = grandfa->father;
185![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (ggrandfa != NULL)
{
186
if (ggrandfa->left == grandfa) ggrandfa->left = p;
187
else ggrandfa->right = p;
188
}
189
190![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (grandfa->left == fa)
{
191
if (fa->left == p) zigzig_left(p, fa, grandfa);
192
else zigzag_left(grandfa);
193
}
194![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
195
if (fa->right == p) zigzig_right(p, fa, grandfa);
196
else zigzag_right(grandfa);
197
}
198![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
199
p->father = ggrandfa;
200![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
201
}
202![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
203
apply_rev(p);
204
}
205![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Tough Water Level重心关于含水量的高度是一个单峰函数(感觉比较像~),因此可以三分。
注意到由于厚度和宽度的函数是一个指定的函数,需要数值积分和表达式求值。
写起来还是有点麻烦的~