2019年蓝桥杯第十届CC++大学B组真题及代码

1A：组队（填空5分_手算）

2B：年号字符（填空5分_进制）

3C：数列求值（填空10分_枚举）

4D：数的分解（填空10分）

5E：迷宫（填空15分）

6F：特别数的和（编程题15分）

解析代码（分解数字）

7G：完全二叉树的权值（编程题20分）

解析代码（二叉树的数组遍历）

8H：等差数列（编程题20分）

解析代码（数论_最大公约数）

9I：后缀表达式（编程题25分）

解析代码（数学+贪心）

10J：灵能传输（编程题25分）

解析代码（前缀和+贪心）

1A：组队（填空5分_手算）

题目描述：

作为篮球队教练，你需要从以下名单中选出 1号位至 5号位各一名球员，
组成球队的首发阵容。
每位球员担任 1号位至 5号位时的评分如下表所示。请你计算首发阵容 1
号位至5号位的评分之和最大可能是多少？

注意不能选同一个人，答案：490

2B：年号字符（填空5分_进制）

题目描述：

小明用字母 A对应数字 1，B对应 2，以此类推，用 Z对应 26。对于 27以上的数字，小明用两位或更长位的字符串来对应，例如 AA对应27，AB对应28，AZ对应52，LQ对应329。

请问2019对应的字符串是什么？

题目分析：

这题就是类似于一个进制转换，你可以回想一下十进制转二进制如何转换，然后再想想将十进制转化成26进制，口诀就是除p取余

答案：BYQ


//小明用字母 A对应数字 1，B对应 2，以此类推，用 Z对应 26。对于 27以上的数字，
//小明用两位或更长位的字符串来对应，例如 AA对应27，AB对应28，AZ对应52，LQ对应329。
//请问2019对应的字符串是什么？		
// AZ = 1 * 26 + 26 = 52。LQ = 12 * 26 + 17
// ZZ = 26 * 26 + 26
#include <iostream>
using namespace std;int main()
{int i = 0;for (char ch = 'A'; ch <= 'Z'; ++ch){i++;cout << i << " " << ch << endl;}cout << 12 * 26 + 17 << endl;cout << 329 / 26 << endl;cout << 26 * 26  << endl; // 676cout << 2019 / 676 << endl; // 2 -> Bcout << 2019 - 2 * 676 << endl; // 667cout << 667 / 26 << endl; // 25 -> Ycout << 667 - 25 * 26 << endl; // 17 -> Q // BYQreturn 0;
}

3C：数列求值（填空10分_枚举）

题目描述：
给定数列1,1,1,3,5,9,17,…，从第4项开始，每项都是前3项的和。求
第20190324项的最后4位数字。

题目解析：

暴力循环+位数判断。答案：4659


#include<iostream>
using namespace std;int main()
{int a = 1, b = 1, c = 1, res = 0;for(int i = 4; i <= 20190324; ++i){res = (a + b + c) % 10000;a = b;b = c;c = res;}cout << res << endl; // 答案4659return 0;
}

4D：数的分解（填空10分）

题目描述：
把 2019分解成 3个各不相同的正整数之和，并且要求每个正整数都不包
含数字2和4，一共有多少种不同的分解方法？
注意交换 3个整数的顺序被视为同一种方法，例如 1000+1001+18和
1001+1000+18被视为同一种。

答案40785

