2017-2018 ACM-ICPC East Central North America Regional Contest (ECNA 2017) Solution
分类:
IT文章
•
2022-03-20 21:35:30
A：Abstract Art
题意：给出n个多边形，求n个多边形分别的面积和，以及面积并
思路：模板
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 1010
5 #define mkp make_pair
6 const double eps = 1e-12;
7
8 inline int sgn(double x)
9 {
10 if (fabs(x) < eps) return 0;
11 if (x < 0) return -1;
12 return 1;
13 }
14
15 struct Point
16 {
17 double x, y;
18 inline Point() {}
19 inline Point(double x, double y) : x(x), y(y) {}
20 inline void scan() { scanf("%lf%lf", &x, &y); }
21 inline bool operator == (const Point &b) const { return sgn(x - b.x) == 0 && sgn(y - b.y) == 0; }
22 inline bool operator < (const Point &b) const { return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x; }
23 inline Point operator - (const Point &b) const { return Point(x - b.x, y - b.y); }
24 inline double operator ^ (const Point &b) const { return x * b.y - y * b.x; }
25 inline double operator * (const Point &b) const { return x * b.x + y * b.y; }
26 };
27
28 inline double seg(Point O, Point A, Point B)
29 {
30 if (sgn(B.x - A.x) == 0) return (O.y - A.y) / (B.y - A.y);
31 return (O.x - A.x) / (B.x - A.x);
32 }
33
34 struct Polygon
35 {
36 int n;
37 Point p[30];
38 inline void scan(int _n)
39 {
40 n = _n;
41 for (int i = 0; i < n; ++i)
42 p[i].scan();
43 }
44 inline double getarea()
45 {
46 double sum = 0;
47 for (int i = 0; i < n; ++i)
48 sum += (p[i] ^ p[(i + 1) % n]);
49 return fabs(sum) / 2;
50 }
51 }poly[N];
52
53 int n;
54 pair <double, int> s[N];
55
56 inline double Polyunion(int n)
57 {
58 double res = 0;
59 for (int i = 1; i <= n; ++i)
60 {
61 int sz = poly[i].n;
62 for (int j = 0; j < sz; ++j)
63 {
64 int m = 0;
65 s[m++] = mkp(0, 0);
66 s[m++] = mkp(1, 0);
67 Point a = poly[i].p[j], b = poly[i].p[(j + 1) % sz];
68 for (int k = 1; k <= n; ++k)
69 {
70 if (i != k)
71 {
72 int sz2 = poly[k].n;
73 for (int ii = 0; ii < sz2; ++ii)
74 {
75 Point c = poly[k].p[ii], d = poly[k].p[(ii + 1) % sz2];
76 int c1 = sgn((b - a) ^ (c - a));
77 int c2 = sgn((b - a) ^ (d - a));
78 if (c1 == 0 && c2 == 0)
79 {
80 if (sgn((b - a) * (d - c)))
81 {
82 s[m++] = mkp(seg(c, a, b), 1);
83 s[m++] = mkp(seg(c, a, b), -1);
84 }
85 }
86 else
87 {
88 double s1 = (d - c) ^ (a - c);
89 double s2 = (d - c) ^ (b - c);
90 if (c1 >= 0 && c2 < 0) s[m++] = mkp(s1 / (s1 - s2), 1);
91 else if (c1 < 0 && c2 >= 0) s[m++] = mkp(s1 / (s1 - s2), -1);
92 }
93 }
94 }
95 }
96 sort(s, s + m);
97 double pre = min(max(s[0].first, 0.0), 1.0), now, sum = 0;
98 int cov = s[0].second;
99 for (int j = 1; j < m; ++j)
100 {
101 now = min(max(s[j].first, 0.0), 1.0);
102 if (!cov) sum += now - pre;
103 cov += s[j].second;
104 pre = now;
105 }
106 res += (a ^ b) * sum;
107 }
108 }
109 return fabs(res) / 2;
110 }
111
112
113 inline void Run()
114 {
115 while (scanf("%d", &n) != EOF)
116 {
117 double tot = 0;
118 for (int i = 1, m; i <= n; ++i)
119 {
120 scanf("%d", &m);
121 poly[i].scan(m);
122 tot += poly[i].getarea();
123 }
124 printf("%.10f %.10f
", tot, Polyunion(n));
125 }
126 }
127
128 int main()
129 {
130 #ifdef LOCAL
131 freopen("Test.in", "r", stdin);
132 #endif
133
134 Run();
135
136 return 0;
137 }
View Code
B：Craters
题意：给出若干个圆，求一个最小的围栏使得将所有圆围住，并且围栏离每个圆的边界至少有10个单位长度
思路：因为半径最多5000 先将半径+10，再将圆5000等分（也不一定5000， 足够大就可以），然后求凸包
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 2000010
5 #define mkp make_pair
6 const double eps = 1e-10;
7 const double PI = acos(-1.0);
8
9 inline int sgn(double x)
10 {
11 if (fabs(x) < eps) return 0;
12 if (x < 0) return -1;
13 return 1;
14 }
15
16 struct Point
17 {
18 double x, y;
19 inline Point() {}
20 inline Point(double x, double y) : x(x), y(y) {}
21 inline void scan() { scanf("%lf%lf", &x, &y); }
22 inline bool operator == (const Point &b) const { return sgn(x - b.x) == 0 && sgn(y - b.y) == 0; }
23 inline bool operator < (const Point &b) const { return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x; }
24 inline Point operator - (const Point &b) const { return Point(x - b.x, y - b.y); }
25 inline double operator ^ (const Point &b) const { return x * b.y - y * b.x; }
26 inline double operator * (const Point &b) const { return x * b.x + y * b.y; }
27 inline double distance(const Point &b) const { return hypot(x - b.x, y - b.y); }
28 };
29
30 struct Polygon
31 {
32 int n;
33 Point p[N];
34 inline void push(Point p0) { p[n++] = p0; }
35 struct cmp
36 {
37 Point p;
38 cmp(const Point &p0) { p = p0; }
39 inline bool operator () (const Point &aa, const Point &bb)
40 {
41 Point a = aa, b = bb;
42 int d = sgn((a - p) ^ (b - p));
43 if (d == 0)
44 return sgn(a.distance(p) - b.distance(p)) < 0;
45 return d > 0;
46 }
47 };
48 inline void norm()
49 {
50 Point mi = p[0];
51 for (int i = 1; i < n; ++i) mi = min(mi, p[i]);
52 sort(p, p + n, cmp(mi));
53 }
54 inline void getconvex(Polygon &convex)
55 {
56 sort(p, p + n);
57 convex.n = n;
58 for (int i = 0; i < min(n, 2); ++i)
59 convex.p[i] = p[i];
60 if (convex.n == 2 && (convex.p[0] == convex.p[1])) --convex.n;
61 if (n <= 2) return;
62 int &top = convex.n;
63 top = 1;
64 for (int i = 2; i < n; ++i)
65 {
66 while (top && sgn((convex.p[top] - p[i]) ^ (convex.p[top - 1] - p[i])) <= 0) --top;
67 convex.p[++top] = p[i];
68 }
69 int temp = top;
70 convex.p[++top] = p[n - 2];
71 for (int i = n - 3; i >= 0; --i)
72 {
73 while (top != temp && sgn((convex.p[top] - p[i]) ^ (convex.p[top - 1] - p[i])) <= 0)
74 --top;
75 convex.p[++top] = p[i];
76 }
77 if (convex.n == 2 && (convex.p[0] == convex.p[1])) --convex.n;
78 convex.norm();
79 }
80 inline double getarea()
81 {
82 double sum = 0;
83 for (int i = 0; i < n; ++i)
84 sum += (p[i] ^ p[(i + 1) % n]);
85 return fabs(sum) / 2;
86 }
87 inline double getcircumference()
88 {
89 double sum = 0;
90 for (int i = 0; i < n; ++i)
91 sum += p[i].distance(p[(i + 1) % n]);
92 return sum;
93 }
94 }poly, ans;
95
96 int n;
97
98 inline void Run()
99 {
100 while (scanf("%d", &n) != EOF)
101 {
102 double x, y, r; poly.n = 0;
103 for (int i = 1; i <= n; ++i)
104 {
105 scanf("%lf%lf%lf", &x, &y, &r); r += 10;
106 double angle = 0;
107 for (int j = 0; j <= 5000; ++j, angle += PI / 2500)
108 poly.push(Point(x + r * cos(angle), y + r * sin(angle)));
109 }
110 poly.getconvex(ans);
111 printf("%.10f
", ans.getcircumference());
112 }
113 }
114
115 int main()
116 {
117 #ifdef LOCAL
118 freopen("Test.in", "r", stdin);
119 #endif
120
121 Run();
122
123 return 0;
124 }
View Code
C：DRM Messages
水。
![]()
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 #define N 15010
6
7 char str[N];
8
9 int main()
10 {
11 while(~scanf("%s",str))
12 {
13 int len = strlen(str);
14 int tmp = 0;
15 int l = len / 2;
16 for(int i = 0; i < l; ++i)
17 {
18 tmp = (tmp + (str[i] - 'A')) % 26;
19 }
20 for(int i = 0; i < l; ++i)
21 {
22 str[i] = str[i] + tmp;
23 while(str[i] > 'Z')
24 {
25 str[i] -= 26;
26 }
27 }
28 tmp = 0;
29 for(int i = l; i < len; ++i)
30 {
31 tmp = (tmp + (str[i] - 'A')) % 26;
32 }
33 for(int i = l; i < len; ++i)
34 {
35 str[i] = str[i] + tmp;
36 while(str[i] > 'Z')
37 {
38 str[i] -= 26;
39 }
40 }
41 for(int i = 0; i < l; ++i)
42 {
43 str[i] = str[i] + str[i + l] - 'A';
44 while(str[i] > 'Z')
45 {
46 str[i] -= 26;
47 }
48 }
49 for(int i = 0; i < l; ++i)
50 {
51 putchar(str[i]);
52 }
53 printf("
");
54 }
55 return 0;
56 }
View Code
D - Game of Throwns
用栈维护。水。
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 int n, m;
6 string s;
7 stack<int>st;
8
9 inline int change(string s)
10 {
11 int i = (s[0] == '-');
12 int flag = (s[0] == '-');
13 int num = 0;
14 for(int len = s.length();i < len; ++i)
15 {
16 num = num * 10 + (s[i] - '0');
17 }
18 if(flag)
19 {
20 num = -num;
21 }
22 return num;
23 }
24
25 int main()
26 {
27 ios::sync_with_stdio(false);
28 cin.tie(0);
29 cout.tie(0);
30 while(cin >> n >> m)
31 {
32 while(!st.empty()) st.pop();
33 for(int i = 0; i < m; ++i)
34 {
35 cin >> s;
36 if(s == "undo")
37 {
38 int num;
39 cin >> num;
40 for(int j = 0; j < num; ++j)
41 {
42 if(!st.empty()) st.pop();
43 }
44 }
45 else
46 {
47 int num = change(s);
48 st.push(num);
49 }
50 }
51 int tmp = 0;
52 while(!st.empty())
53 {
54 int num = st.top();
55 tmp += num;
56 st.pop();
57 }
58 tmp = (tmp % n + n) % n;
59 cout << tmp << endl;
60 }
61 return 0;
62 }
View Code
E - Is-A? Has-A? Who Knowz-A?
题意：有两种关系，一种是 is-a 一种是 has-a 给出n对关系，然后有m次询问，回答询问的关系是否存在
思路：
如果 A is-a B B is-a C 那么 A is-a C
如果 A is-a B B has-a C 那么 A has-a C
假设is-a关系为0 has-a 关系为1
如果A 和 B 的关系为0 那么 A 和 B 后面所有的关系 都是 B 和其的关系
如果A 和 B 的关系为1，那么A 和 B 后面所有的关系都是1
然后对于每一个点，BFS预处理出它和其他点的关系
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 #define N 510
6
7 int link[N][N][2];
8
9 struct node{
10 int pos;
11 int flag;
12 inline node(){}
13 inline node(int pos, int flag) :pos(pos), flag(flag){};
14 };
15
16 string s1, s2, s3;
17 map<string,int>mp;
18 int cnt;
19 int n, m;
20 vector<node>vec[N];
21
22 inline void init()
23 {
24 memset(link, 0, sizeof link);
25 for(int i = 0; i < N; ++i) vec[i].clear();
26 mp.clear();
27 cnt = 1;
28 }
29
30 int main()
31 {
32 ios::sync_with_stdio(false);
33 cin.tie(0);
34 cout.tie(0);
35 while(cin >> n >> m)
36 {
37 init();
38 for(int i = 1; i <= n; ++i)
39 {
40 cin >> s1 >> s2 >> s3;
41 if(mp[s1] == 0) mp[s1] = cnt++;
42 if(mp[s3] == 0) mp[s3] = cnt++;
43 int id1 = mp[s1];
44 int id2 = mp[s3];
45 int f = 0;
46 if(s2[0] == 'h') f = 1;
47 vec[id1].push_back(node(id2, f));
48 }
49 for(int i = 1; i < cnt; ++i)
50 {
51 link[i][i][0] = 1;
52 queue<node>q;
53 q.push(node(i, 0));
54 while(!q.empty())
55 {
56 node st = q.front();
57 q.pop();
58 for(auto it : vec[st.pos])
59 {
60 if(link[i][it.pos][st.flag | it.flag]) continue;
61 link[i][it.pos][st.flag | it.flag] = 1;
62 q.push(node(it.pos, it.flag | st.flag));
63 }
64 }
65 }
66 for(int cas = 1; cas <= m; ++cas)
67 {
68 cin >> s1 >> s2 >> s3;
69 int id1 = mp[s1];
70 int id2 = mp[s3];
71 int f = 0;
72 if(s2[0] == 'h') f = 1;
73 cout << "Query " << cas << ": " << (link[id1][id2][f] ? "true" : "false") << endl;
74 }
75 }
76 return 0;
77 }
View Code
F - Keeping On Track
题意：给出n + 1 个点，n 条边，就是一棵树，然后求去除一个点，使得破坏的关系最多，并且挽留的关系最多
思路：DFS下去，然后对每一个点统计一下如果去除这个点，答案是多少，维护一下
![]()
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 #define N 100010
6 #define ll long long
7
8 struct Edge
9 {
10 int to, nx;
11 inline Edge() {}
12 inline Edge(int to, int nx) : to(to), nx(nx) {}
13 }edge[N << 1];
14
15 int n;
16 int head[N], pos;
17 ll cnt[N];
18 ll ans, remind;
19
20 inline void Init()
21 {
22 memset(head, -1, sizeof head);
23 memset(cnt, 0, sizeof cnt);
24 pos = 0; ans = 0; remind = 0;
25 }
26
27 inline void addedge(int u, int v)
28 {
29 edge[++pos] = Edge(v, head[u]); head[u] = pos;
30 edge[++pos] = Edge(u, head[v]); head[v] = pos;
31 }
32
33 inline void DFS(int u, int pre)
34 {
35 cnt[u] = 1;
36 vector <ll> vv;
37 for (int it = head[u]; ~it; it = edge[it].nx)
38 {
39 int v = edge[it].to;
40 if (v == pre) continue;
41 DFS(v, u);
42 cnt[u] += cnt[v];
43 vv.push_back(cnt[v]);
44 }
45 vv.push_back(n + 1 - cnt[u]);
46 sort(vv.begin(), vv.end());
47 ll tmp = 0;
48 for (int i = 0, len = vv.size(); i < len; ++i)
49 {
50 tmp += vv[i] * (n - vv[i]);
51 }
52 tmp /= 2;
53 if(tmp > ans)
54 {
55 ans = tmp;
56 int len = vv.size();
57 if(len > 1)
58 remind = vv[len - 1] * vv[len - 2];
59 }
60 else if(tmp == ans)
61 {
62 int len = vv.size();
63 if(len > 1)
64 remind = max(remind, vv[len - 1] * vv[len - 2]);
65 }
66 }
67
68 int main()
69 {
70 while (scanf("%d", &n) != EOF)
71 {
72 Init();
73 for (int i = 1, u, v; i <= n; ++i)
74 {
75 scanf("%d%d", &u, &v);
76 addedge(u, v);
77 }
78 DFS(0, -1);
79 printf("%lld %lld
", ans, ans - remind);
80 }
81 return 0;
82 }
View Code
G - A Question of Ingestion
题意：给定初始的胃口，和每天有的食物。如果第一天吃了东西，那么第二天的胃口下降到2/3 如果一天没吃，那么胃口恢复为3/2
如果连续两天都没吃，那么恢复为原来的
思路：有两种状态，吃或者不吃，记忆化搜索
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 typedef long long ll;
6
7 #define N 110
8
9 int dp[N][N][N];
10
11 int arr[N];
12 int brr[N];
13 int n, m;
14
15 inline int DFS(int cnt, int eat, int no)
16 {
17 if(cnt > n) return 0;
18 if(eat < 0) eat = 0;
19 if(dp[cnt][eat][no] != -1) return dp[cnt][eat][no];
20 //eat
21 int ans1 = min(brr[eat], arr[cnt]) + DFS(cnt + 1, eat + 1, 0);
22 //not eat
23 int ans2;
24 if(no)
25 {
26 ans2 = DFS(cnt + 1, 0, 1);
27 }
28 else
29 {
30 ans2 = DFS(cnt + 1, eat - 1, 1);
31 }
32 dp[cnt][eat][no] = max(ans1, ans2);
33 return dp[cnt][eat][no];
34 }
35
36 int main()
37 {
38 while(~scanf("%d %d", &n, &m))
39 {
40 memset(dp, -1, sizeof dp);
41 for(int i = 1; i <= n; ++i)
42 {
43 scanf("%d", &arr[i]);
44 }
45 brr[0] = m;
46 for(int i = 1; i < N; ++i) brr[i] = brr[i - 1] * 2 / 3;
47 int ans = DFS(1, 0, 0);
48 printf("%d
", ans);
49 }
50 return 0;
51 }
View Code
H - Sheba's Amoebas
题意：找连通块，八个方向
思路：DFS
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 #define N 110
6
7 int dir[][2] = {0,1,
8 1,0,
9 -1,0,
10 0,-1,
11 1,1,
12 1,-1,
13 -1,-1,
14 -1,1
15 };
16
17 int n, m;
18 char mp[N][N];
19
20 inline bool judge(int x,int y)
21 {
22 if(x < 1 || x > n || y < 1 || y > m || mp[x][y] == '.') return false;
23 else return true;
24 }
25
26 inline void DFS(int x,int y)
27 {
28 mp[x][y] = '.';
29 for(int i = 0 ; i < 8; ++i)
30 {
31 int dx = x + dir[i][0];
32 int dy = y + dir[i][1];
33 if(judge(dx, dy))
34 {
35 DFS(dx, dy);
36 }
37 }
38 }
39
40 int main()
41 {
42 while(~scanf("%d %d",&n ,&m))
43 {
44 for(int i = 1; i <= n; ++i)
45 {
46 for(int j = 1; j <= m; ++j)
47 {
48 scanf(" %c",&mp[i][j]);
49 }
50 }
51 int ans = 0;
52 for(int i = 1; i <= n; ++i)
53 {
54 for(int j = 1; j <= m; ++j)
55 {
56 if(mp[i][j] == '#')
57 {
58 ans++;
59 DFS(i, j);
60 }
61 }
62 }
63 printf("%d
",ans);
64 }
65 return 0;
66 }
View Code
I - Twenty Four, Again
留坑。
J - Workout for a Dumbbell
题意：有十个机器，Jim要在十个机器上工作三轮，对于每一个机器都有一个固定的工作时间以及工作之后需要的休息时间，然后每个机器还有另外一个工人要跟Jim抢机器，如果Jim要使用某一天机器的时候，刚好有工人要用或者在用，那么只能等工人用完Jim再用，求Jim工作三轮后需要的时间
思路：模拟一下，每次更新另外一个工人的起始时间，就可以判断当Jim要去用的时候，那个工人是在工作还是在休息了
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 #define N 100
6
7 const int n = 10;
8
9 typedef long long ll;
10
11 ll W[N], R[N], C[N], w[N], r[N], c[N], t[N];
12
13 int main()
14 {
15 for(int i = 1; i <= n; ++i)
16 {
17 scanf("%lld %lld", W + i, R + i);
18 C[i] = W[i] + R[i];
19 }
20 for(int i = 1; i <= n; ++i)
21 {
22 scanf("%lld %lld %lld",w + i, r + i, t + i);
23 c[i] = w[i] + r[i];
24 }
25 ll ans = 0;
26 for(int cnt = 1; cnt <= 3; ++cnt)
27 {
28 for(int i = 1; i <= n; ++i)
29 {
30 if(ans < t[i])
31 {
32 ans += C[i];
33 t[i] = max(t[i], ans - R[i]);
34 }
35 else
36 {
37 int tmp = (ans - t[i]) / c[i];
38 t[i] += tmp * c[i] + w[i];
39 if(ans < t[i]) ans = t[i];
40 ans += C[i];
41 t[i] = max(t[i] + r[i], ans - R[i]);
42 }
43 }
44 }
45 printf("%lld
", ans - R[n]);
46 return 0;
47 }
View Code
