Solution * 2025 - 暑期集训 DAY 4

HTML

平均难度：7/10

平均AC率：33%

水题×0\times0

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

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

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

并查集算法讲义

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

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

const int N = 3e4 + 10;

int parent[N];
int dist[N];
int siz[N];

void init() {
    for (int i = 1; i < N; i++) {
        parent[i] = i;
        dist[i] = 0;
        siz[i] = 1;
    }
}

int find(int x) {
    if (parent[x] != x) {
        int root = find(parent[x]);
        dist[x] += dist[parent[x]];
        parent[x] = root;
    }
    return parent[x];
}

void merge(int i, int j) {
    int root_i = find(i);
    int root_j = find(j);
    if (root_i != root_j) {
        parent[root_i] = root_j;
        dist[root_i] = siz[root_j];
        siz[root_j] += siz[root_i];
    }
}

int query(int i, int j) {
    int root_i = find(i);
    int root_j = find(j);
    if (root_i != root_j) return -1;
    else return abs(dist[i] - dist[j]) - 1;
}

void solve() {
    char opt;
    int i, j;
    cin >> opt >> i >> j;
    if (opt == 'M') merge(i, j);
    else printf("%d\n", query(i, j));
}

int main() {
    init();

    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

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，直接判定为谎言。
  • 检查当前陈述是否与之前已确认的陈述矛盾。如果是，判定为谎言。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

const int N = 5e4 + 10;

struct DSU {
    vector<int> parent;

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

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) parent[y] = x;
    }

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

int main() {
    int n, k;
    cin >> n >> k;
    DSU dsu(3 * n);
    
    int lies = 0;
    for (int i = 0; i < k; i++) {
        int d, x, y;
        cin >> d >> x >> y;
        if (x > n or y > n) {
            lies++;
            continue;
        }

        if (d == 1) {
            if (dsu.IsSame(x, y+n) or dsu.IsSame(x, y + 2*n)) lies++;
            else {
                dsu.unite(x, y);
                dsu.unite(x+n, y+n);
                dsu.unite(x + 2*n, y + 2*n);
            }
        } else {
            if (x == y) {
                lies++;
                continue;
            }

            if (dsu.IsSame(x, y) or dsu.IsSame(x, y + 2*n)) lies++;
            else {
                dsu.unite(x, y+n);
                dsu.unite(x+n, y + 2*n);
                dsu.unite(x + 2*n, y);
            }
        }
    }

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

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

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

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

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

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

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

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

int dist[N], total[N];

void bfs() {
    dist[1] = 0;
    total[1] = 1;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (dist[v] > dist[u]+1) {
                dist[v] = dist[u]+1;
                total[v] = total[u];
                q.push(v);
            } else if (dist[v] == dist[u]+1) total[v] = (total[v] + total[u]) % Mod;
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

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

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

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

✅状态表示 定义 dpidp_i 为到达第 ii 级台阶的方案数，如果第 xx 级台阶是坏的，那么 dpx=0dp_x=0。

✅初始状态 dp0=1dp_0=1（地面），dp1=1dp_1=1（如果第 1 级台阶不是坏的）

✅状态转移 dpi=dpi−1+dpi−2dp_i = dp_{i-1}+dp_{i-2}

注意数组越界问题。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

const int Mod = 1000000007;
const int N = 1e5 + 10;

int dp[N];
bool IsBadStep[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        IsBadStep[x] = true;
    }

    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (IsBadStep[i]) {
            dp[i] = 0;
            continue;
        }
        dp[i] = (dp[i] + dp[i-1]) % Mod;
        if (i >= 2) dp[i] = (dp[i] + dp[i-2]) % Mod;
    }

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

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

0 条评论

目前还没有评论...
117
已通过
0
题解被赞
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 15ms
  4. Powered by Hydro v5.0.0-beta.13 Community