题解|2022年第十三届蓝桥杯省赛C/C++B组个人题解算法|蓝桥杯|算法|数据结构|数

2022第十三届蓝桥杯省赛C++B组个人题解试题 A: 九进制转十进制
文章图片

#include #include using namespace std; int main() { cout << 2 * pow(9, 0) + 2 * pow(9, 1) + 0 * pow(9, 2) + 2 * pow(9, 3) << endl; return 0; }

答案：1478
试题 B: 顺子日期

文章图片

20220123 20220321 // ？？？ 20221123 20221230 20221231

看题，在说明 20220123 时，说它出现了一个顺子：123。
所以我认为 012 这种数字是不算的。
然后在说明20221023时又涉及到了 210 这个逆序数，但它说这不是一个顺子日期。因此我认为，这里更明确了 0 不可以被包括进去，而逆序的可以算是顺子。
所以我在考试时写了五种，但赛后又觉得逆序的顺子应该不能算，所以可能要把3月21去掉…
答案：5
试题 C: 刷题统计

文章图片

【样例输入】

10 20 99

【样例输出】

8

文章图片

陷阱：注意 n 要用 long long 存

#include using namespace std; int main() { int cnt = 1; long long n; int a, b; cin >> a >> b >> n; long long sum = 0; while (sum < n) { if (cnt % 7 == 0 || cnt % 7 == 6) { sum += b; } else { sum += a; } cnt++; } // 当超出时退出while循环，所以答案需要减一。 cout << cnt - 1 << endl; return 0; }

试题 D: 修剪灌木

文章图片

【样例输入】

3

【样例输出】

4 2 4

文章图片

首先用暴力找规律，然后再根据规律简化代码

// 暴力代码：来回走两次。注意回的时候要把两个边界去掉。#include #include using namespace std; const int maxn = 1e4 + 100; int a[maxn]; int maxHeight[maxn]; int main() { int n; while (cin >> n) { memset(a, 0, sizeof(a)); memset(maxHeight, 0, sizeof(maxHeight)); // 来回走两次 for (int today = 0; today < n; today++) { for (int i = 0; i < n; i++) { a[i]++; if (a[i] > maxHeight[i]) { maxHeight[i] = a[i]; } if (i == today) { a[i] = 0; } } } for (int today = n - 2; today > 0; today--) { for (int i = 0; i < n; i++) { a[i]++; if (a[i] > maxHeight[i]) { maxHeight[i] = a[i]; } if (i == today) { a[i] = 0; } } } for (int today = 0; today < n; today++) { for (int i = 0; i < n; i++) { a[i]++; if (a[i] > maxHeight[i]) { maxHeight[i] = a[i]; } if (i == today) { a[i] = 0; } } } for (int today = n - 2; today > 0; today--) { for (int i = 0; i < n; i++) { a[i]++; if (a[i] > maxHeight[i]) { maxHeight[i] = a[i]; } if (i == today) { a[i] = 0; } } } for (int i = 0; i < n; i++) { cout << maxHeight[i] << " "; } cout << endl << endl; } return 0; }

结果如下：

文章图片

通过找规律可以简化代码：

#include using namespace std; const int maxn = 1e4 + 10; int ans[maxn]; int main() { int n; cin >> n; for (int i = 0; i < n / 2; i++) { ans[i] = ans[n - i - 1] = (n - i - 1) * 2; } // 奇数情况单独处理 ans[n / 2] = n / 2 * 2; for (int i = 0; i < n; i++) { cout << ans[i] << endl; } return 0; }

试题 E: X 进制减法

文章图片

【样例输入】

11 3 10 4 0 3 1 2 0

【样例输出】

94

文章图片

看了一个小时，读不懂题 orz…
试题 F: 统计子矩阵

文章图片

【样例输入】

3 4 10 1 2 3 4 5 6 7 8 9 10 11 12

【样例输出】

19

文章图片

文章图片

注意 k 已经超了 int 范围（虽然我到不了那就已经超时了，但还是要注意的），int 范围是 -21 4748 3648 ～ 21 4748 3647 (21*10^8)
不会做，直接暴力了，6 个 for ！

#include using namespace std; int mat[550][550]; int main() { int n, m; long long k; cin >> n >> m >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> mat[i][j]; } } long long sum = 0; long long cnt = 0; for (int h1 = 1; h1 <= n; h1++) { for (int h2 = h1; h2 <= n; h2++) { for (int l1 = 1; l1 <= m; l1++) { for (int l2 = l1; l2 <= m; l2++) { sum = 0; for (int h = h1; h <= h2; h++) { for (int l = l1; l <= l2; l++) { sum += mat[h][l]; } } if (sum <= k) { cnt++; } } } } } cout << cnt << endl; return 0; }

试题 G: 积木画

文章图片

【样例输入】

3

【样例输出】

5

文章图片