#include <iostream>
using namespace std;bool have_24(int x)
{while (x){if (x % 10 == 2 || x % 10 == 4)return true;x /= 10;}return false;
}int main()
{int res = 0;for (int i = 1; i < 2019; ++i){if (!have_24(i))for (int j = i + 1; j < 2019; ++j){if (have_24(j))continue;int k = 2019 - i - j;if (!have_24(k) && k > j) // i j k 从小到大++res;}}cout << res << endl; // 答案40785return 0;
}

思路：先获得2021041820210418所有质因数（所以质因数也就一百多个），再通过质因数去组合从而获得所有的正约数，最后只需在所有的正约数找3个乘积为2021041820210418就行。

答案：2430

#include <iostream>
#include <vector>using namespace std;
#define int long long
#define endl '\n'
// n比较大，会爆因子signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n = 2021041820210418;vector<int> v;for (int i = 1; i * i <= n; i++) // 得到n的所有约数{if (n % i == 0){v.push_back(i);if (n / i != i)v.push_back(n / i);}}//cout << v.size() << endl;int res = 0;for (auto& a : v) //枚举一下a b c{for (auto& b : v){for (auto& c : v){if (a * b * c == n)++res;}}}cout << res << endl;return 0;
}
// 答案：2430

5E：迷宫（填空15分）

题目描述：
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可
以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这
个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，
一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，
其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务
必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 maze.txt，
内容与下面的文本相同）
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

题目解析：一道bfs类型的题目，与平常的bfs不同的是，本题要求的走的路径，所以可以先用bfs计算出相邻格子距离差值为1的路径，然后遍历该路径，并且一定是要求题目所说的字典序来排序（在bfs中无所谓），在main函数中需要讲究先后顺序，所以dir数组的顺序是‘D’,'U','L','R'，如果满足相邻的各自距离为1，那么就将该字母字母加入string ans，然后break跳出，为的是只走一次，因为是一条完整的最短路径。

答案：

UUUULLRLLLLLLLULLLUUUDUULUUUUUUUUUUUULULULLRLLRRLLUUUULULLLLLLRLLULLUUULLLLRRLRRRRRRRDRDDRRRRLLLLRRDDDRRRRDDRRRDRRLLRLLRLRLLLULULLLLULULUUDDDUULLUULUUDUUUDDUUDDDUDUUUDUULLLLLLLLLUUUUUULL

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
char g[30][50];
int dist[30][50];char dir[] = { 'D', 'L', 'R', 'U' };
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
void bfs()
{memset(dist, -1, sizeof(dist));queue<PII> q;q.push({ 29, 49 });dist[29][49] = 0;while (!q.empty()){PII t = q.front();q.pop();for (int i = 0; i < 4; i++){int a = t.first + dx[i], b = t.second + dy[i];if (a < 0 || a >= 30 || b < 0 || b >= 50 || g[a][b] == '1' || dist[a][b] != -1)continue;q.push({ a, b });dist[a][b] = dist[t.first][t.second] + 1;}}
}int main()
{for (int i = 0; i < 30; i++){cin >> g[i];}bfs();string ans;int x = 0, y = 0;while (x != 29 || y != 49){for (int i = 0; i < 4; i++){int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= 30 || b < 0 || b >= 50 || g[a][b] == '1')continue;if (dist[x][y] == dist[a][b] + 1){ans += dir[i];x = a;y = b;break;}}}cout << ans << endl;return 0;
}

6F：特别数的和（编程题15分）

题目描述：
小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到
40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 n 中，所有这样的数的和是多少？
【输入格式】
输入一行包含两个整数 n。
【输出格式】
输出一行，包含一个整数，表示满足条件的数的和。
【样例输入】
40
【样例输出】
574
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ n ≤ 10。
对于 50% 的评测用例，1 ≤ n ≤ 100。
对于 80% 的评测用例，1 ≤ n ≤ 1000。
对于所有评测用例，1 ≤ n ≤ 10000。
【输出格式】
输出一个整数代表答案。
【样例输入】
7
1 6 5 4 3 2 1

解析代码（分解数字）

#include <iostream>
using namespace std;bool have_2019(int x)
{while (x){int a = x % 10;if (a == 2 || a == 0 || a == 1 || a == 9)return true;x /= 10;}return false;
}int main()
{int n = 0, sum = 0;cin >> n;for (int i = 1; i <= n; ++i){if (have_2019(i)){sum += i;}}cout << sum << endl;return 0;
}

7G：完全二叉树的权值（编程题20分）

解析代码（二叉树的数组遍历）

#include<iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
long long arr[N];int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> arr[i];}int maxv = -INF;int depth = 1, res = 1;for (int i = 1; i <= n; i *= 2){long long s = 0; // 完全二叉树每层的开头为2^(n-1)，结尾则是 2^n - 1for (int j = i; j <= i * 2 - 1 && j <= n; j++) // j++就是同一层的下一个{s += arr[j];}if (s > maxv){maxv = s;res = depth;}depth++;}cout << res << endl;return 0;
}

8H：等差数列（编程题20分）

题目描述：
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

【输入格式】
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A 1 ,A 2 ,··· ,A N 。(注意 A 1 ∼ A N 并不一定是按等差数
列中的顺序给出)

【输出格式】
输出一个整数表示答案。

