【【蓝桥杯历年真题】每日算法详解解析（C/C++）
✨博主介绍
试题 A: 九进制转十进制
试题 B: 顺子日期
试题 C: 刷题统计
试题 D: 修剪灌木
试题 E: X 进制减法
试题 F: 统计子矩阵
试题 G: 积木画
试题 H: 扫雷
试题 I: 李白打酒加强版
试题 J: 砍竹子
💫点击直接资料领取💫
✨博主介绍
🌊 作者主页：苏州程序大白
🌊 作者简介：🏆CSDN人工智能域优质创作者🥇，苏州市凯捷智能科技有限公司创始之一，目前合作公司富士康、歌尔等几家新能源公司
💬如果文章对你有帮助，欢迎关注、点赞、收藏
💅 有任何问题欢迎私信，看到会及时回复
💅关注苏州程序大白，分享粉丝福利
试题 A: 九进制转十进制
【问题描述】
九进制正整数 ( 2022 ) 9 (2022)_9(2022)
9
`转换成十进制等于多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
这个没什么说的直接看代码：
#include <bits/stdc++.h> using namespace std; int main() { int ans = 2*9*9*9 + 2*9 + 2; cout << ans << endl << endl; // 验证 while (ans) { cout << ans % 9; ans /= 9; } return 0; }
运行结果：1478
试题 B: 顺子日期
【问题描述】
小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456 等。顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123；而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022年份中，一共有多少个顺子日期。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
这个题使用枚举即可
#include <bits/stdc++.h> using namespace std; int a[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int ans; bool check2(string s) { int len = s.length(); for (int i = 2; i < len; i ++) { if (s[i - 2] + 1 == s[i - 1] && s[i - 1] + 1 == s[i]) { return true; } } return false; } bool check(int yy, int dd) { if (dd > a[yy]) { return false; } else { return true; } } int main() { string str = "2022"; string data = ""; for (int yy = 1; yy <= 12; yy ++) { for (int dd = 1; dd <= 31; dd ++) { if (check(yy, dd)) { data = ""; char ch; ch = '0' + yy / 10; data += ch; ch = '0' + (yy % 10); data += ch; ch = '0' + dd / 10; data += ch; ch = '0' + (dd % 10); data += ch; if (check2(str + data)) { cout << str + data << endl; ans ++; } } } } cout << ans; return 0; }
运行结果：
试题 C: 刷题统计
【问题描述】
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？
【输入格式】
输入一行包含三个整数 a, b 和 n。
【输出格式】
输出一个整数代表天数。
【样例输入】
10 20 99
【样例输出】
8
【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ a , b , n ≤ 1 0 6 1 ≤ a, b, n ≤ 10^61≤a,b,n≤10
6
对于 100% 的评测用例，1 ≤ a , b , n ≤ 1 0 18 1 ≤ a, b, n ≤ 10^{18}1≤a,b,n≤10
18
#include <iostream> using namespace std; typedef long long ll; ll a, b, n; int main() { cin >> a >> b >> n; ll t = a * 5 + b * 2; // 一周的数量 ll c = n / t; // 共可以多少周 ll ans = c * 7; // 记录天数 ll res = c * t; // 记录数量 if (res < n) { for (int i = 1; res < n && i <= 7; i ++) { if (i <= 5) res += a; else res += b; ans ++; } } cout << ans; return 0; }
试题 D: 修剪灌木
【问题描述】
爱丽丝要完成一项修剪灌木的工作。有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。
灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。
【输入格式】
一个正整数 N ，含义如题面所述。
【输出格式】
输出 N 行，每行一个整数，第行表示从左到右第 i 棵树最高能长到多高。
【样例输入】
3
【样例输出】
4
2
4
【评测用例规模与约定】
对于 30% 的数据，$N ≤ 10$.
对于 100% 的数据，$1 < N ≤ 10000$.
#include <iostream> #include <cstdio> using namespace std; const int N = 1e4 + 10; int n; long long h[N], m[N]; int main() { scanf("%d", &n); for (int k = 1; k <= 2; k ++) { // 从左到右 for (int i = 1; i <= n; i ++) { for (int j = 1; j <= n; j ++) { h[j] ++; if (h[j] > m[j]) m[j] = h[j]; } h[i] = 0; } // 从右到左 for (int i = n - 1; i >= 2; i --) { for (int j = 1; j <= n; j ++) { h[j] ++; if (h[j] > m[j]) m[j] = h[j]; } h[i] = 0; } } for (int i = 1; i <= n; i ++) { printf("%lld\n", m[i]); } return 0; }
试题 E: X 进制减法
【问题描述】
进制规定了数字在数位上逢几进一。X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则X 进制数 321 转换为十进制数为 65。现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。请你算出 A − B 的结果最小可能是多少。请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数字要小于其进制。
【输入格式】
第一行一个正整数 N，含义如题面所述。
第二行一个正整数 Ma，表示 X 进制数 A 的位数。
第三行 Ma 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各个数位上的数字在十进制下的表示。
第四行一个正整数 Mb，表示 X 进制数 B 的位数。
第五行 Mb 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各个数位上的数字在十进制下的表示。
请注意，输入中的所有数字都是十进制的。
【输出格式】
输出一行一个整数，表示 X 进制数 A − B 的结果的最小可能值转换为十进制后再模 1000000007 的结果。
【样例输入】
11
3
10 4 0 3
1 2 0
【样例输出】
94
【样例说明】
当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法得到的差最小。此时 A 在十进制下是 108，B 在十进制下是 14，差值是 94。
【评测用例规模与约定】
对于 30% 的数据，N ≤ 10; Ma, Mb ≤ 8
对于 100% 的数据，2 ≤ N ≤ 1000; 1 ≤ Ma, Mb ≤ 100000; A ≥ B
这块你们只需要理解x进制是怎么回事就好了，然后用了贪心和前缀乘积。
#include <iostream> #include <algorithm> using namespace std; const int N = 1e5 + 10; int n; int ma, mb, mc; int a[N], b[N], c[N], Max[N]; long long A, B; void re(int *arr, int n) { // 反转 n ++; int len = n / 2; for (int i = 1; i <= len; i ++) { int temp = arr[i]; arr[i] = arr[n - i]; arr[n - i] = temp; } } int main() { scanf("%d", &n); // 输入a scanf("%d", &ma); for (int i = 1; i <= ma; i ++) { scanf("%d", &a[i]); } re(a, ma); // 输入b scanf("%d", &mb); for (int i = 1; i <= mb; i ++) { scanf("%d", &b[i]); } re(b, mb); // 得到进位（贪心） int len = max(ma, mb); for (int i = 1; i <= len; i ++) { Max[i] = max(a[i], b[i]) + 1; if (Max[i] < 2) Max[i] = 2; } puts("\n\n"); for (int i = 1; i <= ma; i ++) printf("%d ", a[i]); puts("\n\n"); for (int i = 1; i <= mb; i ++) printf("%d ", b[i]); puts("\n\n"); for (int i = 1; i <= len; i ++) printf("%d ", Max[i]); puts("\n\n"); // 得到进位权 Max[0] = 2; for (int i = 2; i <= len; i ++) { long long w = ((long long)Max[i] * (long long)Max[i - 1]) % 1000000007; Max[i] = (int)w; } // 相减 for (int i = 1; i <= len; i ++) { c[i] = a[i] - b[i]; } long long ans = 0; // 计算进位 for (int i = 1; i <= len; i ++) { ans = (ans + (c[i] * Max[i - 1]) % 1000000007) % 1000000007; } printf("%lld", ans); return 0; }
试题 F: 统计子矩阵
【问题描述】
给定一个 N × M 的矩阵 A，请你统计有多少个子矩阵 (最小 1 × 1，最大N × M) 满足子矩阵中所有数的和不超过给定的整数 K?
【输入格式】
第一行包含三个整数 N, M 和 K。
之后 N 行每行包含 M 个整数，代表矩阵 A。
【输出格式】
一个整数代表答案。
【样例输入】
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
【样例输出】
19
【样例说明】
满足条件的子矩阵一共有 19，包含：
大小为 1 × 1 的有 10 个。
大小为 1 × 2 的有 3 个。
大小为 1 × 3 的有 2 个。
大小为 1 × 4 的有 1 个。
大小为 2 × 1 的有 3 个。
【评测用例规模与约定】
对于 30% 的数据，N, M ≤ 20
对于 70% 的数据，N, M ≤ 100
对于 100% 的数据，1 ≤ N, M ≤ 500; 0 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int N = 1e3 + 10; int n, m; ll s[N][N]; ll res, ans, k; ll Sum(int i, int j, int u, int v) { ll s1 = s[u][v]; ll s2 = s[i - 1][v]; ll s3 = s[u][j - 1]; ll s4 = s[i - 1][j - 1]; return s1 - s2 - s3 + s4; } int main() { scanf("%d %d %lld", &n, &m, &k); for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { scanf("%lld", &s[i][j]); } } // 二维前缀和 for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + s[i][j]; } } // 枚举每一个单元矩阵大小 for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { for (int u = i; u <= n; u ++) { for (int v = j; v <= m; v ++) { res = Sum(i, j, u, v); if (res <= k) ans ++; } } } } printf("%lld", ans); return 0; }
试题 G: 积木画
【问题描述】
小明最近迷上了积木画，有这么两种类型的积木，分别为 I 型（大小为 2个单位面积）和 L 型（大小为 3 个单位面积）：
同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？积木可以任意旋转，且画布的方向固定。
【输入格式】
输入一个整数 N，表示画布大小。
【输出格式】
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值。
【样例输入】
3
【样例输出】
5
【样例说明】
五种情况如下图所示，颜色只是为了标识不同的积木：
【评测用例规模与约定】
对于所有测试用例，1 ≤ N ≤ 10000000
#include <iostream> #include <cstdio> using namespace std; int n; long long ans; int main() { scanf("%d", &n); if (n == 1) printf("1"); else if (n == 2) printf("2"); else { ans = 2; for (int i = 3; i <= n; i ++) { ans = (ans * ans + 1) % 1000000007; } printf("%lld", ans); } return 0; }
试题 H: 扫雷
【问题描述】
小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下，在一个二维平面上放置着 n 个炸雷，第 i 个炸雷 (xi, yi,ri) 表示在坐标 (xi, yi) 处存在一个炸雷，它的爆炸范围是以半径为 ri 的一个圆。为了顺利通过这片土地，需要玩家进行排雷。玩家可以发射 m 个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第j个排雷火箭 (xj, yj,rj) 表示这个排雷火箭将会在 (xj, yj) 处爆炸，它的爆炸范围是以半径为 rj 的一个圆，在其爆炸范围内的炸雷会被引爆。同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷？
你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。
【输入格式】
输入的第一行包含两个整数 n、m.
接下来的 n 行，每行三个整数 xi, yi,ri，表示一个炸雷的信息。再接下来的 m 行，每行三个整数 xj, yj,rj，表示一个排雷火箭的信息。
【输出格式】
输出一个整数表示答案。
【样例输入】
2 1
2 2 4
4 4 2
0 0 5
【样例输出】
2
【样例说明】
示例图如下，排雷火箭 1 覆盖了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆盖了炸雷 2，所以炸雷 2 也被排除。
【评测用例规模与约定】
对于 40% 的评测用例：$0 ≤ x, y ≤ 10^9, 0 ≤ n, m ≤ 10^3, 1 ≤ r ≤ 10$
对于 100% 的评测用例：$0 ≤ x, y ≤ 10^9, 0 ≤ n, m ≤ 5 × 10^4, 1 ≤ r ≤ 10.$
#include <iostream> #include <cstdio> #include <vector> #include <cmath> #include <cstring> using namespace std; const int N = 5e4 + 10; int n, m; long long ans; struct node { int x, y, r; vector<int> child; int cnt = 0; } a[N]; bool b[N]; void add(int i, int j) { // 计算圆心距 double L = sqrt(pow(a[i].x - a[j].x, 2) + pow(a[i].y - a[j].y, 2)); if (a[i].r > L) a[i].child.push_back(j); if (a[j].r > L) a[j].child.push_back(i); } long long dfs(int index) { long long res = 1; for (int i:a[index].child) { if (!b[i]) { b[i] = true; res = res + dfs(i); } } return res; } long long check(int x, int y, int r) { memset(b, 0, sizeof b); long long res = 0; for (int i = 1; i <= n; i ++) { // 计算圆心距 double L = sqrt(pow(a[i].x - x, 2) + pow(a[i].y - y, 2)); if (r > L && !b[i]) { b[i] = true; res = res + dfs(i); } } return res; } int main() { scanf("%d %d", &n, &m); int x, y, r; for (int i = 1; i <= n; i ++) { scanf("%d %d %d", &x, &y, &r); a[i].x = x; a[i].y = y; a[i].r = r; } for (int i = 1; i <= n; i ++) { for (int j = 1; i <= n; i ++) { if (i != j) add(i, j); } } for (int i = 1; i <= m; i ++) { scanf("%d %d %d", &x, &y, &r); ans = ans + check(x, y, r); } printf("%lld", ans); return 0; }
试题 I: 李白打酒加强版
【问题描述】
话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店 N 次，遇到花 M 次。已知最后一次遇到的是花，
他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？
注意：壶里没酒 ( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。
【输入格式】
第一行包含两个整数 N 和 M。
【输出格式】
输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果。
【样例输入】
5 10
【样例输出】
14
【样例说明】
如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：
010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100
【评测用例规模与约定】
对于 40% 的评测用例：1 ≤ N, M ≤ 10。
对于 100% 的评测用例：1 ≤ N, M ≤ 100。
#include <iostream> #include <cstdio> using namespace std; int n, m; long long ans = 0; void dfs(int n, int m, int x) { if (n == 0 && m == 0 && x == 1) { ans = (ans + 1) % 1000000007; return; } else if (n == 0 && m == 0) { return; } // 遇到花 if (m > 0) { if (x > 0) { dfs(n, m - 1, x - 1); } } // 遇到店 if (n > 0) { dfs(n - 1, m, 2 * x); } } int main() { scanf("%d %d", &n, &m); dfs(n, m - 1, 2); printf("%lld", ans); return 0; }
试题 J: 砍竹子
【问题描述】
这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的
高度为 H i H_iH
i
。
他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以把这一段竹子的高度都变为 ⌊ H 2 + 1 ⌋ ⌊\sqrt{\frac{H}{2}+1}⌋⌊
2
H
+1
⌋其中 ⌊x⌋ 表示对 x 向下取整。小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。
【输入格式】
第一行为一个正整数 n，表示竹子的棵数。
第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度。
【输出格式】
一个整数表示答案。
【样例输入】
6
2 1 4 2 6 7
【样例输出】
5
【样例说明】
其中一种方案：
2 1 4 2 6 7
→ 2 1 4 2 6 2
→ 2 1 4 2 2 2
→ 2 1 1 2 2 2
→ 1 1 1 2 2 2
→ 1 1 1 1 1 1
共需要 5 步完成
【评测用例规模与约定】
对于 20% 的数据，保证 n ≤ 1000 , h i ≤ 1 0 6 n ≤ 1000, h_i ≤ 10^6n≤1000,h
i
≤10
6
。
对于 100% 的数据，保证 n ≤ 2 × 1 0 5 , h i ≤ 1 0 18 n ≤ 2 × 10^5, hi ≤ 10^{18}n≤2×10
5
,hi≤10
18
。
#include <iostream> #include <cstdio> #include <cmath> #include <set> #include <vector> #include <unordered_set> using namespace std; int n, t; set<long long> v; long long ans = 0; int main() { scanf("%d", &n); vector<unordered_set<long long>> arr(n); for (int i = 1; i <= n; i ++) { scanf("%d", &t); v.insert(t); } while (true) { if (v.size() == 1 && *v.begin() == 1) { break; } bool flag = true; // 判断是否砍断后有重复的合并即可 for (set<long long>::iterator it = v.begin(); it != v.end(); it ++) { long long res = *it; if (res == 1) continue; res = sqrt(res/2 + 1); if (v.find(res) != v.end()) { // 有重复直接删除现在这个 v.erase(*it); flag = false; break; } } if (flag) { // 砍掉后没有重复的，那么尝试砍掉其他的 for (set<long long>::iterator it = v.begin(); it != v.end(); it ++) { long long res = *it; if (res > 1) { v.erase(res); res = sqrt(res/2 + 1); v.insert(res); break; } } } // 判断是否与之前重复 int len = v.size(), index = 0; bool t = true; for (auto x:v) { if (arr[index].find(x) == arr[index].end()) { t = false; arr[index].insert(x); } index ++; } if (t) ans --; ans ++; } ans ++; printf("%lld", ans); return 0; }
