比较不错的一套题，很多题挺有意思的～
Strange Billboard
经典思路了，枚举第一行的使用方法（2^16），然后推后面的方案。
Cell Phone
以每个点为圆心，r为半径画圆，问题转化为求被覆盖次数最多的区域次数。可以在每个圆上将相交的圆弧求出来，排序扫描，复杂度O(n^2logn)
CEOI06 Antenna有一种解法就是二分半径然后用这个方法来求最多能覆盖多少个点。
CODE
1
// Central Europe 2007, Cell Phone
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <cmath>
8#include <complex>
9
10using namespace std;
11
12typedef complex<double> Point;
13const int MaxN = 2000 + 100, MaxEvent = 2 * 2 * MaxN;
14const double eps = 1e-8, pi = 2.0 * acos(0.0);
15struct Event 
{
16
double arg;
17 bool add;
18
void set(double arg, bool add) {
19 this->arg = arg; this->add = add;
20
}
21
}e[MaxEvent];
22Point p[MaxN];
23int n, e_cnt;
24double r;
25
26void init();
27void work();
28void add_events(double a1, double a2);
29bool operator<(const Event &a, const Event &b);
30
31int main() {
32 for (; ;) {
33 scanf("%d%lf", &n, &r);
34 if (n == 0) break;
35 init();
36 work();
37 }
38 return 0;
39}
40
41void init() {
42 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
50void work() {
51 int ans = 0;
52 for (int i = 0; i < n; ++i) {
53 e_cnt = 0;
54 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 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
76void add_events(double a1, double a2) {
77 e[e_cnt++].set(a1, true);
78 e[e_cnt++].set(a2, false);
79}
80
81bool operator<(const Event &a, const Event &b) {
82 return a.arg < b.arg;
83}
84
85
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状态（类似于线段树的处理方法）
CODE
1// Central Europe 2007, Robotic Sort
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <algorithm>
8
9using namespace std;
10
11const int MaxN = 100000 + 100;
12struct SplayTreeNode {
13 SplayTreeNode *left, *right, *father;
14 int cnt;
15 bool deleted, rev;
16}tree[MaxN];
17int n;
18int s[MaxN], seq[MaxN];
19
20void init();
21void work();
22SplayTreeNode *make_tree(int begin, int end, SplayTreeNode *father);
23void splay(SplayTreeNode *p);
24bool my_cmp(int a, int b) {
25 return s[a] < s[b] || (s[a] == s[b] && a < b);
26}
27
28void 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
34SplayTreeNode *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
43 update(p); update(t);
44 return t;
45}
46
47SplayTreeNode *right_rotate(SplayTreeNode *p) {
48 SplayTreeNode *t = p->left;
49 p->left = t->right;
50 if (t->right) t->right->father = p;
51
52 t->father = p->father;
53 t->right = p;
54 p->father = t;
55
56 update(p); update(t);
57 return t;
58}
59
60SplayTreeNode *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
68SplayTreeNode *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
76SplayTreeNode *zigzig_left(SplayTreeNode *p, SplayTreeNode *fa, SplayTreeNode *grandfa) {
77 p->father = grandfa->father;
78
79 grandfa->left = fa->right;
80 if (fa->right) fa->right->father = grandfa;
81
82 fa->right = grandfa; grandfa->father = fa;
83
84 fa->left = p->right;
85 if (p->right) p->right->father = fa;
86
87 p->right = fa; fa->father = p;
88
89 update(grandfa); update(fa); update(p);
90}
91
92SplayTreeNode *zigzig_right(SplayTreeNode *p, SplayTreeNode *fa, SplayTreeNode *grandfa) {
93 p->father = grandfa->father;
94
95 grandfa->right = fa->left;
96 if (fa->left) fa->left->father = grandfa;
97
98 fa->left = grandfa; grandfa->father = fa;
99
100 fa->right = p->left;
101 if (p->left) p->left->father = fa;
102
103 p->left = fa; fa->father = p;
104
105 update(grandfa); update(fa); update(p);
106}
107
108int main() {
109 for (; ;) {
110 scanf("%d", &n);
111 if (n == 0) break;
112 init();
113 work();
114 }
115 return 0;
116}
117
118void 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
131void work() {
132 make_tree(0, n, NULL);
133
134 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 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
150SplayTreeNode *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
160 return &tree[s[mid]];
161}
162
163void apply_rev(SplayTreeNode *p) {
164 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
172void splay(SplayTreeNode *p) {
173 for (; p->father; ) {
174 SplayTreeNode *fa = p->father, *grandfa = fa->father;
175 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
184 SplayTreeNode *ggrandfa = grandfa->father;
185 if (ggrandfa != NULL) {
186 if (ggrandfa->left == grandfa) ggrandfa->left = p;
187 else ggrandfa->right = p;
188 }
189
190 if (grandfa->left == fa) {
191 if (fa->left == p) zigzig_left(p, fa, grandfa);
192 else zigzag_left(grandfa);
193 }
194 else {
195 if (fa->right == p) zigzig_right(p, fa, grandfa);
196 else zigzag_right(grandfa);
197 }
198
199 p->father = ggrandfa;
200
201 }
202
203 apply_rev(p);
204}
205
Tough Water Level重心关于含水量的高度是一个单峰函数（感觉比较像～），因此可以三分。
注意到由于厚度和宽度的函数是一个指定的函数，需要数值积分和表达式求值。
写起来还是有点麻烦的～