第十五届蓝桥杯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"
请问你是否可以使得字符串变成回文字符串