ACM/ICPC Central Europe 2007 解题报告

比较不错的一套题，很多题挺有意思的～

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 Parcels
Euclid空间上的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
重心关于含水量的高度是一个单峰函数（感觉比较像～），因此可以三分。
注意到由于厚度和宽度的函数是一个指定的函数，需要数值积分和表达式求值。
写起来还是有点麻烦的～

Comments

Article rating:
Your rating:

Categories

Based on community consensus.

Activity for this knol

This week:

13pageviews

Totals:

474pageviews
©2009 Google