当前位置: 首页 > article >正文

第十五届蓝桥杯C/C++ C 组全部题目详细题解

本文为第十五届蓝桥杯C/C++ C 组全部题目的详细题解,题目均来自于蓝桥杯官网,真题链接:

蓝桥杯真题卷 - 蓝桥云课
觉的有帮助或者写的不错可以点个赞,如果我题解写的有问题也欢迎评论指出,欢迎友好讨论


目录

题一:拼正方形 - 简单数学

题目大意:

解题思路:

代码(C++):

题二:劲舞团 - 模拟

题目大意:

解题思路:

代码(C++):

题三:数字诗意 - 找规律,简单数学证明

题目大意:

解题思路:

代码(C++):

题四:封闭图形个数 - 自定义排序 + 简单模拟

题目大意:

解题思路:

代码(C++):

题五: 回文数组 - 贪心

题目大意:

解题思路:

代码(C++):

题六:商品库存管理 - 差分

题目大意:

解题思路:

代码(C++):

题七:挖矿 - 排序 + 二分查找 / 前缀和

题目大意:

解题思路:

方法一: 枚举一边选的个数 + 排序 + 二分查找

代码(C++):

方法二:枚举移动距离 - 前缀和

代码(C++):

题八:回文字符串 - 双指针

题目大意:

解题思路:

代码(C++):


题一:拼正方形 - 简单数学

0拼正方形 - 蓝桥云课

题目大意:

给你一些2 * 2的正方形和一些1 * 1的正方形
2 * 2的正方形个数为7385137888721,1 * 1的正方形个数为10470245
请问这些正方形能拼出的最大正方形边长为多少?

解题思路:

可以看出2 * 2的正方形个数是远大于1 * 1的正方形个数的。

那么我们可以这么做,先用2*2的正方形全部用来拼一个正方形。

可以拼的数目为7385137888721 ^(1/2)的整数部分,我们可以用计算器算出来为2717561,也就是用掉2717561个2 * 2的正方形。

这个正方形的边长为2717561 * 2 = 5435122。需要用掉5435122 * 2 + 1= 10870245个1*1的正方形才能使得这个正方形的边长加1。

这个数量是大于已有的1*1的正方形个数,所以1 * 1的正方形是用不上的,最后的边长为5435122

代码(C++):

#include <bits/stdc++.h>

int main() {
    std::cout << 5435122;
}

题二:劲舞团 - 模拟

0劲舞团 - 蓝桥云课

题目大意:

给你一些敲击记录,每一条敲击记录包含三个数据,分别是正确的字符,敲出的字符,毫秒时间戳。(其中时间戳保证从小到大排序)

现在定义一个K最大连击:在连续的K次敲击中,都不准有错误,并且每一个相邻的两次敲击时间小于等于1s。

请你找出这些敲击记录中K最大连击这个K的最大值

解题思路:

模拟题,可以直接看代码理解

我们用一个cur来判断当前的连击次数,last 存上一个时间

首先判断此时是否是正确答案,也就是t == s
如果是正确答案,我们就看上一个是否也是正确答案(我这里用last来判断), 来更新cur

更新完后把last设置成此时的time

如果不是正确答案,把last 变成-1

每次判断完后更新cur的最大值即可

代码(C++):

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    char t, s;
    i64 time, last;
    
    int ans = 0, cur;
    
    while (std::cin >> t >> s >> time) {
        if (t == s) {
            if (last == -1) {
                last = time;
                cur = 1;
            } else {
                if (time - last <= 1000) {
                    cur++;
                } else {
                    cur = 1;
                }
            }
            last = time;
        } else {
            last = -1;
        }
        ans = std::max(ans, cur);
    }

    std::cout << ans;
}

把log.txt的数据输出进去算出的是9然后输出9即为正确答案

题三:数字诗意 - 找规律,简单数学证明

0数字诗意 - 蓝桥云课

题目大意:

定义一个数字:
可以表示成连续的(至少两个)正整数相加,那么这个数字就是有诗意的

例如:

3 = 1 + 2

5 = 2 + 3

6 = 1 + 2 + 3

7 = 3 + 4

....

现在给你一n个数字,你需要删除其中的一些数字(可以为0),使得剩下的数字全部是有诗意的

解题思路:

结论: 为2的若干幂次的数字没有诗意,1也没有诗意

直接列举可以猜出这个结论

严格证明的话,主要就是从等差数列求和公式出发证明

