AISing Programming Contest 2019 Solution

A - Bulletin Board

签到。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int n, h, w;
 7     while (scanf("%d%d%d", &n, &h, &w) != EOF)
 8     {
 9         printf("%d
", (n - h + 1) * (n - w + 1));
10     }
11     return 0;
12 }

View Code

B - Contests

签到。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 110
 5 int n, a, b, p[N];
 6 
 7 bool check(int x)
 8 {
 9     if (n - x + 1 <= x) return false;
10     if (p[x] > a) return false;
11     if (p[n - x + 1] <= b) return false;
12     int cnt = 0;
13     for (int i = x + 1, j = 1; j <= x && i <= n - x; ++i)
14     {
15         if (p[i] > b) break;
16         if (p[i] > a) 
17         {
18             ++j;
19             ++cnt;
20         }
21     }
22     return cnt >= x;
23 }
24 
25 int main()
26 {
27     while (scanf("%d", &n) != EOF)
28     {
29         scanf("%d%d", &a, &b);
30         for (int i = 1; i <= n; ++i) scanf("%d", p + i);
31         sort(p + 1, p + 1 + n);
32         int l = 0, r = n, res = 0;
33         while (r - l >= 0)
34         {
35             int mid = (l + r) >> 1;
36             if (check(mid))
37             {
38                 l = mid + 1;
39                 res = max(res, mid);
40             }
41             else 
42                 r = mid - 1;
43         }
44         printf("%d
", res);
45     }
46     return 0;
47 }

View Code

C - Alternating Path

Solved

题意：

起点选择一个黑点，终点选择一个白点，如果起点到终点之间存在一条路径是黑、白、黑、白这样的

那么这一对点就合法，给出一张图，求有多少对合法点对

思路：

将每个点与四周和自己颜色不同的点用并查集并起来，然后同一个连通块的任意一堆黑点和白点都是合法的

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 410
 6 char G[N][N];
 7 int n, m;
 8 int pre[N * N], tot[N * N];
 9 int find(int x) { return pre[x] == 0 ? x : pre[x] = find(pre[x]); }
10 void join(int u, int v)
11 {
12     int fu = find(u), fv = find(v);
13     if (fu != fv) pre[fu] = fv;
14 }
15 int f(int x, int y) { return (x - 1) * m + y; }
16 int Move[][2] = 
17 {
18     -1, 0,
19      0,-1,
20 };
21 bool ok(int x, int y) 
22 {
23     if (x < 1 || x > n || y < 1 || y > m) return false;
24     return true;
25 }
26 
27 int main()
28 {
29     while (scanf("%d%d", &n, &m) != EOF)
30     {
31         for (int i = 1; i <= n; ++i) scanf("%s", G[i] + 1);
32         memset(pre, 0, sizeof pre);
33         memset(tot, 0, sizeof tot);
34         for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
35         {
36             for (int k = 0; k < 2; ++k) 
37             {
38                 int nx = i + Move[k][0];
39                 int ny = j + Move[k][1];
40                 if (ok(nx, ny) && G[i][j] != G[nx][ny]) join(f(i, j), f(nx, ny));    
41             }
42         }
43         for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (G[i][j] == '.')
44             ++tot[find(f(i, j))];
45         ll res = 0;
46         for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (G[i][j] == '#') res += tot[find(f(i, j))];
47         printf("%lld
", res);
48     }
49     return 0;
50 }

View Code

D - Nearest Card Game

Unsolved.

题意：

有一个游戏，$B先选择一个整数x$

接着开始游戏

A在剩下的数中选择最大的
B在剩下的数中选择最接近x的，如果有多个，选择最小的那个

每次询问给出一个x，根据这个策略，求A最后选取的数的总和