【蓝桥杯历年真题】每日算法详解解析（C/C++）
- ✨博主介绍
- 试题 A: 九进制转十进制
- 试题 B: 顺子日期
- 试题 C: 刷题统计
- 试题 D: 修剪灌木
- 试题 E: X 进制减法
- 试题 F: 统计子矩阵
- 试题 G: 积木画
- 试题 H: 扫雷
- 试题 I: 李白打酒加强版
- 试题 J: 砍竹子
✨博主介绍
🌊 作者主页：苏州程序大白 🌊 作者简介：🏆CSDN人工智能域优质创作者🥇，苏州市凯捷智能科技有限公司创始之一，目前合作公司富士康、歌尔等几家新能源公司
试题 A: 九进制转十进制
【问题描述】
九进制正整数 (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 ≤ 10^6
对于 100% 的评测用例，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，那么使用一次魔法可以把这一段竹子的高度都变为 ⌊\sqrt{\frac{H}{2}+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 ≤ 10^6 。
对于 100% 的数据，保证 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;
}腾讯云开发者
