#|2020年第11届蓝桥杯C++B组第一次省赛真题 #|竞赛题目

文章目录

试题 A: 跑步训练
试题 B: 纪念日
试题 C: 合并检测
试题 D: REPEAT 程序
试题 F: 整除序列
试题 G: 解码
试题 H: 走方格
试题 I: 整数拼接
试题 J: 网络分析

试题 A: 跑步训练

文章图片

【#|2020年第11届蓝桥杯C++B组第一次省赛真题】答案：3880

#include using namespace std; int main(void) { int n = 10000, minu, sec; for (int i = 0; ; i++) { if (i % 2 == 0) { // 跑 if (n > 600) { n -= 600; } else { // 体力不足跑完一分钟 minu = i; sec = n / 10; break; } } else { // 休息 n += 300; } } cout << (minu * 60 + sec) << endl; return 0; }

试题 B: 纪念日

文章图片

答案：52038720

文章图片

可以通过excel来计算出，两个日期相差36138天
所以答案为：36138*24*60=52038720
试题 C: 合并检测

文章图片

答案：10

假设有n个人，需要使用的试剂盒有
n / k + 0.01 ? n ? k n/k+0.01*n*k n/k+0.01?n?k
提取n，有
n ? ( 1 / k + 0.01 ? k ) n*(1/k+0.01*k) n?(1/k+0.01?k)
所以，当k=10时，有最小值
试题 D: REPEAT 程序

文章图片

答案：241830

这道题我只会转换为python的做法
可以先用记事本打开prog.txt，再进行替换。
将 “REPEAT” 替换为 “for i in range(”，再将 “:” 替换为 “):”
此时就把代码转换成了python，运行之后的结果是 241830
试题 F: 整除序列

文章图片

模拟

#include using namespace std; typedef long long ll; int main(void) { ll n; cin >> n; cout << n; n /= 2; while (n > 0) { cout << " " << n; n /= 2; } cout << endl; return 0; }

试题 G: 解码

文章图片

模拟，将简写的字符串展开

#include using namespace std; typedef long long ll; int main(void) { string s; cin >> s; int n = s.size(), num; for (int i = 0; i < n; i++) { if (i != n - 1 && s[i + 1] >= '1' && s[i + 1] <= '9') { num = s[i + 1] - '0'; while (num--) { cout << s[i]; } i++; } else { cout << s[i]; } } cout << endl; return 0; }

试题 H: 走方格

文章图片

简单的动态规划

#include using namespace std; typedef long long ll; int dp[35][35]; int main(void) { int n, m; cin >> n >> m; for (int i = 1; i <= max(n, m); i++) dp[i][1] = dp[1][i] = 1; for (int i = 2; i <= n; i++) { for (int j = 2; j <= m; j++) { if (i % 2 == 0 && j % 2 == 0) dp[i][j] = 0; else dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } cout << dp[n][m] << endl; return 0; }

试题 I: 整数拼接

文章图片

直接进行拼接的复杂度为O ( n 2 ) O(n^2) O(n2)，需要进行优化
如果 x 和 y 进行拼接，拼接后个位上的数为 y 个位上的数
可以先计算出 k 的 0——9 倍个位上的数，并记录到数组里
如果 y 个位上的数存在于数组，说明拼接后的数字有可能是 k 的倍数，从而进行拼接判断
如果 y 个位上的数不在数组内，说明拼接后的数组不可能是 k 的倍数，直接跳过即可

#include using namespace std; typedef long long ll; const int N = 1e5 + 5; ll a[N], num[15]; bool vis[15]; ll connect(ll a, ll b) { ll bb = b; while (bb != 0) { a *= 10; bb /= 10; } a += b; return a; } int main(void) { int n, k, res = 0; cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i <= 9; i++) vis[(i * k) % 10] = 1; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { ll x = a[i], y = a[j]; if (vis[y % 10] && connect(x, y) % k == 0) res++; if (vis[x % 10] && connect(y, x) % k == 0) res++; } } cout << res << endl; return 0; }

试题 J: 网络分析

文章图片

这道题我只会用并查集的暴力做法，复杂度为 O ( n m ) O(nm) O(nm)
如果是1，就用并查集进行合并。如果是2，就遍历所有元素，如果在一个集合内，就加上对应的值。

#include using namespace std; typedef long long ll; const int N = 1e4 + 5; int n, m; ll fa[N], sum[N]; void init() { for (int i = 1; i <= n; i++) fa[i] = i; }int find(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); }void unite(int x, int y) { x = find(x), y = find(y); fa[x] = y; }int main(void) { int t, a, b; cin >> n >> m; init(); while (m--) { cin >> t >> a >> b; if (t == 1) { unite(a, b); } else { for (int i = 1; i <= n; i++) { if (find(a) == find(i)) { sum[i] += b; } } } } for (int i = 1; i <= n - 1; i++) cout << sum[i] << " "; cout << sum[n] << endl; return 0; }