【样例输入】
5
2 6 4 10 20

【样例输出】
10

【样例说明】
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、
18、20。

【评测用例规模与约定】
对于所有评测用例，2 ≤ N ≤ 100000，0 ≤ Ai ≤ 10^9 。

解析代码（数论_最大公约数）

题目概述：给出一段序列，求出满足该段序列的最短等差数列的长度

既然要求的是最短的等差数列的长度，那么就要要求公差比较大，那么这个序列就短
那么问题来了：公差怎么取？

        如果公差取得比较大，那么很有可能就不满足等差序列这个条件了：比如下面这个例子

2 4 8 （如果公差取4，那么2->4，就不满足公差为4，这个性质了->不满足等差数列）

        综上所述：我们要求的是一个数列中满足题意的最小的公差即可，那么现在的问题就转为了：如何求上述的特殊公差？

        根据数据范围我们可以直到这个算法不能写O(N^2)。2 ≤ N ≤ 100000（两层循环会超时）0 ≤ Ai≤ 10^9

        优化：首先遍历一遍数组是跑不了了，要做的优化就是求最小的公差那部分，有没有一种可能，可以用另外一种方式求公差，那就是欧几里得算法求公约数，为什么可以这样写？为说明会联想到公约数？

        因为在等差数列中，首项为a1，剩下的数均可表示为a1+nd，那么是不是只需要同时减去a[0]，也就是首项，那么剩下的数均可表示为nd，那么n不同，d一定相同，那么就完美满足了最大公约数这个性质了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}
int main()
{int n;cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}sort(a, a + n); // 排序是为了让首项为a[0]int d = 0; // 0与任何数的最大公约数都是它的本身for (int i = 1; i < n; i++){//d = gcd(d, a[i] - a[0]); // 减去首项a1d = __gcd(d, a[i] - a[0]); // 减去首项a1，Linux或另一些编译器能用，蓝桥杯也能，VS2022不能}if (!d)printf("%d\n", n); // 如果公约数为0.那么就证明这时一个常数数列elseprintf("%d\n", (a[n - 1] - a[0]) / d + 1); // 公式return 0;
}

9I：后缀表达式（编程题25分）

题目描述：
给定 N 个加号、M 个减号以及 N + M + 1 个整数 A 1 ,A 2 ,··· ,A N+M+1 ，小
明想知道在所有由这 N 个加号、M 个减号以及 N + M +1 个整数凑出的合法的
后缀表达式中，结果最大的是哪一个？
请你输出这个最大的结果。
例如使用1 2 3 + -，则 “2 3 + 1 -” 这个后缀表达式结果是 4，是最大的。
【输入格式】
第一行包含两个整数 N 和 M。
第二行包含 N + M + 1 个整数 A 1 ,A 2 ,··· ,A N+M+1 。
【输出格式】
输出一个整数，代表答案。
【样例输入】
1 1
1 2 3
【样例输出】
4
【评测用例规模与约定】
对于所有评测用例，0 ≤ N, M ≤ 100000，−10^9 ≤ A i ≤ 10^9 。

解析代码（数学+贪心）

题目解析：

后缀表达式：可以任意添加括号进行优先计算，所以可以把所有的负号，变成只有一个负号，那么就让负号对应那个最小的值，得到的总和就是最大的。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;#define int long long
#define endl '\n'signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n = 0, m = 0;cin >> n >> m;int k = n + m + 1; // n = k - m - 1vector<int> arr(k);for (int i = 0; i < k; ++i){cin >> arr[i];}int sum = 0;if(m == 0){for (int i = 0; i < k; i++){sum += arr[i];}}else // 有负号，能把负数变为正数{sort(arr.begin(), arr.end());//int index = 0; // 百分之70的分//while (arr[index] < 0 && m--)//{//	sum += -arr[index++];//}//while (m--)//{//	sum -= arr[index++];//}//while(index < k)//{//	sum += arr[index++];//}sum = arr[k - 1] - arr[0]; // 只保留一个减号for (int i = 1; i < k - 1; i++){sum += abs(arr[i]);}}cout << sum << endl;return 0;
}

10J：灵能传输（编程题25分）

【样例输入】