题解区有详细证明,这里就不写了(

然后问题就变成了,怎么判断一个数字是否是2的幂次

可以发现,如果一个数字是2的幂次,那么它一定可以一直除以2,直到为1

我们可以一直判断这个数字是否是偶数,如果是偶数,那么就除以2,最后判断是不是1就行

时间复杂度为O(n * log n)

代码(C++):

#include <bits/stdc++.h>

using i64 = long long;

bool check(i64 x) { //这里也要开long long
    while (x > 0) {
        if (x % 2 == 0) {
            x /= 2;
        } else {
            break;
        }
    }
    return x == 1;
}

int main() {
    int n;
    std::cin >> n;

    int ans = 0;
    for (int i = 0; i < n; i++) {
        i64 x; //注意题目范围得开long long
        std::cin >> x;
        if (check(x)) {
            ans++;
        }
    }
    
    std::cout << ans;
}

题四:封闭图形个数 - 自定义排序 + 简单模拟

0封闭图形个数 - 蓝桥云课

题目大意:

题目定义4, 6, 9, 0分别有一个封闭图形 , 8有两个封闭图形

现在给你一个数组,你需要对数组里面的元素进行排序,一个数字所含的封闭图形总数小的排在前面,如果封闭图形个数相同,那么数字本身小的在前面

解题思路:

我们先定义一个函数求出一个数字的封闭图形个数

然后用自定义排序函数,根据题目意思模拟就行

具体看代码

代码(C++):

#include <bits/stdc++.h>


int cal(int x) {
    int res = 0;
    while (x > 0) {
        int cur = x % 10;
        if (cur == 8) {
            res += 2;
        }
        if (cur == 4 || cur == 6 || cur == 9 || cur == 0) {
            res++;
        }
        x /= 10;
    }
    return res;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end(), [&](int i, int j) {
        if (cal(i) == cal(j)) {
            return i < j;
        }
        return cal(i) < cal(j);
    });

    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " ";
    }
    std::cout << "\n";
}

题五: 回文数组 - 贪心

0回文数组 - 蓝桥云课

题目大意:

给你一个长度为n的数组,你需要让数组变成回文数组:

每次操作,你可以从以下两个操作中选择一个进行:

1.选择一个数字,让它加一或者减一

2.选择两个相邻的数字,同时让他们加一或者减一

现在请你输出把数组变成回文数组所需要的最小操作次数

解题思路:

关键点1:要使得数组为回文数组,我们只需要操作数组的左边边让其等于右半边即可

为了方便理解和计算,我们可以建立一个长度为n / 2的数组b,其中b[i] = a[i] - a[n - i - 1]

也就是原来数组与对称的一边的元素的差值

然后现在就变成了:我们需要通过操作使得这个数组b的所有值为0

贪心的想,要使得操作次数最小,我们需要进行更多的操作2,也就是对b数组中”同号“且”相邻“的元素进行操作

我们可以这样模拟这个操作过程:(具体可以看代码理解)

遍历数组b,不断检查相邻的两个元素

如果同号,那么就让绝对值小的那个为0,答案加上这个绝对值小的值,绝对值大的减去绝对值小的 (操作二)

如果不同号,那么就只把当前这个变成0即可 (操作一)

最后再遍历检查一遍,加上每个元素的绝对值 (也就是使用操作一)

代码(C++):

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<i64> b(n / 2);
    for (int i = 0; i < n / 2; i++) {
        b[i] = a[i] - a[n - i - 1];
    }

    i64 ans = 0;
    for (int i = 0; i < n / 2 - 1; i++) {
        if (b[i] * b[i + 1] > 0) {
            ans += std::min(abs(b[i]), abs(b[i + 1]));
            if (abs(b[i]) < abs(b[i + 1])) {
                b[i + 1] -= b[i];
                b[i] = 0;
            } else {
                b[i] -= b[i + 1];
                b[i + 1] = 0;
            }
        } else {
            ans += abs(b[i]);
            b[i] = 0;
        }
    }

    for (int x : b) {
        ans += abs(x);
    }

    std::cout << ans;
}

题六:商品库存管理 - 差分 + 前缀和

此题蓝桥官网的数据有问题,暴力O(n ^ m)也能过,这里讲差分写法

0商品库存管理 - 蓝桥云课

题目大意:

题目可以这么理解:

给你一个长度为n的数组,起初数组里面元素都为0, 再给你m个操作,每个操作为一个区间 [L, R]

表示把这个区间内所有的元素都加1

现在你需要做的是,对面m个操作中的每一个操作,如果不进行这个操作,那么最后数组中有多少个数字为0

解题思路:

差分的原理可以参考:
1094. 拼车 - 力扣(LeetCode)

关键点:我们先把所有的操作完成(可以用差分),得到最终的数组,然后,其中一个操作不做表示把一段区间全部-1,我们只需要统计每段区间1的个数即可

可以用前缀和思想,快速的计算一段区间的1的个数

代码(C++):

#include <bits/stdc++.h>

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> d(n + 1, 0); //差分数组,具体可以看链接的原理

    std::vector<int> l(m), r(m);
    for (int i = 0; i < m; i++) {
        std::cin >> l[i] >> r[i];
        l[i]--;
        d[l[i]]++;
        d[r[i]]--;
    }

    std::vector<int> a(n, 0); //所有操作完后的数组
    a[0] = d[0];

    int tot = (a[0] == 0); //统计所有操作完还为0的个数
    for (int i = 1; i < n; i++) {
        a[i] = a[i - 1] + d[i];//根据差分数组还原
        if (a[i] == 0) {
            tot++;
        }
    }

    std::vector<int> pref(n + 1, 0); //前缀和数组
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + (a[i] == 1);
    }

    for (int i = 0; i < m; i++) {
        std::cout << pref[r[i]] - pref[l[i]] + tot << "\n";
    }
}

