牛客春招刷题训练营-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;
}
查看14道真题和解析