3
3
5 -2 3
4
0 0 0 0
3
1 2 3
【样例输出】
3
0
3
【样例说明】
对于第一组询问：
对 2 号高阶圣堂武士进行传输操作后 a1 = 3，a2 = 2，a3 = 1。答案为 3。
对于第二组询问：
这一组高阶圣堂武士拥有的灵能都正好可以让他们达到最佳战斗状态。

【样例输入】
3
4
-1 -2 -3 7
4
2 3 4 -8
5
-1 -1 6 -1 -1
【样例输出】
5
7
4

解析代码（前缀和+贪心）

该题实际上要求通过何种灵能传输可以使得该序列的最大值最小
而由前缀和可知一个有序的前缀和序列其max(s[i]-s[i-1])的最大值可以达到最小
（关于这个点大家可以画个图理解一下）
通过对几个样例的观察可以发现一个规律

1.对于ai有
1.a[i]>0时 a[i-1]=a[i-1]+a[i] 则 s[i-1]= 原来的s[i]
a[i]=a[i]-2*a[i] 则原s[i]= s[i-1] + a[i]
则现s[i]= 现s[i-1] - a[i]= 原s[i]- a[i]=原s[i-1]
a[i+1]=a[i+1]+a[i] 参考上述推导可得 s[i+1]=原s[i+1]

这意味着除了s[0]和s[n]以外1~n的任何s[i]可以进行相互交互从而得到一个有序的序列
而a[i]=s[i]-s[i-1]
也就意味着可以通过交换s[i]的方式得到灵能传输后最终结果

        for (int i = 1;i <= n;i++){cin >> a[i];s[i] = s[i - 1] + a[i];}sort(s, s + 1 + n);

如果s[0],s[n]也可以正常交换的话那么这题的推导到这步就可以结束了
我们可以通过直接计算max(s[i]-s[i-1]的值获得最大值的最小值
但问题在于 s[0],s[n]
即我们最终得到的一个序列并不一定是单调的
所以接下来我们就要通过一系列操作解决不单调序列的问题

2.通过上述分析可以明确想要求得本题的最优解应使得所求序列尽量保持单调
通过画图可知一个有两个拐点的曲线重叠部分最小时单调部分最多
而一个曲线符合下列情况时符合要求：
1.左端点小于右端点即要求s[0]<s[n]

        LL s0 = s[0], sn = s[n];if (s0 > sn)swap(s0, sn);

2.极小值在极大值左边
该点要求我们在后续选点的时
应s[0]向左取 s[n]向右取因为只有这样才能取得两边的极值

        int l = 0, r = n; // 构造重叠部分最小的序列for (int i = s0; i >= 0; i -= 2){f[l++] = s[i], st[i] = true;}for (int i = sn; i <= n; i += 2){f[r--] = s[i], st[i] = true;}for (int i = 0; i <= n; ++i){if (st[i] == false)f[l++] = s[i];}

这样以后就可以保证序列为f为重叠部分最小的前缀和序列

        LL res = 0;for (int i = 1;i <= n;i++){res = max(res, abs(f[i] - f[i - 1]));}cout << res << endl;

res即为所求结果，以下为完整代码。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 3e5 + 10;
#define endl '\n'
//由于a[]可能达到1e9所以需要使用到LL
typedef long long LL;LL a[N];    //用于存放初始灵能值
LL s[N];    //用于存放前缀和
LL f[N];    //用于存放最终的有序序列
bool st[N];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){int n;cin >> n;s[0] = 0;// 注意这一步不要忘了for (int i = 1;i <= n;i++){cin >> a[i];s[i] = s[i - 1] + a[i];}LL s0 = s[0], sn = s[n];if (s0 > sn)swap(s0, sn);sort(s, s + 1 + n);for (int i = 0; i <= n; ++i) // 找到排序后 s0,sn的位置{if (s0 == s[i]){s0 = i;break;}}for (int i = 0; i <= n; ++i){if (sn == s[i]){sn = i;break;}}memset(st, false, sizeof st);int l = 0, r = n; // 构造重叠部分最小的序列for (int i = s0; i >= 0; i -= 2){f[l++] = s[i], st[i] = true;}for (int i = sn; i <= n; i += 2){f[r--] = s[i], st[i] = true;}for (int i = 0; i <= n; ++i){if (st[i] == false)f[l++] = s[i];}LL res = 0;for (int i = 1;i <= n;i++){res = max(res, abs(f[i] - f[i - 1]));}cout << res << endl;}return 0;
}