陷阱：注意要取模取模取模，经常有人忘记这回事！！！
（是的，比如说，我倒数第二题就忘记取模了。。。。。
这道题足足用了我三张白纸，我从 n = 1 画到了 n = 6，写了一个小时。
我认为 dp 就是找规律，可是，该死的是我 n = 6 的时候漏画了一种情况（三列横着的摆放），导致一直找不到规律。。。
这道题的规律是，第 n 列可以通过前面的排列，再加上那几种基础的排列得到。
第一种情况：
dp[n] 可以通过 dp[n - 1] 加上普通的一列得到
第二种情况：
dp[n] 可以通过 dp[n - 2] 加上两块横的得到
第三种情况：
dp[n] 可以通过 dp[n - 3] 加上两个三角形的堆起来得到，但要注意的是，这两个三角形的堆叠方式有两种，所以要加上两倍的 dp[n - 3]
综上：dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3] * 2

#include using namespace std; const long long MOD = 1e9 + 7; const int maxn = 1e7 + 100; long long dp[maxn]; int main() { int n; cin >> n; dp[0] = 1; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { // 注意每次相加后都要取余 dp[i] = (((dp[i - 1] + dp[i - 2]) % MOD) + dp[i - 3] * 2) % MOD; } cout << dp[n] << endl; return 0; }

试题 H: 扫雷

文章图片

【样例输入】

2 1 2 2 4 4 4 2 0 0 5

【样例输出】

2

文章图片

赛前半小时又专门看了眼 BFS，用上了！
陷阱：一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。

#include #include #include #include using namespace std; const int maxn = 50100; // 记录坐标和半径 int x_pos[maxn]; int y_pos[maxn]; int radius[maxn]; bool vis[maxn]; // 用来记录这个点爆炸了没有// 用于 bfs 的 struct，更方便处理 struct point { int x, y, r; // 将结构体放入 map 中，需要自己写一个 operator 来排序，因为 map 本身是有序的 bool operator < (const point& p) const { if (x == p.x) { if (y == p.y) { return r < p.y; } return y < p.y; } return x < p.x; } }; map all; double getDis(int x1, int y1, int x2, int y2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }int bfs(point begin, int n) { int cnt = 0; queue q; q.push(begin); while (!q.empty()) { point cur = q.front(); q.pop(); // 遍历以 2 倍半径为边长的正方形，找到其爆炸所涉及到的炸雷 for (int i = cur.y - cur.r; i <= cur.y + cur.r; i++) { for (int j = cur.x - cur.r; j <= cur.x + cur.r; j++) { if(getDis(j, i, cur.x, cur.y) > cur.r) { continue; } point temp; temp.y = i, temp.x = j; for (int k = 0; k < n; k++) { if (!vis[k] && x_pos[k] == temp.x && y_pos[k] == temp.y) { temp.r = radius[k]; q.push(temp); cnt++; all[temp]--; vis[k] = true; // 标记为以爆炸 } } } } } return cnt; }int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> x_pos[i] >> y_pos[i] >> radius[i]; vis[i] = false; // 初始化都还没有爆炸 } int x, y, r; for (int i = 0; i < m; i++) { point p; cin >> p.x >> p.y >> p.r; cout << bfs(p, n) << '\n'; // dev调试还不能用endl，否则就不能进入下一步 } return 0; }

试题 I: 李白打酒加强版 【题解|2022年第十三届蓝桥杯省赛C/C++B组个人题解】

文章图片

【样例输入】

5 10

【样例输出】

14

文章图片

文章图片

泪目了，写题解发现我竟然忘记取模了忘记取模了忘记取模了5555555555
大家一定要记得取模！！！
年前和年后都练了一段时间的回溯，觉得特别有意思。
赛前半小时还专门看了一眼！！然后考试最后半个小时花了 20min 就写出来了。
本来一下子就写出框架了，不过太着急了，很多题目条件没看清楚，导致找了好久错误，不过还好，这题答案错了的话就是比正确答案大一些，很容易发现错误。
主要错误如下：
① 一共必须要且仅要经过 N 次店，M 次花
② 最后一次遇到的必须是花
③ 最后遇到花后，酒必须喝光
④ 在中途遇到花时，酒不能为空

#include #include #include using namespace std; const int MOD = 1e9 + 7; void backTrack(vector& temp, vector >& ans, int n, int m, int nn, int mm, int jiu) { if (jiu < 0) return; // 如果遇到花却没酒了，则不符合条件 if (nn > n || mm > m) return; // 如果经过了多于 N 次店、M 次花，则不符合条件 if (temp.size() == n + m) { if (jiu == 0 && temp.back() == '0') { // 如果最后到达的是店也不符合条件 ans.push_back(temp); } return; } temp.push_back('0'); backTrack(temp, ans, n, m, nn, mm + 1, jiu - 1); temp.pop_back(); temp.push_back('1'); backTrack(temp, ans, n, m, nn + 1, mm, jiu * 2); temp.pop_back(); }int main() { int n, m; cin >> n >> m; int jiu = 2; vector temp; vector > ans; backTrack(temp, ans, n, m, 0, 0, jiu); cout << ans.size() % MOD << endl; return 0; }

试题 J: 砍竹子