挑战赛#12题解T2-T4
2024-12-02 11:05:45
发布于：广东
64阅读
0回复
0点赞
T2:分配水源
这道题其实就是考gcd函数，然后根据题目条件判断即可
代码展示：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
int _; cin >> _;
while (_ --) {
ll a, b, c;
cin >> a >> b >> c;
ll gcdAB = __gcd(a, b);
if (c % gcdAB == 0 && c <= max(a, b) + min(a, b))
cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
这段代码中的gcd前面加了两个下划线，接下来给你们手写gcd的代码
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
T3:不做作业会被抓走
这题可以用广度优先搜索（BFS）来解，可以直接套模板
广搜标准代码：
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 55;
struct node {
int x, y, z;
int step;
};
int bfs(int a, int b, int c, int t, int mp[][MAXN][MAXN]) {
queue<node> q;
q.push({1, 1, 1, 0});
bool vis[MAXN][MAXN][MAXN];
memset(vis, 0, sizeof vis);
vis[1][1][1] = 1;
while (!q.empty()) {
auto [x, y, z, s] = q.front();
q.pop();
if (x == a && y == b && z == c)
return s;
int d[][6] = {{1, -1, 0, 0, 0, 0}, {0, 0, 1, -1, 0, 0}, {0, 0, 0, 0, 1, -1}};
for (int i = 0; i < 6; i ++) {
int nx = x + d[0][i];
int ny = y + d[1][i];
int nz = z + d[2][i];
if (x >= 1 && x <= a && y >= 1 && y <= b && z >= 1 && z <= c && !vis[nx][ny][nz] && mp[nx - 1][ny - 1][nz - 1] == 0) {
q.push({nx, ny, nz, s + 1});
vis[nx][ny][nz] = 1;
}
}
}
return -1;
}
int main() {
int _; cin >> _;
while (_ --) {
int a, b, c, t;
cin >> a >> b >> c >> t;
int mp[MAXN][MAXN][MAXN];
for (int i = 0; i < a; i ++)
for (int j = 0; j < b; j ++)
for (int k = 0; k < c; k ++)
cin >> mp[i][j][k];
int ans = bfs(a, b, c, t, mp);
if (ans != -1 && ans <= t)
cout << ans << endl;
else cout << -1 << endl;
}
return 0;
}
当然，这是三维的数组，所以广搜也要根据模版改一下
T4：智能计算器
所以我们只需要对每个数字进行分解，计算出每个数字包含的 2,5 的个数。
这就是后缀0的个数
代码：
#include <bits/stdc++.h>
using namespace std;
int jc(int n) {
int cnt = 0;
while (n > 0) {
n /= 5;
cnt += n;
}
return cnt;
}
int main() {
int m;
cin >> m;
vector<int> ans;
for (int n = 0; n <= 1000000; n ++)
if (jc(n) == m)
ans.push_back(n);
if (!ans.empty()) {
cout << ans.size() << endl;
for (int i : ans)
cout << i << " ";
cout << endl;
}
else cout << 0;
return 0;
}
这就是我的解题思路，有用的可以点个赞哦
这里空空如也
有帮助，赞一个