Solution * 2025 - 暑期集训 DAY 4

平均难度：7/10 平均AC率：33% 水题$\times 0$$\times0$

数据截止至2025/7/19 10:00

A. 奇怪的魔法 提交人数：8/23 AC率：34% 难度：5/10

这个问题涉及到动态合并集合以及查询元素之间的距离，使用并查集（Disjoint Set Union, DSU）的数据结构来高效处理。我们需要手写标准的并查集，以支持维护每个节点到其根节点的距离，从而能够计算同一集合中两个节点之间的距离。

并查集算法讲义

对于查询两个节点是否在同一集合，若在同一集合，则计算它们到根节点的距离之差减一即为它们之间的距离；否则返回-1。

67
1
#include <iostream>
2
#include <stdio.h>
3
#include <algorithm>
4
#include <iomanip>
5
#include <math.h>
6
#include <limits.h>
7
#include <string>
8
#include <cstring>
9
#include <vector>
10
using namespace std;
11

12
const int N = 3e4 + 10;
13

14
int parent[N];
15
int dist[N];
16
int siz[N];
17

18
void init() {
19
    for (int i = 1; i < N; i++) {
20
        parent[i] = i;
21
        dist[i] = 0;
22
        siz[i] = 1;
23
    }
24
}
25

26
int find(int x) {
27
    if (parent[x] != x) {
28
        int root = find(parent[x]);
29
        dist[x] += dist[parent[x]];
30
        parent[x] = root;
31
    }
32
    return parent[x];
33
}
34

35
void merge(int i, int j) {
36
    int root_i = find(i);
37
    int root_j = find(j);
38
    if (root_i != root_j) {
39
        parent[root_i] = root_j;
40
        dist[root_i] = siz[root_j];
41
        siz[root_j] += siz[root_i];
42
    }
43
}
44

45
int query(int i, int j) {
46
    int root_i = find(i);
47
    int root_j = find(j);
48
    if (root_i != root_j) return -1;
49
    else return abs(dist[i] - dist[j]) - 1;
50
}
51

52
void solve() {
53
    char opt;
54
    int i, j;
55
    cin >> opt >> i >> j;
56
    if (opt == 'M') merge(i, j);
57
    else printf("%d\n", query(i, j));
58
}
59

60
int main() {
61
    init();
62

63
    int t;
64
    cin >> t;
65
    while (t--) solve();
66
    return 0;
67
}

B. 不安分的魔法学院 7/17 41% 5/10

这个问题类似于经典的并查集问题，但需要处理更复杂的克制关系。

为了方便理解，我们将题目抽象为（可能会违反直觉）：

这个世界上只有三种动物：狗、猫、老虎，其中，狗吃猫、猫吃老虎（别笑）、老虎吃狗。

• 类型1（X和Y是同类）：检查 X 和 Y 的三种动物是否可以在同一集合中而不引起矛盾。具体来说，合并 X 的狗节点与 Y 的狗节点，X 的猫节点与 Y 的猫节点，X 的老虎节点与 Y 的老虎节点。

• 类型2（X吃Y）：根据食用关系（狗吃猫、猫吃老虎、老虎吃狗），检查 X 的动物节点与 Y 的被吃节点是否可以合并。例如，如果 X 是狗，Y 必须是猫（即 Y 是猫或老虎节点中的一个）。

在每次合并前，检查是否存在矛盾：

• 如果 X 或 Y 的编号超过 N，直接判定为谎言。

• 对于类型 2，如果 X=Y，直接判定为谎言。

• 检查当前陈述是否与之前已确认的陈述矛盾。如果是，判定为谎言。

73
1
#include <iostream>
2
#include <stdio.h>
3
#include <algorithm>
4
#include <iomanip>
5
#include <math.h>
6
#include <limits.h>
7
#include <string>
8
#include <cstring>
9
#include <vector>
10
using namespace std;
11

12
const int N = 5e4 + 10;
13

14
struct DSU {
15
    vector<int> parent;
16

17
    DSU(int size) : parent(size+1) {
18
        for (int i = 0; i <= size; i++) parent[i] = i;
19
    }
20

21
    int find(int x) {
22
        if (parent[x] != x) parent[x] = find(parent[x]);
23
        return parent[x];
24
    }
25

26
    void unite(int x, int y) {
27
        x = find(x);
28
        y = find(y);
29
        if (x != y) parent[y] = x;
30
    }
31

32
    bool IsSame(int x, int y) { return find(x) == find(y); }
33
};
34

