2021年蓝桥杯第十二届CC++大学B组真题及代码

目录

1A：空间（填空5分_单位转换）

2B：卡片（填空5分_模拟）

3C：直线（填空10分_数学+排序）

4D：货物摆放（填空10分_质因数）

5E：路径（填空15分_最短路）

6F：时间显示（编程题15分）

解析代码（模拟）

7G：砝码称重（编程题20分）

解析代码（01背包dp）

8H：杨辉三角形（编程题20分）

解析代码（找规律）

9I：双向排序（编程题25分）（待续）

10J：括号序列（编程题25分）（待续）

---

1A：空间（填空5分_单位转换）

答案：67108864

#include <iostream>
using namespace std;int main()
{// A题：256MB存多少个32位二进制整数(4bit)// 256MB = 256 * 1024 KB = 256 * 1024 * 1024 B = 256 * 1024 * 1024 * 8 bitcout << 256 * 1024 * 1024 * 8 / 32 << endl;cout << 256 * 1024 * 1024 / 4 << endl;return 0;
}
// 答案67108864

---

2B：卡片（填空5分_模拟）

答案：3181

#include <iostream>
#include <vector>
using namespace std;vector<int> arr(10, 2021);bool chick(int x)
{while (x){int tmp = x % 10;if (--arr[tmp] < 0)return false;x /= 10;}return true;
}int main()
{for (int i = 1; ; ++i){if (!chick(i)) // 如果拼不出来{cout << i - 1 << endl;return 0;}}return 0;
}
// 答案3181

---

3C：直线（填空10分_数学+排序）

答案：40257

// C：直线
// 大致思路：依次枚举各个点，每两个点生成对应的斜率和截距。最后看有多少个不同的组合，即有多少条不同的直线
// 注意事项：类型为double的两个数值a和b，即使数值相同，对应的double值也有可能不同，
// 故在cpp中比较两个double值应判断其abs之差是否在很小的一个范围之内，例如1e-8
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 200000; // 直线的最大数
int n = 0;
struct Line
{double k;double b;// 结构体内嵌排序函数// 直接写比较函数是裸的len表示当前的值，如果len<a.len，那么就是从小到大排序。// 括号中的const表示参数a对象不会被修改，最后的const表明调用函数对象不会被修改// sort默认为从小到大排序，优先队列默认为从大到小。bool operator < (const Line& t) const  //重载<操作符。可以对两个node使用<操作符进行比较{if (k != t.k)  // k不同的话，k小的在前return k < t.k;return b < t.b; // k相同的话，b小的在前}
}l[N];int main()
{//枚举一下所有的点对for (int x1 = 0; x1 < 20; ++x1){for (int y1 = 0; y1 < 21; ++y1){for (int x2 = 0; x2 < 20; ++x2){for (int y2 = 0; y2 < 21; ++y2){if (x1 != x2)//避免斜率不存在的情况，总共20条竖线{double k = (double)(y2 - y1) / (x2 - x1);double b = y2 - k * x2;l[n++] = { k,b }; // 存数对}}}}}sort(l, l + n);int res = 1;for (int i = 1; i < n; ++i) // 找出截率和斜率不等的就是不同数{if (fabs(l[i].k - l[i - 1].k) > 1e-8 || fabs(l[i].b - l[i - 1].b) > 1e-8)++res;}cout << res + 20 << endl; // 加上不存在斜率的20条竖线return 0;
}
// 答案40257

---

4D：货物摆放（填空10分_质因数）

---

        思路：先获得2021041820210418所有质因数（所以质因数也就一百多个），再通过质因数去组合从而获得所有的正约数，最后只需在所有的正约数找3个乘积为2021041820210418就行。

答案：2430

#include <iostream>
#include <vector>using namespace std;
#define int long long
#define endl '\n'
// n比较大，会爆因子signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n = 2021041820210418;vector<int> v;for (int i = 1; i * i <= n; i++) // 得到n的所有约数{if (n % i == 0){v.push_back(i);if (n / i != i)v.push_back(n / i);}}//cout << v.size() << endl;int res = 0;for (auto& a : v) //枚举一下a b c{for (auto& b : v){for (auto& c : v){if (a * b * c == n)++res;}}}cout << res << endl;return 0;
}
// 答案：2430

---

5E：路径（填空15分_最短路）

求最短路的问题，答案是1026837

---

6F：时间显示（编程题15分）

---

解析代码（模拟）

需要注意的是1秒等于1000毫秒，不需要输出毫秒，一开始先除等1000。

#include <iostream>
using namespace std;
#define endl '\n'signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);long long n;cin >> n;//1s=1000ms,先去除毫秒n /= 1000;// 每一天秒数24*60*60==86400s，取得到最后一天的秒数n %= (24 * 60 * 60);int h = n / 3600; // 小时n %= 3600; // 得到最后一天除了时以外的秒数int m = n / 60; //分钟int s = n % 60; //秒printf("%02d:%02d:%02d\n", h, m, s);return 0;
}
// 46800999
// 1618708103123

---

7G：砝码称重（编程题20分）

---

解析代码（01背包dp）

#include <bits/stdc++.h>
#include <iostream>using namespace std;
#define endl '\n'
#define int long long// -m<=j<=m
const int N = 110, M = 200010, OFFSET = M / 2;int n, sum; // n代表总选择数，sum代表所有砝码总重量
int w[N]; // 存重量的数组
bool dp[N][M];
// dp:状态表示f(i,j)-->集合：只从前i个物品中选，且总重量为j的所有方案的集合；属性：是否为true
// 状态计算：不选wi -> dp(i-1,j))、选+wi -> dp(i-1,j-wi)、选-wi ->dp(i-1,j+wi)
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; ++i){cin >> w[i];sum += w[i];}dp[0][OFFSET] = true; // j可能是负数，都要加一个偏移量(足够大的数）for (int i = 1; i <= n; ++i){for (int j = -sum; j <= sum; ++j) // -sum到sum +sum就从0开始，dp[0][0]初始化为true{dp[i][j + OFFSET] = dp[i - 1][j + OFFSET];if (j - w[i] >= -sum)dp[i][j + OFFSET] |= dp[i - 1][j - w[i] + OFFSET];if (j + w[i] <= sum)dp[i][j + OFFSET] |= dp[i - 1][j + w[i] + OFFSET];}}int res = 0;for (int j = 1; j <= sum; ++j){if (dp[n][j + OFFSET] == true)++res;}cout << res << endl;return 0;
}
/*
3
1 4 6
*/

---

8H：杨辉三角形（编程题20分）

---

解析代码（找规律）

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int mod = 1000000007;
const int M = 110;
int dp[M * 2][M][M];signed main()
{memset(dp, 0, sizeof dp); // 0 表示花 1 表示店dp[0][0][2] = 1;int n, m;cin >> n >> m;for (int i = 0; i <= n; ++i){for (int j = 0; j <= m; ++j){for (int k = 0; k <= 101; ++k){if (i == 0 && j == 0)continue;if (i > 0 && !(k & 1)) // 店dp[i][j][k] += dp[i - 1][j][k / 2];if (j > 0) // 花dp[i][j][k] += dp[i][j - 1][k + 1];dp[i][j][k] %= mod;}}}cout << dp[n][m - 1][1];
}

---

9I：双向排序（编程题25分）（待续）

---

10J：括号序列（编程题25分）（待续）