这套题比较。。。有意思。。。
Assemble据说是简单题
March of the Penguins你看相传每个ice floes是有跳的次数限制的是吧。。。用经典的拆点流量限制法，每个ice floes拆成i和i'，i到i'的流量上限为跳的次数，然后如果能从i跳到j连一条i'到j的边(流量无穷大)。。。点数好像有点多。。。不要客气～，dinic很快的～
Containers推一下式子，在实数意义下可以求最值是吧。然后现在限制整数。。。上下浮动一下吧。。。
| Youth Hostel Dorm
相当麻烦的状态压缩dp，还么写。。。
Escape from Enemy Territory
二分 + bfs应该可以，或者排个序 + 并查集
Flight Safety
比较麻烦的计算几何题。大体的想法是二分答案 + judge。得知了答案r以后我们可以把整个多边形往外膨胀r个单位然后判断是否整条路线都在里面。具体实现的时候我们把整个图形拆成原来的多边形，一堆矩形（每天边对应一个矩形）和一堆圆（每个点对应一个圆），每一部分求一下航线有哪些部分在里面，最后判断是否整条航线都被包含了。。。
  CODE
1 // Northwestern Europe 2007, Flight Safety
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <cmath>
8#include <vector>
9#include <algorithm>
10
11using namespace std;
12
13const double eps = 1e-8;
14struct Point  {
15 double x, y;
16  Point() {}
17 Point(double _x, double _y) : x(_x), y(_y) {}
18 bool operator<(const Point &p) const {
19 if (fabs(x - p.x) > eps) return x < p.x;
20 else return y < p.y;
21 }
22 double length_to(const Point &p) const {
23 return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
24 }
25 }oo(223456789.0, 897654321.0);
26
27double point_segment(const Point &p0, const Point &p1, const Point &p2);
28void adjust_len(double len, double &x, double &y);
29bool inside_segment(const Point &p0, const Point &p1, const Point &p2);
30bool seg_cross(const Point &a, const Point &b, const Point &c, const Point &d, Point &p);
31bool seg_cross(const Point &a, const Point &b, const Point &c, const Point &d);
32double cross(const Point &p0, const Point &p1, const Point &p2);
33
34struct Shape {
35 virtual bool inside(const Point &x) = 0;
36 virtual void append_segment(const Point &p0, const Point &p1, vector<pair<Point, Point> > &lst) = 0;
37};
38struct Circle : Shape {
39 Point o;
40 double r;
41 bool inside(const Point &x) {
42 return o.length_to(x) < r + eps;
43 }
44 void append_segment(const Point &p0, const Point &p1, vector<pair<Point, Point> > &lst) {
45 if (inside(p0) && inside(p1)) {
46 lst.push_back(make_pair(p0, p1));
47 return;
48 }
49
50 double dist = point_segment(o, p0, p1);
51 if (dist + eps > r) return;
52
53 double dx = -(p1.y - p0.y), dy = (p1.x - p0.x);
54 adjust_len(dist, dx, dy);
55 Point mid(o.x + dx, o.y + dy);
56
57 if (fabs(cross(p0, p1, mid)) > eps)
58 mid = Point(o.x - dx, o.y - dy);
59
60 dx = p1.x - p0.x; dy = p1.y - p0.y;
61 adjust_len(sqrt(r * r - dist * dist), dx, dy);
62 Point t1(mid.x + dx, mid.y + dy), t2(mid.x - dx, mid.y - dy);
63
64 bool in1 = inside_segment(t1, p0, p1), in2 = inside_segment(t2, p0, p1);
65 if (in1 && in2) lst.push_back(make_pair(t1, t2));
66 else if (in1 && (!in2)) lst.push_back(make_pair(p0, t1));
67 else if (in2 && (!in1)) lst.push_back(make_pair(t2, p1));
68 }
69};
70struct Polygon : Shape {
71 int n;
72 Point p[40];
73 bool inside(const Point &x) {
74 int cnt = 0;
75 for (int i = 0; i < n; ++i)
76 if (seg_cross(x, oo, p[i], p[i + 1])) ++cnt;
77 return cnt % 2;
78 }
79 void append_segment(const Point &p0, const Point &p1, vector<pair<Point, Point> > &lst) {
80 vector<Point> x;
81 x.push_back(p0); x.push_back(p1);
82 for (int i = 0; i < n; ++i) {
83 Point tmp;
84 if (seg_cross(p0, p1, p[i], p[i + 1], tmp)) {
85 x.push_back(tmp);
86 }
87 }
88
89 sort(x.begin(), x.end());
90 for (int i = 0; i + 1 < x.size(); ++i) {
91 Point mid((x[i].x + x[i + 1].x) / 2.0, (x[i].y + x[i + 1].y) / 2.0);
92 if (inside(mid))
93 lst.push_back(make_pair(x[i], x[i + 1]));
94 }
95
96 }
97};
98
99Polygon poly[30];
100Circle cir[30][30];
101Polygon rect[30][30];
102Point route[30];
103int c, n;
104
105void init();
106void work();
107bool judge_valid(double r);
108bool xy_cmp(double x0, double x1, double x2);
109int sgn(double x);
110
111int main() {
112 int t;
113 cin >> t;
114 for (; t > 0; --t) {
115 init();
116 work();
117 }
118 return 0;
119}
120
121void init() {
122 cin >> c >> n;
123 for (int i = 0; i < n; ++i)
124 cin >> route[i].x >> route[i].y;
125
126 for (int i = 0; i < c; ++i) {
127 cin >> poly[i].n;
128 for (int j = 0; j < poly[i].n; ++j)
129 cin >> poly[i].p[j].x >> poly[i].p[j].y;
130 poly[i].p[poly[i].n] = poly[i].p[0];
131 }
132}
133
134void work() {
135 const double Accurate = 1e-4;
136 double h = 0.0, t = 30000.0, mid = (h + t) / 2.0;
137 for (; h + Accurate < t; mid = (h + t) / 2.0) {
138 if (judge_valid(mid)) t = mid;
139 else h = mid;
140 }
141
142 printf("%.15lf\n", mid);
143}
144
145
146double point_segment(const Point &p0, const Point &p1, const Point &p2) {
147 return cross(p0, p1, p2) / p1.length_to(p2);
148}
149
150void adjust_len(double len, double &x, double &y) {
151 double ratio = len / sqrt(x * x + y * y);
152 x *= ratio; y *= ratio;
153}
154
155bool inside_segment(const Point &p0, const Point &p1, const Point &p2) {
156 if (fabs(p2.x - p1.x) > fabs(p2.y - p1.y))
157 return xy_cmp(p0.x, p1.x, p2.x);
158 else
159 return xy_cmp(p0.y, p1.y, p2.y);
160}
161
162bool seg_cross(const Point &a, const Point &b, const Point &c, const Point &d, Point &p) {
163 double s1 = cross(a, b, c), s2 = cross(a, b, d), s3 = cross(c, d, a), s4 = cross(c, d, b);
164 int d1 = sgn(s1), d2 = sgn(s2), d3 = sgn(s3), d4 = sgn(s4);
165
166 if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) {
167 p.x = (c.x * s2 - d.x * s1) / (s2 - s1);
168 p.y = (c.y * s2 - d.y * s1) / (s2 - s1);
169 return true;
170 }
171
172 return false;
173}
174
175bool seg_cross(const Point &a, const Point &b, const Point &c, const Point &d) {
176 double s1 = cross(a, b, c), s2 = cross(a, b, d), s3 = cross(c, d, a), s4 = cross(c, d, b);
177 int d1 = sgn(s1), d2 = sgn(s2), d3 = sgn(s3), d4 = sgn(s4);
178
179 return ((d1 ^ d2) == -2 && (d3 ^ d4) == -2);
180}
181
182double cross(const Point &p0, const Point &p1, const Point &p2) {
183 return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
184}
185
186bool judge_valid(double r) {
187 // Initialize rectangles & circles
188 for (int i = 0; i < c; ++i) {
189 for (int j = 0; j < poly[i].n; ++j) {
190 Point &p0 = poly[i].p[j], &p1 = poly[i].p[j + 1];
191 double dx = -(p1.y - p0.y), dy = p1.x - p0.x;
192 adjust_len(r, dx, dy);
193
194 rect[i][j].n = 4;
195 rect[i][j].p[0] = Point(p0.x + dx, p0.y + dy);
196 rect[i][j].p[1] = Point(p0.x - dx, p0.y - dy);
197 rect[i][j].p[2] = Point(p1.x - dx, p1.y - dy);
198 rect[i][j].p[3] = Point(p1.x + dx, p1.y + dy);
199 rect[i][j].p[4] = rect[i][j].p[0];
200
201 cir[i][j].o = poly[i].p[j];
202 cir[i][j].r = r;
203 }
204 }
205
206
207
208 // Judge all the segments
209 for (int i = 0; i < n - 1; ++i) {
210 vector<pair<Point, Point> > lst;
211 for (int j = 0; j < c; ++j) {
212 poly[j].append_segment(route[i], route[i + 1], lst);
213 for (int k = 0; k < poly[j].n; ++k) {
214 rect[j][k].append_segment(route[i], route[i + 1], lst);
215 cir[j][k].append_segment(route[i], route[i + 1], lst);
216 }
217
218 }
219
220 static pair<double, double> tmp[10000];
221 int tmp_cnt = 0;
222 double b;
223
224 if (fabs(route[i].x - route[i + 1].x) > fabs(route[i].y - route[i + 1].y)) {
225 b = fabs(route[i + 1].x - route[i].x);
226 for (vector<pair<Point, Point> >::iterator it = lst.begin(); it != lst.end(); ++it) {
227 tmp[tmp_cnt].first = fabs(it->first.x - route[i].x);
228 tmp[tmp_cnt].second = fabs(it->second.x - route[i].x);
229 ++tmp_cnt;
230 }
231 }
232 else {
233 b = fabs(route[i + 1].y - route[i].y);
234 for (vector<pair<Point, Point> >::iterator it = lst.begin(); it != lst.end(); ++it) {
235 tmp[tmp_cnt].first = fabs(it->first.y - route[i].y);
236 tmp[tmp_cnt].second = fabs(it->second.y - route[i].y);
237 ++tmp_cnt;
238 }
239 }
240
241
242 // Whether the segment is covered
243 for (int j = 0; j < tmp_cnt; ++j)
244 if (tmp[j].first > tmp[j].second) swap(tmp[j].first, tmp[j].second);
245 sort(tmp, tmp + tmp_cnt);
246 if (tmp[0].first > eps) return false;
247 double tail = tmp[0].second;
248 for (int j = 1; j < tmp_cnt; ++j) {
249 if (tail + eps < tmp[j].first) return false;
250 tail >?= tmp[j].second;
251 if (tail + eps > b) break;
252 }
253 if (tail + eps < b) return false;
254
255 }
256
257
258 return true;
259}
260
261bool xy_cmp(double x0, double x1, double x2) {
262 if (x1 < x2)
263 return (x1 < x0 + eps && x0 < x2 + eps);
264 else
265 return (x2 < x0 + eps && x0 < x1 + eps);
266}
267
268int sgn(double x) {
269 return x > eps ? 1 : (x < -eps ? -1 : 0);
270}
271
272
273
Summits
一道比较经典的思路题了，大体就是按照高度从高往低处理，每次合并当前高度和它周围的比它低的。最后判断每一块中能达到的最高的。
注意我合并的时候使用树形并查集，并且严格保证把低的合并到高的。。。处理的要自仔细考虑细节。
CODE
1// Northwestern Europe 2007, Summits
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <vector>
8#include <algorithm>
9
10using namespace std;
11
12const int MaxN = 500 + 10;
13const int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
14int s[MaxN * MaxN];
15int h, w, diff_h[MaxN * MaxN], diff_h_cnt;
16vector<int> grid_of_h[MaxN * MaxN];
17int father[MaxN * MaxN], ans;
18int delta;
19
20void init();
21void work();
22int find_root(int u);
23void unite(int u, int v);
24bool is_valid(int x, int y);
25void check_height(int id);
26
27int main() {
28 int t;
29 scanf("%d", &t);
30 for (; t > 0; --t) {
31 init();
32 work();
33 }
34 return 0;
35}
36
37void init() {
38 scanf("%d%d%d", &h, &w, &delta);
39
40 diff_h_cnt = 0;
41 for (int i = 0; i < h; ++i)
42 for (int j = 0; j < w; ++j) {
43 scanf("%d", &s[i * w + j]);
44 diff_h[diff_h_cnt++] = s[i * w + j];
45
46 }
47
48 sort(diff_h, diff_h + diff_h_cnt);
49 diff_h_cnt = unique(diff_h, diff_h + diff_h_cnt) - diff_h;
50
51 for (int i = 0; i < diff_h_cnt; ++i)
52 grid_of_h[i].clear();
53 for (int i = 0; i < h; ++i)
54 for (int j = 0; j < w; ++j) {
55 grid_of_h[lower_bound(diff_h, diff_h + diff_h_cnt, s[i * w + j]) - diff_h].push_back(i * w + j);
56 }
57
58}
59
60void work() {
61 for (int i = 0; i < w * h; ++i)
62 father[i] = i;
63
64 ans = w * h;
65 int p = diff_h_cnt - 1;
66
67 for (int i = diff_h_cnt - 1; i >= 0; --i) {
68 for (vector<int>::iterator it = grid_of_h[i].begin(); it != grid_of_h[i].end(); ++it) {
69 int x = *it / w, y = *it % w;
70 for (int d = 0; d < 4; ++d) {
71 int nx = x + dx[d], ny = y + dy[d];
72 if (is_valid(nx, ny) && s[nx * w + ny] >= s[x * w + y]) {
73 unite(find_root(nx * w + ny), find_root(x * w + y));
74 }
75 }
76 }
77
78 for (; diff_h[p] >= diff_h[i] + delta; --p) {
79 continue;
80 }
81 if (i == 0) continue;
82
83 for (; p >= 0 && diff_h[p] >= diff_h[i - 1] + delta; --p) {
84 check_height(p);
85 }
86
87 }
88
89 for (; p >= 0; --p)
90 check_height(p);
91
92 cout << ans << endl;
93}
94
95int find_root(int u) {
96 int q = u;
97 for (; q != father[q]; )
98 q = father[q];
99 for (; u != father[u]; ) {
100 int tmp = father[u];
101 father[u] = q;
102 u = tmp;
103 }
104 return q;
105}
106
107void unite(int u, int v) {
108 if (s[u] < s[v]) father[u] = v;
109 else father[v] = u;
110}
111
112bool is_valid(int x, int y) {
113 return x >= 0 && x < h && y >= 0 && y < w;
114}
115
116void check_height(int id) {
117 for (vector<int>::iterator it = grid_of_h[id].begin(); it != grid_of_h[id].end(); ++it)
118 if (s[find_root(*it)] > s[*it]) {
119 --ans;
120 }
121}
122
123
124
125
126
Obfuscation
字典树 + dp
Tower Parking
简单的模拟题
Walk
非常有趣的一道题。
首先我们在两点拉一条线，观察每一个封闭等高线被经过的次数。
如果某条等高线被经过偶数次，那么两点同在线内或线外，必然有办法不经过这条线。
如果经过奇数次，那么在不同侧，必须要经过一次，并且总可以有办法只经过一次。
接下来要确定经过等高线的次序。基本想法是这个顺序是唯一的，我是以最左边交到的点作为次序来排的。。。
另外关于刚好交在端点的情况需要考虑下。。。
CODE
1// Northwestern Europe 2007, Walk
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <vector>
8#include <cmath>
9#include <algorithm>
10
11using namespace std;
12
13struct Point {
14 double x, y;
15};
16const int MaxN = 3000 + 100;
17const double eps = 1e-8;
18vector<Point> poly[MaxN];
19int h[MaxN];
20int n, intersect_cnt[MaxN];
21double left_most[MaxN];
22
23void init();
24void work();
25bool my_cmp(int a, int b) {
26 return left_most[a] < left_most[b];
27}
28
29int main() {
30
31 //freopen("in.txt", "r", stdin);
32
33 int t;
34 scanf("%d", &t);
35 for (; t > 0; --t) {
36 init();
37 work();
38 }
39
40 return 0;
41}
42
43void init() {
44 scanf("%d", &n);
45 for (int i = 0; i < n; ++i) {
46 scanf("%d", &h[i]);
47 int pn;
48 scanf("%d", &pn);
49 poly[i].resize(pn + 1);
50 for (int j = 0; j < pn; ++j) {
51 scanf("%lf%lf", &poly[i][j].x, &poly[i][j].y);
52 }
53 poly[i][pn] = poly[i][0];
54
55 }
56}
57
58void work() {
59 fill(intersect_cnt, intersect_cnt + n, 0);
60 fill(left_most, left_most + n, 1e100);
61
62 for (int i = 0; i < n; ++i) {
63 for (int j = 0; j + 1 < poly[i].size(); ++j) {
64 double x1 = poly[i][j].x, y1 = poly[i][j].y, x2 = poly[i][j + 1].x, y2 = poly[i][j + 1].y;
65 if (fabs(y1 - y2) < eps) continue;
66 if (y1 > y2) {
67 swap(x1, x2); swap(y1, y2);
68 }
69 double y = 0.0;
70 if (!(y1 < y + eps && y + eps < y2)) continue;
71 double x = x1 + (y - y1) * (x2 - x1) / (y2 - y1);
72 if (x < 0.0 || x > 100000.0) continue;
73
74 ++intersect_cnt[i];
75 left_most[i] <?= x;
76 }
77 }
78
79 int seq[MaxN];
80 for (int i = 0; i < n; ++i) seq[i] = i;
81 sort(seq, seq + n, my_cmp);
82 int pre_h = -1;
83 int up_cnt = 0, down_cnt = 0;
84 for (int i = 0; i < n; ++i) {
85 if (intersect_cnt[seq[i]] % 2 == 0) continue;
86 if (pre_h == h[seq[i]]) continue;
87 if (pre_h != -1)
88 if (pre_h < h[seq[i]]) up_cnt += h[seq[i]] - pre_h;
89 else down_cnt += pre_h - h[seq[i]];
90 pre_h = h[seq[i]];
91 }
92
93 printf("%d %d\n", up_cnt, down_cnt);
94}
95
|