【蓝桥杯历年真题】每日算法详解解析（C/C++）-阿里云开发者社区

【【蓝桥杯历年真题】每日算法详解解析（C/C++）

✨博主介绍

试题 A: 九进制转十进制

试题 B: 顺子日期

试题 C: 刷题统计

试题 D: 修剪灌木

试题 E: X 进制减法

试题 F: 统计子矩阵

试题 G: 积木画

试题 H: 扫雷

试题 I: 李白打酒加强版

试题 J: 砍竹子

💫点击直接资料领取💫

✨博主介绍

🌊 作者主页：苏州程序大白

🌊 作者简介：🏆CSDN人工智能域优质创作者🥇，苏州市凯捷智能科技有限公司创始之一，目前合作公司富士康、歌尔等几家新能源公司

💬如果文章对你有帮助，欢迎关注、点赞、收藏

💅 有任何问题欢迎私信，看到会及时回复

💅关注苏州程序大白，分享粉丝福利

试题 A: 九进制转十进制

【问题描述】

九进制正整数 ( 2022 ) 9 (2022)_9(2022)

`转换成十进制等于多少？

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

这个没什么说的直接看代码：

#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

【样例输出】

【评测用例规模与约定】

对于 50% 的评测用例，1 ≤ a , b , n ≤ 1 0 6 1 ≤ a, b, n ≤ 10^61≤a,b,n≤10

对于 100% 的评测用例，1 ≤ a , b , n ≤ 1 0 18 1 ≤ a, b, n ≤ 10^{18}1≤a,b,n≤10

#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 棵树最高能长到多高。

【样例输入】

【样例输出】

【评测用例规模与约定】

对于 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 的结果。

【样例输入】

10 4 0 3

1 2 0

【样例输出】

【样例说明】

当进制为：最低位 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，包含：

大小为 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 取模后的值。

【样例输入】

【样例输出】

【样例说明】

五种情况如下图所示，颜色只是为了标识不同的积木：

【评测用例规模与约定】

对于所有测试用例，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

【样例输出】

【样例说明】

示例图如下，排雷火箭 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

【样例输出】

【样例说明】

如果我们用 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

。

他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以把这一段竹子的高度都变为 ⌊ H 2 + 1 ⌋ ⌊\sqrt{\frac{H}{2}+1}⌋⌊

⌋其中 ⌊x⌋ 表示对 x 向下取整。小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。

【输入格式】

第一行为一个正整数 n，表示竹子的棵数。

第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度。

【输出格式】

一个整数表示答案。

【样例输入】

2 1 4 2 6 7

【样例输出】

【样例说明】

其中一种方案：

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

≤10

。

对于 100% 的数据，保证 n ≤ 2 × 1 0 5 , h i ≤ 1 0 18 n ≤ 2 × 10^5, hi ≤ 10^{18}n≤2×10

,hi≤10

。

#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;
}

【蓝桥杯历年真题】每日算法详解解析（C/C++）