2019年第十届蓝桥杯C/C++ B组省赛题解
试题A——组队
话说这道题也不算太简单吧？不过它确实有几个隐藏的小陷阱。如果不小心疏忽的话，在比赛中可能会犯错。那场比赛时我还以为自己计算了一行的最大值呢！不过这道题目的要求是让你从1-20号球员中选择五个人。这样就等同于在每一列上找到最大的数值。
492填上？那就WA了
可以看到我们圈出的每一个位置的最大值1号位和3号位还有4号位都是同一个人，这显然是错的。
所以有一个限制条件就是每个人只能去一个位置而不是多个位置。
这道题目编程实现的话还不如直接算来的直接。
答案：490
试题B——年号字串
此题实际上就是将十进制数转成二十六进制表示，请看下面的具体解析：
#include <bits/stdc++.h>
using namespace std;
char str[27] = {0,'A','B','C','D','E','F','G','H','I','J','K'
,'L','M','N','O','P','Q','R','S','T','U','V',
'W','X','Y','Z'};
int main() {
int num;
string ans = "";
scanf("%d", &num);
while(num) {
ans += str[num % 26];
num /= 26;
}
for (int i = ans.size() - 1; i >= 0; i--) {
cout << ans[i];
}
return 0;
}答案：BYQ
试题C——数列求值
这道题目本质上就是一种斐波那契数列的变体，在题目中已经明确指出从第四项起每一项目都是前三者的和；因此无需深入观察就能直接写出递推关系式：
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] (i >=4)
//边界条件
dp[1] = dp[2] = dp[3] = 1掌握这一方法就可较为轻松地求得答案。
然而，在处理如此之大的数值时显然无法直接使用long long类型。我们可以通过逐步取模的方式进行计算。
无需采用高精度计算的方法，
因为每一步取模都不会影响最终结果。
有些人可能会疑惑为什么每一步取模操作不会影响最终结果？
证明：
假设我们有两个整数a和b，
那么(a + b) mod m = [(a mod m) + (b mod m)] mod m。
同样地，
(a × b) mod m = [(a mod m) × (b mod m)] mod m。
这些性质确保了即使在每次运算中都进行取模操作，
也不会对最终的结果产生任何影响。
字体不够工整可能会让人觉得不够专业。然而实际上，在每次求和取模于1, 但随后将所有求和后的总值再取模于1,这与直接将每次求和结果先取模后再累加的结果是一致的。这样一来就简化了计算过程
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e4;
LL dp[20190325];
int main() {
dp[1] = dp[2] = dp[3] = 1;
for (int i = 4; i <= 20190324; i++) {
dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;
}
cout << dp[20190324] << endl;
return 0;
}答案：4659
试题D——数的分解
这道题目需要分解为三个数且不可重复使用数字2和4。因此无需采用搜索法而可以直接枚举所有可能性但需要注意如何处理重复情况？注意到2019可表示为x加y加z的形式其中x、y、z均为正整数。对于同一组x、y、z三者的不同排列视为不同的解共有六种不同的排列组合方式因此最终的答案可通过将所有枚举结果除以六来获得。
#include <bits/stdc++.h>
using namespace std;
bool check(int x, int y, int z) { //判断三个正整数中是否含2或4
int res = 0;
while (x) {
res = x % 10;
if (res == 2 || res == 4) return false;
x /= 10;
}
while (y) {
res = y % 10;
if (res == 2 || res == 4) return false;
y /= 10;
}
while (z) {
res = z % 10;
if (res == 2 || res == 4) return false;
z /= 10;
}
return true;
}
int main() {
int ans = 0;
for (int a = 1; a < 2019; a++) {
for (int b = 1; b < 2019; b++) {
if (b == a) continue; //a,b,c三个数不相同
for (int c = 1; c < 2019; c++) {
if (b == c || a == c) continue;
if (a + b + c == 2019 && check(a, b, c)) ans++;
}
}
}
cout << ans / 6 << endl;
return 0;
}因为是填空题，时间复杂度为2019^3，还是要跑个10几秒的
答案：40785
试题E——迷宫
一见这道题激动不已, 因我在刷蓝桥杯题库中的算法提高部分遇到了完全相同的一道题, 名字叫学霸的迷宫
对于这道题而言，在解决最短路径问题时
/*
测试数据
30 50
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
*/
#include <bits/stdc++.h>
using namespace std;
char mp[30][50]; //地图
bool vis[30][50]; //标记该点是否走过
int dir[4][2] = {{1,0},{0,-1},{0,1},{-1,0}}; //方向数组按照下，左，右，上的顺序走
char dirc[4] = {'D','L','R','U'};
int n,m; //迷宫的行列
struct node{
int x; //横坐标
int y; //纵坐标
int step; //步数
string str; //路径
node(int xx, int yy, int ss, string s) { //构造函数
x = xx;
y = yy;
step = ss;
str = s;
}
};
queue<node> q; //创建队列
bool check(int x, int y) { //判断是否越界以及是否是墙以及是否访问过了
if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || mp[x][y] == '1') {
return false;
}
return true;
}
void bfs(int x, int y) {
q.push(node(x, y, 0, ""));
vis[x][y] = true;
while (!q.empty()) {
node now = q.front();
if (now.x == n - 1 && now.y == m - 1) { //到达终点了
cout << now.str << endl;
cout << now.step << endl;
break;
}
q.pop();
for (int i = 0; i < 4; i++) {
int nx = now.x + dir[i][0];
int ny = now.y + dir[i][1];
if (check(nx, ny)) {
q.push(node(nx, ny, now.step + 1, now.str + dirc[i]));
vis[nx][ny] = true;
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%s", mp[i]);
}
bfs(0, 0);
return 0;
}DD DD RR UR RR RR RD RR DL DL LD DL DL LD RR DL RR RD LR LL DD RL DL LD LL LD RL DD RL UR UR LR UL UL UR LR LU LR LU LR UR LU LR UL UL LL UL DR DR RD DR LL LL DDLL LD LL DL DR RR DR RR RD RR LDL DL DDRL DL LDLL DDLL LD LDL LDL DLL LDL
试题F——特别数的和
这道题目差不多是水题，没啥算法，直接枚举加check即可
#include <bits/stdc++.h>
using namespace std;
bool check(int x) {
int res = 0;
while (x) {
res = x % 10;
if (res == 0 || res == 1 || res == 2 || res == 9) return true;
x /= 10;
}
return false;
}
int main() {
int n;
scanf("%d", &n);
int ans = 0;
for (int i = 1; i <= n; i++) {
if (check(i)) {
ans += i;
}
}
cout << ans << endl;
return 0;
}7.试题G——完全二叉树的权值
具体操作如下：第一层仅需输入一个数值；第二层则需要输入两个数值；第三层则需四个数值……如此类推形成一个指数增长的关系模式。整个过程无需额外存储空间或复杂逻辑判断。”
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int n;
cin >> n;
LL maxv = INT_MIN; //INT_MIN是在limits.h头文件中,代表INT型最小值 ,这里记录权值和最大
LL maxv_d = 0; //最大的权值和的层数
for (int i = 0, length = 1, depth = 1; i < n; depth++, length *= 2)
{
LL sum = 0; //每一层的和
for (int j = 0; j < length && i < n; j++, i++ )
{
int x;
cin >> x;
sum += x;
}
if (sum > maxv)
{
maxv = sum;
maxv_d = depth;
}
}
cout << maxv_d << endl;
return 0;
}试题H——等差数列
这道题目考查了一些基础的数论知识, 包括最大公约数gcd和等差数列的相关公式. 为了求解问题, 我们需要找到一个包含所有给定数字的最短等差序列. 这就需要我们首先确定这个序列的最大公差d. 通过样例分析可知, 这个序列的第一项应该是所有数字中的最小值, 而末项则是最大的值. 只有确定了最大公约数值之后, 才能计算出满足条件的最短序列长度. 具体方法是: 计算每个数值与第一个数值之差, 然后找出这些差异的最大公约数值d; 最后利用等差数列长度公式an - a1 / d + 1来计算最终结果.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;
LL a[maxn];
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1);
for (int i = 2; i <= n; i++) {
a[i] -= a[1];
}
int d = a[2];
for (int i = 3; i <= n; i++) {
d = gcd(d, a[i]);
}
if (d == 0) {
cout << n << endl;
} else {
cout << a[n] / d + 1 << endl;
}
return 0;
}因为之前我对每个数都减掉了a[1]所以最后不用减掉a[1]了。
试题I——后缀表达式
这道题简直是个大麻烦啊！实在说不清楚怎么操作才好呢，在用例这里特意构造了一个特别的情况，在其中用例中的处理方式与中缀表达式的运算结果相同。（个人经历表明）其实这个情况对理解前后置运算的区别影响挺大的嘛！
实则上无论是采用前置还是后置运算方式，在这个特定的例子中得到的结果都是一致的。
减号相当于一个二叉树的根。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 200010;
int n, m;
int a[maxn];
int main()
{
scanf("%d%d", &n, &m);
int k = n + m + 1;
LL sum = 0;
for (int i = 0; i < k; i++)
{
scanf("%d", &a[i]);
sum += a[i]; //求这些数的和
}
sort(a, a + k);
if (a[0] >= 0) //第一个数大于0，说明没有负数，因为之前加过一次a[0]，然后我们本来就需要减掉a[0]，所以减掉2*a[0]
{
if (m) sum -= 2 * a[0];
}
else //如果是负数的那么我们需要加上，因为之前是负数，加上去也就相当于减掉,所以-=2*a[i](a[i]<0)
{
for (int i = 0; i < k && a[i] < 0 && m > 0; i++ )
{
sum -= a[i] * 2;
m-- ;
}
}
cout << sum << endl;
return 0;
}试题J——灵能传输
说实话, 这道题的代码实现起来并不复杂. 然而, 思路不容易想到, 实际上就是思想与贪心算法的结合. 在学习过程中, 我对于这道题的理解还不够深入. 老师也提到了这道题目, 并分享了相关的链接以及他的代码:
#include <cstring>
#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef long long LL;
const int N = 300010;
int n;
LL sum[N], a[N], s0, sn;
bool st[N];
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%lld", &sum[i]);
sum[i] += sum[i - 1];
}
s0 = sum[0], sn = sum[n];
if (s0 > sn) swap(s0, sn);
sort(sum, sum + n + 1);
for (int i = 0; i <= n; i ++ )
if (s0 == sum[i])
{
s0 = i;
break;
}
for (int i = n; i >= 0; i -- )
if (sn == sum[i])
{
sn = i;
break;
}
memset(st, 0, sizeof st);
int l = 0, r = n;
for (int i = s0; i >= 0; i -= 2)
{
a[l ++ ] = sum[i];
st[i] = true;
}
for (int i = sn; i <= n; i += 2)
{
a[r -- ] = sum[i];
st[i] = true;
}
for (int i = 0; i <= n; i ++ )
if (!st[i])
{
a[l ++ ] = sum[i];
}
LL res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, abs(a[i] - a[i - 1]));
cout << res << endl;
}
return 0;
}视频讲解：灵能传输