比較不錯(cuò)的一套題，很多題挺有意思的～
Strange Billboard
經(jīng)典思路了，枚舉第一行的使用方法（2^16），然后推后面的方案。
Cell Phone
以每個(gè)點(diǎn)為圓心，r為半徑畫圓，問題轉(zhuǎn)化為求被覆蓋次數(shù)最多的區(qū)域次數(shù)。可以在每個(gè)圓上將相交的圓弧求出來，排序掃描，復(fù)雜度O(n^2logn)
CEOI06 Antenna有一種解法就是二分半徑然后用這個(gè)方法來求最多能覆蓋多少個(gè)點(diǎn)。
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樹有一個(gè)性質(zhì)就是n個(gè)點(diǎn)，增加的點(diǎn)不超過n-2個(gè)。然后這道題有點(diǎn)Steiner樹的感覺，然后我們就猜增加的點(diǎn)至多2個(gè)，求最小生成樹。。。然后就對(duì)了。不會(huì)嚴(yán)密證明。
標(biāo)程的另一種做法是基于狀態(tài)壓縮的DP好像，沒看懂。。。
Key Task簡(jiǎn)單的BFS題。
Gates of Logic很麻煩的處理題，暫時(shí)沒做。
Weird Numbers負(fù)進(jìn)制轉(zhuǎn)換。用類似于正進(jìn)制的方法做，每次保證余數(shù)在[0,b)范圍內(nèi)即可。
證明如下：
設(shè)我們要轉(zhuǎn)-b進(jìn)制，先得到b進(jìn)制表達(dá)式
N = an*b^n + an-1 * b^(n-1) + ... + a0*b^0
注意到p為偶數(shù)時(shí)，ap*b^p = ap * (-b)^p
p為奇數(shù)時(shí)，ap*b^p = 1*(-b)^(p+1) + (b - ap) * (-b)^p
~~~
Rectangular Polygon由于Polygon的特殊性，我們拉一條平行于x或y軸的直線，則上面一定經(jīng)過偶數(shù)個(gè)頂點(diǎn)，并且連邊一定是0-1, 2-3……
這樣可以construct出邊來，判斷方向可以使用有向面積（即按照當(dāng)前方向走一遍算面積，根據(jù)面積的正負(fù)號(hào)來判斷是否需要reverse）
參見SGU 128, Snake
Reaux! Sham! Beaux!簡(jiǎn)單題
Robotic Sort需要支持定位某個(gè)數(shù)和將某一段reverse兩種操作，可以使用分塊處理或者splay_tree。
因?yàn)槭前凑諒男〉酱蟮捻樞虬褦?shù)依次歸位的，所以我們可以理解為每次將這個(gè)數(shù)歸位后就把這個(gè)數(shù)刪掉，每次就是reverse從頭開始的一段，這樣可以減少常數(shù) & 編程復(fù)雜度。
用splay_tree的主要想法就是利用樹的中序遍歷來表示序列。利用SplayTree的spaly操作，設(shè)當(dāng)前要?dú)w位的元素為x，把x splay到根，標(biāo)記根左邊節(jié)點(diǎn)為reverse，并刪除根。
SplayTree的節(jié)點(diǎn)需要維護(hù)cnt和rev域。在遍歷樹的時(shí)候需要應(yīng)用父節(jié)點(diǎn)的rev狀態(tài)（類似于線段樹的處理方法）
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重心關(guān)于含水量的高度是一個(gè)單峰函數(shù)（感覺比較像～），因此可以三分。
注意到由于厚度和寬度的函數(shù)是一個(gè)指定的函數(shù)，需要數(shù)值積分和表達(dá)式求值。
寫起來還是有點(diǎn)麻煩的～