牛客春招刷题训练营-2025.5.28题解

8 活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 小红浏览论坛

简单的判断。
统计 帖子的数量。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, x;
    cin >> n >> x;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        if (abs(a - b) >= x)ans++;
    }
    cout << ans << '\n';
    return 0;
}

中等题 游游的排列构造

选择不相邻的位置放置好数，肯定是放置越密越好。
在前 个位置里将好数和非好数间隔放置，好数需要尽可能大，那只需将 取值范围的数全当作好数。
考虑这么放置： 。
剩下的位置只需任意放置。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    int tot1 = 1, tot2 = n - k + 1;
    vector<int> ans(n);
    for (int i = 0, j = 0; i < k; i++, j += 2) {
        ans[j] = tot2++;
    }
    for (int i = 0; i < n; i++) {
        if (ans[i] == 0) {
            ans[i] = tot1++;
        }
    }
    for (int i = 0; i < n; i++)cout << ans[i] << " \n"[i == n - 1];
    return 0;
}

困难题 【模板】最小生成树

使用 Kruskal 算法：每次贪心取边权最小的边，如果加上该边图中仍不存在环则将该边加入生成树中，否则跳过这条边。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
struct DSU {
    vector<int> fa;
    DSU(int n) : fa(n + 1) {
        iota(fa.begin(), fa.end(), 0);
    }
    int get(int x) {
        while (x != fa[x]) {
            x = fa[x] = fa[fa[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        fa[y] = x;
        return true;
    }
    bool same(int x, int y) {
        return get(x) == get(y);
    }
};
int main() {
    int n, m;
    cin >> n >> m;
    vector<array<long long, 4>> ver;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        ver.push_back({u, v, w, i});
    }
    sort(ver.begin(), ver.end(), [&](auto & x, auto & y) {
        return x[2] < y[2];
    });
    vector<int> idx;
    long long ans = 0;
    DSU dsu(n);
    for (auto [x, y, w, i] : ver) {
        if (dsu.same(x, y)) continue;
        dsu.merge(x, y);
        ans += w;
        idx.push_back(i);
    }
    cout << ans << '\n';
    for (auto it : idx)cout << it << ' ';
    return 0;
}