Codeforces Round #766 (Div. 2)题解

传送门：Codeforces Round #766 (Div. 2)

A. Not Shading

题意：有一个网格，每个格子要么黑色要么白色，现在有一个操作，选择一些黑色的格子，将它们所在的行或列全变成黑色。输出使得坐标(r,c)(r, c)变成黑色的最小操作次数。

思路：直接进行暴力，如果一个黑色的点都没有，那就输出−1-1；如果(r,c)(r, c)已经为黑色，输出00；如果同行或同列有黑色，输出11；否则输出22。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) {
    int n, m, r, c;
    cin >> n >> m >> r >> c;
    vector<string> grid(n);
    for (auto& v : grid) {
      cin >> v;
    }
    int B = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        B += (grid[i][j] == 'B');
      }
    }
    if (!B) {
      cout << "-1\n";
      continue;
    }
    if (grid[r - 1][c - 1] == 'B') {
      cout << "0\n";
      continue;
    }
    B = 0;
    for (int i = 0; i < m; i++) {
      B += (grid[r - 1][i] == 'B');
    }
    for (int i = 0; i < n; i++) {
      B += (grid[i][c - 1] == 'B');
    }
    if (B != 0) {
      cout << "1\n";
      continue;
    }
    cout << "2\n";
  }
  return 0;
}

B. Not Sitting

题意：在一间n∗mn*m的教室里，Tina首先选择刚好kk个位置涂上粉色，然后Rahul会选择一个没被涂颜色的座位坐下，他想坐的离Tina最近，最后Tina会选择一个离Rahul最远的位置坐下，并且Tina可以选择有颜色的位置。对于kk从[0,n∗m−1][0,n*m-1]，输出两人在最优选择下相隔的距离是多少。

思路：Rahul想离Tina最近，但又不知道Tina会坐哪，那么他一定会选择越靠近中间的位置。而Tina此时只能够选择四个角落，这样才能保证自己离Rahul最远。对于每个位置求出到达四个角落的最长距离，此时我们能够知道位置的距离，答案直接将这些距离从小到大输出即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

int fx[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> dp(n, vector<int>(m, INT_MAX));
    queue<pair<int, int>> q;
    dp[0][0] = dp[0][m - 1] = dp[n - 1][0] = dp[n - 1][m - 1] = 0;
    q.emplace(0, 0);
    q.emplace(0, m - 1);
    q.emplace(n - 1, 0);
    q.emplace(n - 1, m - 1);
    while (!q.empty()) {
      auto& [x, y] = q.front();
      q.pop();
      for (int i = 0; i < 4; i++) {
        int nx = x + fx[i][0];
        int ny = y + fx[i][1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && dp[nx][ny] > dp[x][y] + 1) {
          dp[nx][ny] = dp[x][y] + 1;
          q.emplace(nx, ny);
        }
      }
    }
    vector<int> ans;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        ans.push_back(dp[i][j]);
      }
    }
    sort(ans.begin(), ans.end(), greater<>());
    for (int i = 0; i < n * m; i++) {
      cout << n + m - ans[i] - 2 << " \n"[i == n * m - 1];
    }
  }
  return 0;
}

C. Not Assigning

题意：有一棵树，需要给树上的变赋值，使得树上刚好每一条边或相邻的两条边的和为素数。

思路：对于一个点来说，如果它只有一条边，那么随意选一个质数赋给那条边即可；如果有两条边，那么我们可以一条边赋值为22，另一条边赋值为33；如果超过两条，则一定不存在答案，因为不存在三个素数两两加起来还是素数。所以能构造出答案的树一定是一条链。我们dfsdfs对每条边交换的赋值2,32,3即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 5;
struct Edge {
  int v, next;
} edges[MAX << 1];
int head[MAX], k;
int d[MAX], col[MAX];
map<pair<int, int>, int> ans;

void add(int u, int v) {
  edges[++k].next = head[u]; edges[k].v = v; head[u] = k;
  edges[++k].next = head[v]; edges[k].v = u; head[v] = k;
}

void dfs(int u, int fa, int x) {
  for (int i = head[u]; i; i = edges[i].next) {
    int v = edges[i].v;
    if (v == fa) continue;
    ans[{u, v}] = ans[{v, u}] = x;
    dfs(v, u, x ^ 1);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) {
    ans.clear();
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      head[i] = d[i] = 0;
    }
    k = 0;
    vector<pair<int, int>> vec(n - 1);
    for (auto& [u, v] : vec) {
      cin >> u >> v;
      d[u]++;
      d[v]++;
      add(u, v);
    }
    bool flag = true;
    for (int i = 1; i <= n; i++) {
      if (d[i] >= 3) {
        flag = false;
        break;
      }
    }
    if (!flag) {
      cout << "-1\n";
      continue;
    }
    int root = 0;
    for (int i = 1; i <= n; i++) {
      if (d[i] == 1) {
        root = i;
        break;
      }
    }
    dfs(root, 0, 0);
    for (auto& [u, v] : vec) {
      cout << (ans[{u, v}] ? 2 : 3) << " ";
    }
    cout << "\n";
  }
  return 0;
}

D. Not Adding

题意：有一个数组，里面的数互不相同，有一个操作，你可以选择任意两个数求gcdgcd，如果求出来的数不存在在数组中，那么就将它加入到数组。求最多的操作次数。

思路：对于一个数xx，怎么样的两个数a,ba,b的gcdgcd会等于xx。首先这两个数一定是xx的倍数，并且gcd⁡(ax,bx)=1\gcd(\frac{a}{x},\frac{b}{x})=1。那么我们只需要对每个未出现的数去枚举它的所有出现过的倍数，并对这些数取gcdgcd，如果gcd=1gcd=1，那么这个数就是可以产生的，否则不行。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<bool> ok(1000001);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    ok[x] = true;
  }
  int ans = 0;
  for (int i = 1; i <= 1000000; i++) {
    if (ok[i]) continue;
    int gcd = 0;
    for (int j = i + i; j <= 1000000; j += i) {
      if (ok[j]) {
        gcd = __gcd(gcd, j / i);
      }
    }
    ans += (gcd == 1);
  }
  cout << ans << "\n";
  return 0;
}