P8741 [蓝桥杯 2021 省 B] 填空问题 题解
题目传送门
欢迎大家指出错误并联系这个蒟蒻
更新日志
- 2023-05-09 23:19 文章完成
- 2023-05-09 23:20 通过审核
- 2023-06-20 21:03 优化了文章代码格式
试题 A ：空间
【解析】
本题考察计算机存储的基础知识，只要掌握空间存储的换算方法，就能够算出答案。
【程序】
#include <bits/stdc++.h>
using namespace std;
int main() {
printf("%d\n", 256 * 8 / 32 * 1024 * 1024);
return 0;
}
【答案】
67108864
试题 B ：卡片
【解析】
这道题应该先定义一个长度为 \(10\) 的数组，用来存放数字 \(0 \sim 9\) 的卡片数，下标则代表数字，元素代表卡片已经使用的张数，初始值为 \(0\) ，每种卡片如果使用超过 \(2021\) 张，则输出结果。
程序从 \(1\) 开始递增遍历，当遍历到某个数时，将拼成该数所需的所有卡片类型数增加，随后判断数组中每种卡片是否被用完，如果用完则退出循环。
【程序】
#include <bits/stdc++.h>
using namespace std;
int a[10];
int main() {
for (int s = 1;; s++) {
int temp = s;
while (temp) {
a[temp % 10]++;
temp /= 10;
}
for (int i = 1; i < 10; i++) {
if (a[i] > 2021) {
printf("%d\n", s - 1);
// 减1是因为这一张无法凑出
return 0;
}
}
}
return 0;
}
【答案】
3181
试题 C ：直线
【解析】
本题很容易让人想到枚举和去重，本人代码就是用枚举和去重来实现的。
为了储存 \(3\) 个数，本人采取了 \(\operatorname{STL}\) 中 \(\operatorname{pair}\) 类来表示，为了去重，本人采取了 \(\operatorname{STL}\) 中的 \(\operatorname{set}\) 集合 （如果没学过，请自行查阅资料）。
【程序】
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
set<PIII> s;
vector<PII> vec;
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int main() {
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 21; j++) {
vec.push_back({ i, j });
}
}
for (int i = 0; i < vec.size(); i++) {
for (int j = i + 1; j < vec.size(); j++) {
int x1 = vec[i].first, y1 = vec[i].second;
int x2 = vec[j].first, y2 = vec[j].second;
int A = x2 - x1, B = y1 - y2, C = x1 * y2 - x2 * y1;
int gcdd = gcd(gcd(A, B), C);
s.insert({ { B / gcdd, A / gcdd }, C / gcdd });
}
}
cout << s.size() << endl;
return 0;
}
【答案】
40257
试题 D ：货物摆放
【解析】
本题根据题意，要满足 \(\operatorname{n}=\operatorname{x}\times \operatorname{y}\times \operatorname{z}\) 的所有情况，首先想到枚举法，分为两步：
1、找出 \(n\) 的所有因子。
2、对所有因子进行暴力枚举。
【程序】
#include <bits/stdc++.h>
using namespace std;
long long a[100];
long long n = 2021041820210418;
int len;
int main() {
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0)
// i是约数
{
a[len++] = i;
// 将约数放入数组
if (n / i != i)
// n/i也是约数
{
a[len++] = n / i;
}
}
}
int ans = 0;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
for (int k = 0; k < len; k++) {
if (a[i] * a[j] * a[k] == n) {
ans++;
}
}
}
}
printf("%d\n", ans);
return 0;
}
【答案】
2430
试题 E ：路径
【解析】
本题题意比较直接，通过题意就可以知道题目考查图的最短路径算法，本人则使用了 \(\operatorname{Dijkstra}\) 算法直接计算 （如果没学过，请自行查阅资料并学习）。
【程序】
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2022;
int edges[MAXN][MAXN];
int d[MAXN];
bool visited[MAXN];
int gcd(int u, int v) {
int temp = u % v;
while (temp > 0) {
u = v;
v = temp;
temp = u % v;
}
return v;
}
int lcm(int u, int v) {
return (u * v / gcd(u, v));
}
int main() {
memset(edges, 0x3f3f3f, sizeof(edges));
for (int i = 1; i <= 2021; i++) {
edges[i][i] = 0;
for (int j = i + 1; j <= 2021; j++) {
if (j - i <= 21) {
edges[i][j] = edges[j][i] = lcm(j, i);
} else {
break;
}
}
}
memset(d, 0x3f3f3f, sizeof(d));
memset(visited, false, sizeof(visited));
d[1] = 0;
for (int i = 1; i < 2021; i++) {
int x = 0;
for (int j = 1; j < 2021; j++) {
if (!visited[j] && d[j] < d[x]) {
x = j;
}
}
visited[x] = 1;
for (int j = max(1, x - 21); j <= min(2021, x + 21); j++) {
d[j] = min(d[j], d[x] + edges[x][j]);
}
}
printf("%d\n", d[2021]);
return 0;
}
【答案】
10266837