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

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

简单题 小红的矩阵

判断几个数除以 的余数为 。矩阵可以当成一维数组。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n * m);
    for (int i = 0; i < n * m; i++)cin >> a[i];
    cout << accumulate(a.begin(), a.end(), 0, [](int x, int y) {
        return x + (y % 10 == 9);
    });
    return 0;
}

中等题 游游的最小公倍数

两个数互质的时候，其最小公倍数即为两个数的乘积，所以需要构造两个互质的数，且这两个数尽量接近 。
由于质数的密度为 ，即一个数 在 内很大概率能找到质数，所以只需在 附近暴力查找一对互质的 ，找到输出 即结束查找。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
void solve() {
    long long n;
    cin >> n;
    for (long long i = n / 2; i >= 1; i--) {
        if (gcd(i, n - i) == 1) {
            cout << i << ' ' << n - i << '\n';
            return;
        }
    }
}
int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

困难题 【模板】单源最短路Ⅰ ‖ 无权图

所有边权都是 ，首选bfs（广度优先搜索）。
使用 数组记录节点是否被访问过， 记录节点到 的距离， 数组初始化为 。
起始时将 加入队列，设 ，如果队列非空，就一直取出队头 ，如果 就将 设为 并遍历其子节点 ，更新 并将 加入队列。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<int>> ver(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        ver[u].push_back(v);
    }
    vector<int> dis(n + 1, 1e9), vis(n + 1);
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (vis[x])continue;
        vis[x] = 1;
        for (auto it : ver[x]) {
            if (vis[it])continue;
            dis[it] = min(dis[it], dis[x] + 1);
            q.push(it);
        }
    }
    for (int i = 1; i <= n; i++)
        if (dis[i] == 1e9)
            dis[i] = -1;
    for (int i = 1; i <= n; i++)cout << dis[i] << " \n"[i == n];
    return 0;
}