2025春训第十三场

A. 团结#

其实非常简单，但是我中招了😭

他这个操作等价于先把 $\gcd_{i = 1}^{n} A_i$ 算出来，然后在 1 ～ n 里面选一些数和前面的结果取 gcd，直到结果为 1.

最坏最坏的情况，就是 gcd(n - 1, n) = 1，然后和前面的取 gcd 一定是 1，代价是 3；所以只需要枚举代价是否存在 1 和代价是 2 的两种情况即可。

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
const int N = 100010;
7

8
int gcd(int a, int b) {
9
  return b ? gcd(b, a % b) : a;
10
}
11

12
int a[N];
13

14
int main() {
15
  int n;
16
  scanf("%d", &n);
17
  for (int i = 1; i <= n; ++i) {
18
    scanf("%d", &a[i]);
19
  }
20
  int g = a[1];
21
  if (g == 1) printf("0\n");
22
  else if (gcd(g, n) == 1) printf("1\n");
23
  else if (gcd(g, n - 1) == 1) printf("2\n");
24
  else printf("3\n");
25
  return 0;
26
}

B. 染色#

简单的 dfs 题，从根开始往下搜，遇到不符合的就染色，统计次数即可。

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
const int N = 100010;
7
vector<int> ed[N];
8
int col[N], t[N];
9
int res;
10

11
void dfs(int x) {
12
  if (col[x] != t[x]) {
13
    col[x] = t[x];
14
    res++;
15
  }
16
  for (int y : ed[x]) {
17
    col[y] = col[x];
18
    dfs(y);
19
  }
20
}
21

22
int main() {
23
  int n;
24
  scanf("%d", &n);
25
    for (int i = 2; i <= n; ++i) {
26
      int p;
27
      scanf("%d", &p);
28
      ed[p].push_back(i);
29
  }
30
  for (int i = 1; i <= n; ++i) {
31
    scanf("%d", &t[i]);
32
  }
33
  dfs(1);
34
  printf("%d\n", res);
35
  return 0;
36
}

C. 三元组#

（还在 TLE 但是有戏）

E. 思维导图#

一笔画问题，离散 2-2 刚讲了。对于每个连通块，记度数为奇数的点有 k 个，则需要画 $\lceil \frac{k}{2} \rceil$ 次。把连通块的答案累加即可。

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
const int N = 10010;
7

8
int deg[N];
9
vector<int> ed[N];
10
int cnt;
11
bool v[N];
12

13
void dfs(int x) {
14
  if (v[x]) return;
15
  v[x] = true;
16
  if (deg[x] & 1) cnt++;
17
  for (int y : ed[x]) {
18
    dfs(y);
19
  }
20
}
21

22
int main() {
23
  int n, m;
24
  scanf("%d%d", &n, &m);
25
  for (int i = 1; i <= m; ++i) {
26
    int x, y;
27
    scanf("%d%d", &x, &y);
28
    ed[x].push_back(y);
29
    ed[y].push_back(x);
30
    deg[x]++, deg[y]++;
31
  }
32
  int res = 0;
33
  for (int i = 1; i <= n; ++i) {
34
    if (!v[i]) {
35
      cnt = 0;
36
      dfs(i);
37
      if (!cnt) res++;
38
      else res += (cnt + 1) >> 1;
39
    }
40
  }
41
  printf("%d\n", res);
42
  return 0;
43
}

F. ESP_8266#

这就是个单纯的模拟题，没什么需要注意的。

1
import re
2
l = []
3
while True:
4
    try:
5
        s = input()
6
        l.append(s)
7
    except EOFError:
8
        break
9
s = '\n'.join(l)
10
pos = 0
11
for i in re.findall(r'\([+-]\d{2}\)', s):
12
    if i[1] == '+':
13
        pos += int(i[2:4])
14
    else:
15
        pos -= int(i[2:4])
16
print(pos)

Star's Blog

A. 团结#

B. 染色#

C. 三元组#

E. 思维导图#

F. ESP_8266#