题七:挖矿 - 排序 + 二分查找 / 前缀和

0挖矿 - 蓝桥云课

题目大意:

现在有一条x轴,你位于坐标原点,现在有n个矿物都在x轴上,给出这n个矿物的横坐标,

你现在最多可以移动m次,请问你在最多m次移动的情况下,能获得最多多少矿物

解题思路:

方法一: 枚举一边选的个数 + 排序 + 二分查找

我们把在右边的放在一个数组,把在左边的放在另一个数组,并且取绝对值

然后呢,枚举选的个数

左边选0个

左边选一个,然后剩下的选右边

左边选两个,然后剩下的选右边

....

枚举完左边的,我们再枚举选右边的

右边选0个,剩下选左边的

右边选1个,剩下选右边的

...
 

可以使用排序后,用二分查找快速查找剩下可以选择的个数
具体过程可以看代码

时间复杂度,排序为O (n log n) , 枚举过程有二分,时间复杂度为O (n log n )
总体的时间复杂度为O (n log n)

代码(C++):

#include <bits/stdc++.h>

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a, b;
    for (int i = 0; i < n; i++) {
        int v;
        std::cin >> v;
        if (v > 0) {
            a.push_back(v);
        } else {
            b.push_back(abs(v));
        }
    }

    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    
    int ans = 0;
    for (int r = 0; r <= a.size(); r++) {
        int cost;
        if (r == 0) {
            cost = 0;
        } else {
            cost = 2 * a[r - 1];
        }
        if (cost > m) {
            break;
        }
        int l = std::upper_bound(b.begin(), b.end(), m - cost) - b.begin();
        ans = std::max(ans, l + r);
    }

    for (int l = 0; l <= b.size(); l++) {
        int cost;
        if (l == 0) {
            cost = 0;
        } else {
            cost = 2 * b[l - 1];
        }
        if (cost > m) {
            break;
        }
        int r = std::upper_bound(a.begin(), a.end(), m - cost) - a.begin();
        ans = std::max(ans, l + r);
    }

    std::cout << ans;

}

方法二:枚举移动距离 - 前缀和

此方法参考评论区题解

既然最大只能走m次,那么我们可以建立两个数组a, b,长度分别设置为(m + 1),分别储存大于0和小于0的每个位置所包含的矿物数量

然后枚举移动距离

左边走0步,剩下的走右边

左边走1步,剩下的走右边

..

那么怎么快速判断这个步数下能获得的矿物数目呢?

前缀和数组 (代码中,直接把原数组变成前缀和数组了)

具体过程看代码

时间复杂度o(n)

代码(C++):

#include <bits/stdc++.h>

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(m + 1), b(m + 1);

    for (int i = 0; i < n; i++) {
        int v;
        std::cin >> v;
        if (abs(v) <= m) {
            if (v > 0) {
                a[v]++;
            } else {
                b[abs(v)]++;
            }
        }
    }

    for (int i = 1; i < m + 1; i++) {
        a[i] += a[i - 1];
        b[i] += b[i - 1];
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        if (m - 2 * i < 0) {
            break;
        }
        int mx = std::max(a[i] + b[m - 2 * i], b[i] + a[m - 2 * i]);
        ans = std::max(ans, mx);
    }
    
    std::cout << ans;
}

题八:回文字符串 - 双指针

0回文字符串 - 蓝桥云课

题目大意:

给你一个字符串,你可以往字符串开头添加任意数量的”l“, "g", "b"

请问你是否可以使得字符串变成回文字符串

解题思路:

代码(C++):


http://www.kler.cn/a/584574.html

相关文章:

  • 微信小程序使用的SSL证书在哪里申请?
  • 兼职招聘平台(源码+文档+讲解+演示)
  • tomcat负载均衡配置
  • leetcode0056. 合并区间 - medium
  • SQL Server性能优化实战:从瓶颈定位到高效调优
  • R+VIC模型融合实践技术应用及未来气候变化模型预测
  • Oracle获取SQL执行日志
  • 深度学习基础-onnxruntime推理模型
  • 如何通过自动化测试提升DevOps效率?
  • Axure PR 9 中继器 04 条件查询
  • MySQL与Redis的缓存一致性问题
  • 【linux】文件与目录命令 - stat
  • 使用Python在Word中生成多种不同类型的图表
  • JVM类加载机制和双亲委派
  • 江科大51单片机笔记【16】AD/DA转换(下)
  • Arbitrum之智能合约
  • Java 虚拟机优化指南:CMS垃圾回收器参数调优与性能监控工具详解
  • 【数据结构】初识集合框架及背后的数据结构(简单了解)
  • uniapp移动端图片比较器组件,仿英伟达官网rtx光追图片比较器功能
  • Java --- 根据身份证号计算年龄