2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017) Solution

A. Drawing Borders

Unsolved.

B. Buildings

Unsolved.

C. Joyride

Upsolved.

题意：

在游乐园中，有n个游玩设施，有些设施之间有道路，给出每个设施需要花费的时间和价格，以及经过每条道路的时间，求从设施1出发恰好回到设施1恰好花费时间x的最小花费。

思路：

$dist[i][j] 表示第i个时刻到第j个点的最小花费从<t[1], 1> -> <x, 1>$

跑最短路即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 3010
 5 #define ll long long
 6 #define INF 0x3f3f3f3f3f3f3f3f
 7 int X, n, m, T, t[N], p[N]; 
 8 vector <int> G[N];
 9 
10 struct node
11 {
12     int x, to; ll w;
13     node () {}
14     node (int x, int to, ll w) : x(x), to(to), w(w) {}
15     bool operator < (const node &r) const { return w > r.w; }
16 };
17 
18 bool used[N][N]; 
19 ll dist[N][N];
20 void Dijkstra()
21 {
22     for (int i = 1; i <= X; ++i) for (int j = 1; j <= n; ++j) dist[i][j] = INF, used[i][j] = 0;
23     priority_queue <node> q; q.emplace(t[1], 1, 0); dist[t[1]][1] = p[1]; 
24     while (!q.empty())
25     {
26         int x = q.top().x, u = q.top().to; q.pop();
27         if (x > X) continue;
28         if (used[x][u]) continue;
29         used[x][u] = 1;
30         if (!used[x + t[u]][u] && dist[x + t[u]][u] > dist[x][u] + p[u]) 
31         {
32             dist[x + t[u]][u] = dist[x][u] + p[u];
33             q.emplace(x + t[u], u, dist[x + t[u]][u]);
34         }
35         for (auto v : G[u]) if (!used[x + t[v] + T][v] && dist[x + t[v] + T][v] > dist[x][u] + p[v])
36         {
37             dist[x + t[v] + T][v] = dist[x][u] + p[v];
38             q.emplace(x + t[v] + T, v, dist[x + t[v] + T][v]);
39         }
40     }    
41 }
42 
43 int main()
44 {
45     while (scanf("%d", &X) != EOF)
46     {
47         scanf("%d%d%d", &n, &m, &T);
48         for (int i = 1, u, v; i <= m; ++i)
49         {
50             scanf("%d%d", &u, &v);
51             G[u].push_back(v);
52             G[v].push_back(u);
53         }
54         for (int i = 1; i <= n; ++i) scanf("%d%d", t + i, p + i);
55         Dijkstra();
56         if (dist[X][1] == INF) puts("It is a trap.");
57         else printf("%lld
", dist[X][1]);
58     }
59     return 0; 
60 }

View Code

D. Pants On Fire

Solved.

题意：

给出一些关系，再给出一些关系的询问，对于询问给出三种结果。

思路：

Floyd求闭包，但是我还是想知道为什么拓扑排序不行，难道是题意读错，它不一定是个DAG?

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 410
 5 int n, m; 
 6 map <string, int> mp; int cnt; 
 7 char a[N], b[N];
 8 int G[N][N]; 
 9 
10 int getid(char *s)
11 {
12     if (mp.find(s) == mp.end()) mp[s] = ++cnt;
13     return mp[s];
14 }
15 
16 void Floyd()
17 {
18     for (int k = 1; k <= cnt; ++k)
19     {
20         for (int i = 1; i <= cnt; ++i)
21         {
22             for (int j = 1; j <= cnt; ++j)
23             {
24                 if (G[i][k] & G[k][j])
25                     G[i][j] = 1;
26             }
27         }
28     }
29 }
30 
31 void init()
32 {
33     memset(G, 0, sizeof G); 
34     mp.clear(); cnt = 0; 
35 }
36 
37 int main()
38 {
39     while (scanf("%d%d", &n, &m) != EOF)
40     {
41         init();
42         for (int i = 1, u, v; i <= n; ++i)
43         {
44             scanf("%s are worse than %s", a, b);
45             u = getid(a), v = getid(b);
46             G[u][v] = 1;
47         }
48         Floyd(); 
49         //for (auto it : mp) cout << it.first << " " << rt[it.second] << " " << deep[it.second] << endl;
50         for (int i = 1, u, v; i <= m; ++i)
51         {
52             scanf("%s are worse than %s", a, b);
53             u = getid(a), v = getid(b);
54             if (G[u][v] == 1) puts("Fact");
55             else if (G[v][u] == 1) puts("Alternative Fact");
56             else puts("Pants on Fire");
57         }
58     }
59     return 0;
60 }

View Code

E. Perpetuum Mobile

Upsolved.

题意：

有n个转换器，m个转换关系，转换关系是有向边

求从哪个点出发回到起点后经过的转换大于原来的值

思路：

枚举起点跑最长路，乘法可以取个$log$, 当然也可以再取个负跑最短路也可以

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 10010
 5 #define INF 0x3f3f3f3f
 6 #define pid pair <int, double>
 7 int n, m;
 8 vector <pid> G[N];
 9 
10 struct node
11 {
12     int to; double w;
13     node () {}
14     node (int to, double w) : to(to), w(w) {}
15     bool operator < (const node &r) const { return w < r.w; }
16 };
17 
18 double dist[N]; bool used[N];
19 bool Dijkstra(int st)
20 {
21     for (int i = 1; i <= n; ++i) dist[i] = 0.0, used[i] = false;
22     priority_queue <node> q; q.emplace(st, 0);  
23     while (!q.empty())
24     {
25         int u = q.top().to; q.pop(); 
26         if (used[u] && u == st && dist[u] > 0) return false;  
27         if (used[u]) continue;
28         used[u] = 1;
29         for (auto it : G[u]) if (dist[it.first] < dist[u] + log(it.second)) 
30         {
31             dist[it.first] = dist[u] + log(it.second);
32             q.emplace(it.first, dist[it.first]);
33         }
34     }    
35     return true;
36 }
37 
38 bool solve()
39 {
40     for (int i = 1; i <= n; ++i) if (Dijkstra(i) == false)
41         return false; 
42     return true;
43 }
44 
45 int main()
46 {
47     while (scanf("%d%d", &n, &m) != EOF)
48     {
49         for (int i = 1; i <= n; ++i) G[i].clear();
50         double w;
51         for (int i = 1, u, v; i <= m; ++i)
52         {
53             scanf("%d%d%lf", &u, &v, &w);
54             G[u].emplace_back(v, w);
55         }
56         if (solve() == false) printf("in");
57         puts("admissible");
58     }
59     return 0;
60 }

View Code

F. Plug It In

Unsolved.

题意：

给出一个匹配关系，可以设置一个人和三个人匹配，求最大匹配数。

思路：

先求最大匹配，再枚举每个插座，找增广路，枚举点的时候都要复制原图备份一下

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 1510
 5 int n, m, k;
 6 vector <int> G[N];
 7 int linker[N], vis[N], tmp[N];
 8 
 9 bool DFS(int u)
10 {
11     for (auto v : G[u]) if (!vis[v])
12     {
13         vis[v] = 1; 
14         if (linker[v] == -1 || DFS(linker[v]))
15         {
16             linker[v] = u;
17             return true;
18         }
19     }
20     return false;
21 }
22 
23 int main()
24 {
25     while (scanf("%d%d%d", &n, &m, &k) != EOF)
26     {
27         for (int i = 1; i <= n; ++i) G[i].clear();
28         for (int i = 1, u, v; i <= k; ++i)
29         {
30             scanf("%d%d", &u, &v);
31             G[u].push_back(v);
32         }
33         memset(linker, -1, sizeof linker);
34         int res = 0, ans = 0;
35         for (int i = 1; i <= n; ++i)
36         {
37             memset(vis, 0, sizeof vis);
38             if (DFS(i)) ++res;
39         }
40         memcpy(tmp, linker, sizeof linker);
41         for (int i = 1; i <= n; ++i)
42         {
43             int cnt = 0;
44             for (int j = 1; j <= 2; ++j)
45             {
46                 memset(vis, 0, sizeof vis);
47                 if (DFS(i)) ++cnt;    
48             }
49             ans = max(ans, cnt);
50             memcpy(linker, tmp, sizeof tmp);
51         }
52         printf("%d
", res + ans);
53     }
54     return 0;
55 }

View Code

G. Water Testing

Upsolved.

题意：求一个多边形内部整点个数。

思路：

皮克定理：$S = a + frac{b}{2} - 1 S表示多边形面积，frac{b}{2} 表示多边形边上的整点数 a 表示多边形内部整点数$

因为点是按顺序给出，有求面积公式$S = frac{1}{2} sum_{i = 0}^{i = n}|vec{P_i} x vec{P_i - 1}|$

再考虑线段上的整点个数为

$令 a = abs(stx - edx), b = abs(sty - edy)，整点个数为gcd(a, b) + 1$

考虑证明：

根据直线两点式有：

$y - y_1 = frac{y_2 - y_1}{x_2 - x_1} cdot (x - x _1)$

移项得

$y = frac{y_2 - y_1}{x_2 - x_1} cdot (x - x_1) + y_1$

即考虑有多少个$x使得 (x - x_1) equiv 0 pmod {x_2 - x_1}$

由于 $x 在 [x1, x2] 范围内那么 (x - x_1) 的范围即 [0, x2 - x1]$

$考虑 frac{y_2 - y_1}{x_2 - x_1} 可以跟他们的gcd约分$

$frac{x_2 - x_1}{ frac {x_2 - x_1}{gcd((y_2 - y_1), (x_2 - x_1))}} = gcd((y_2 - y_1), (x_2 - x_1))$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 100010
 5 #define ll long long
 6 int n; 
 7 ll x[N], y[N];
 8 
 9 ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}
10 
11 int main()
12 {
13     while (scanf("%d", &n) != EOF)
14     {
15         for (int i = 1; i <= n; ++i)
16             scanf("%lld%lld", x + i, y + i);
17         x[0] = x[n]; y[0] = y[n];
18         ll s = 0, b = 0;
19         for (int i = 1; i <= n; ++i)
20         {
21             s += x[i - 1] * y[i] - x[i] * y[i - 1];
22             ll A = abs(x[i] - x[i - 1]);
23             ll B = abs(y[i] - y[i - 1]);
24             b += gcd(A, B);
25         }
26         s = abs(s); 
27         printf("%lld
", (s - b + 2) >> 1);  
28     }
29     return 0;
30 }

View Code

H. Ratatoskr

Unsolved.

I. Uberwatch

Water.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 300010
 5 int n, m, x[N], Max[15];
 6 
 7 int main()
 8 {
 9     while (scanf("%d%d", &n, &m) != EOF)
10     {
11         memset(Max, 0, sizeof Max);
12         for (int i = 1; i <= n; ++i) scanf("%d", x + i);
13         for (int i = m + 1, res; i <= n; ++i)
14         {
15             res = x[i] + Max[m];
16             for (int j = m; j >= 1; --j) Max[j] = max(Max[j], Max[j - 1]);
17             Max[1] = max(Max[1], res);
18         }
19         printf("%d
", *max_element(Max + 1, Max + 1 + m));
20     }
21     return 0;
22 }

View Code

J. Word Clock

Unsolved.

K. You Are Fired

Water.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 10010
 5 int n, k, d;
 6 struct node
 7 {
 8     char s[10]; int c;
 9     void scan()
10     {
11         scanf("%s%d", s, &c);
12     }
13     bool operator < (const node &r) const {return c > r.c;}
14 }emp[N];
15 
16 int main()
17 {
18     while (scanf("%d%d%d", &n, &d, &k) != EOF)
19     {
20         for (int i = 1; i <= n; ++i) emp[i].scan();
21         sort(emp + 1, emp + 1 + n);
22         int tot = 0;
23         for (int i = 1; i <= k; ++i) tot += emp[i].c;
24         if (tot < d) puts("impossible");
25         else
26         {
27             printf("%d
", k);
28             for (int i = 1; i <= k; ++i) printf("%s, YOU ARE FIRED!
", emp[i].s);
29         }
30     }
31     return 0;
32 }

View Code