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