35
int main() {
36
    int n, k;
37
    cin >> n >> k;
38
    DSU dsu(3 * n);
39
    
40
    int lies = 0;
41
    for (int i = 0; i < k; i++) {
42
        int d, x, y;
43
        cin >> d >> x >> y;
44
        if (x > n or y > n) {
45
            lies++;
46
            continue;
47
        }
48

49
        if (d == 1) {
50
            if (dsu.IsSame(x, y+n) or dsu.IsSame(x, y + 2*n)) lies++;
51
            else {
52
                dsu.unite(x, y);
53
                dsu.unite(x+n, y+n);
54
                dsu.unite(x + 2*n, y + 2*n);
55
            }
56
        } else {
57
            if (x == y) {
58
                lies++;
59
                continue;
60
            }
61

62
            if (dsu.IsSame(x, y) or dsu.IsSame(x, y + 2*n)) lies++;
63
            else {
64
                dsu.unite(x, y+n);
65
                dsu.unite(x+n, y + 2*n);
66
                dsu.unite(x + 2*n, y);
67
            }
68
        }
69
    }
70

71
    printf("%d", lies);
72
    return 0;
73
}

C. 最短路径的数量 8/27 29% 7/10

这个问题要求我们找到从城市1到城市N的最短路径的数量。由于图中可能存在多条最短路径，我们需要使用广度优先搜索(BFS)来计算最短路径的数量。

我们使用邻接表来表示图，然后使用 BFS 来遍历图，因为 BFS 天然适合寻找最短路径。在 BFS 过程中，我们需要：

• 记录每个节点到起点的最短距离

• 记录到达每个节点的最短路径数量

当发现更短的路径时，更新距离和路径数量；当发现相同长度的路径时，累加路径数量。

53
1
#include <iostream>
2
#include <stdio.h>
3
#include <algorithm>
4
#include <iomanip>
5
#include <math.h>
6
#include <limits.h>
7
#include <string>
8
#include <cstring>
9
#include <vector>
10
#include <queue>
11
using namespace std;
12

13
const int Mod = 1e9 + 7;
14
const int N = 2e5 + 10;
15
vector<vector<int> > adj(N);
16
queue<int> q;
17

18
int dist[N], total[N];
19

20
void bfs() {
21
    dist[1] = 0;
22
    total[1] = 1;
23
    q.push(1);
24

25
    while (!q.empty()) {
26
        int u = q.front();
27
        q.pop();
28

29
        for (int v : adj[u]) {
30
            if (dist[v] > dist[u]+1) {
31
                dist[v] = dist[u]+1;
32
                total[v] = total[u];
33
                q.push(v);
34
            } else if (dist[v] == dist[u]+1) total[v] = (total[v] + total[u]) % Mod;
35
        }
36
    }
37
}
38

39
int main() {
40
    int n, m;
41
    scanf("%d %d", &n, &m);
42
    for (int i = 0; i < m; i++) {
43
        int a, b;
44
        scanf("%d %d", &a, &b);
45
        adj[a].push_back(b);
46
        adj[b].push_back(a);
47
    }
48

49
    fill(dist, dist+N, INT_MAX);    // 等效于memset(dist, 0x3f, sizeof dist);
50
    bfs();
51
    printf("%d", total[n]);
52
    return 0;
53
}

D. 典型楼梯问题 13/24 54% 3/10

这个问题是一个经典的动态规划问题，类似于爬楼梯问题，但增加了不能踩某些坏台阶的限制。

✅状态表示 定义 $d{p}_i$$dp_i$ 为到达第 $i$$i$ 级台阶的方案数，如果第 $x$$x$ 级台阶是坏的，那么 $d{p}_x=0$$dp_x=0$。

✅初始状态 $d{p}_0=1$$dp_0=1$（地面），$d{p}_1=1$$dp_1=1$（如果第 1 级台阶不是坏的）

✅状态转移 $d{p}_i=d{p}_{i-1}+d{p}_{i-2}$$dp_i = dp_{i-1}+dp_{i-2}$

注意数组越界问题。

39
1
#include <iostream>
2
#include <stdio.h>
3
#include <algorithm>
4
#include <iomanip>
5
#include <math.h>
6
#include <limits.h>
7
#include <string>
8
#include <cstring>
9
#include <vector>
10
using namespace std;
11

12
const int Mod = 1000000007;
13
const int N = 1e5 + 10;
14

15
int dp[N];
16
bool IsBadStep[N];
17

18
int main() {
19
    int n, m;
20
    cin >> n >> m;
21
    for (int i = 1; i <= m; i++) {
22
        int x;
23
        cin >> x;
24
        IsBadStep[x] = true;
25
    }
26

27
    dp[0] = 1;
28
    for (int i = 1; i <= n; i++) {
29
        if (IsBadStep[i]) {
30
            dp[i] = 0;
31
            continue;
32
        }
33
        dp[i] = (dp[i] + dp[i-1]) % Mod;
34
        if (i >= 2) dp[i] = (dp[i] + dp[i-2]) % Mod;
35
    }
36

37
    printf("%d", dp[n]);
38
    return 0;
39
}

E. 非递减彩色路径 4/27 14% 10/10

本蒟蒻暂时没有做出来，请移步至 root 大佬的题解……

©LY 2025/7/18 *

Edit by Typora(Markdown) Partial by Deepseek Thanks xqwl.netlify.app (Authors @gdy @root) & @root