2019年蓝桥杯省赛B组C++题解（无E、J题）

A：组队

答案：500 - 10 = 490

B：年号字串

答案：2019 = 2*26^2 + 25*26 + 17 = BYQ

分析

  • 没有0的26进制，转换时可依旧按照进制转换的原则
    1
    2
    3
    2019 % 26 = 17  --Q
    (2019-17)/26 % 26 = 25 --Y
    (2019-17)/26 / 26 = 2  --B

***注： 特别地按照规则: 52 % 26 = 0; 52 / 26 = 2
结果应为B0但该进制没有0，于是前一位借1个26给后一位得AZ
提示的样例中也特意显示了52的结果为AZ，好在问题中不涉及到0

C：数列求值

答案：4659

1
2
3
4
5
6
7
8
int a = 1, b = 1, c = 1;
	for(int k = 4; k <= 20190324; k++){
		int t = c;
		c = (a + b + c) % 10000;
		a = b % 10000;
		b = t % 10000;
	}
	cout << c << endl;

D：数的分解

答案：40785

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool judge(int n){
	while(n>0){
		if(n % 10 == 2 || n % 10 == 4){
			return false;
		}
		n /= 10;
	}
	return true;
}
int main(){
	int ans = 0;
	for(int i = 1; i <= 2019; ++i){
		for(int j = 1; j <= 2019; ++j){
			int k = 2019 - i - j;
			if(i<j && j<k && judge(i) && judge(j) && judge(k)){
				ans++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

F：特别数的和

——————————————完整代码————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cstdio> 

using namespace std;

bool judge(int n){
	while(n>0){
		if(n % 10 == 2 || n % 10 == 0|| n % 10 == 1|| n % 10 == 9){
			return true;
		}
		n /= 10;
	}
	return false;
}
int main(){
	int n, ans = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i){
		if(judge(i)){
			ans += i;
		}
	}
	printf("%d\n", ans);
	return 0;
}

G：完全二叉树的权值

题目链接：·【AcWing】·完全二叉树

分析

  1. 完全二叉树中，通过数组[]构建树，记根节点为1，则树的第i层中第一个结点的下标为2^(i-1)
  2. 于是层序遍历（即遍历数组）过程中，通过层数i的累加，可记录第i层的所以结点和，存放在数组num[]中
  3. 题目规模N最大为10^6，2^n - 1 < N，可估计出数组num[]的长度n
  4. 最后求出num[]中结点和最大的

***注：
遍历到第k个结点时，若k = 2^i，i++，从下一层开始重新记录结点和

——————————————完整代码————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio> 

using namespace std;
/*
7
1 6 5 4 3 2 1
*/

int num[20];
int main(){
	int n, t = 1;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i){
		int value;
		scanf("%d", &value);
		if(i < (1<<t)){
			num[t] += value;
		}else{  //从下一层开始重新记录结点和
			num[++t] += value;
		}
	}
	int maxn = -1, flag = -1;
	for(int i = 1; i <= t; ++i){
		if(num[i] > maxn){
			flag = i;
			maxn = num[i];
		}
	}
	printf("%d\n", flag);
	return 0;
}

H：等差数列

题目链接：·【AcWing】·等差数列
分析

  1. 首先将n个数排序，得到缺损的等差数列，要求最短的等差数列，则令$a_0$、$a_{n-1}$为首、末项
  2. 等差数列的性质：设公差为d，任意两项的差均为d的倍数；项数 = $(a_{n-1}-a_0)/d+1$

***注：特别地，d = 0，则项数为n

  • 需要d尽可能大，确定公差d有如下两种方法：

法一：枚举

算法思想

  1. 因为任意两项的差是d的倍数，只需数列两两做差，枚举最小的差即可
    ——————————————完整代码————————————————
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    #include <iostream>
    #include <cstdio>
    #include <algorithm>

    using namespace std;
    /*
    5
    2 6 4 10 20
    */
    const int maxn = 1e5+5;
    const int INF = 0x3f3f3f3f;
    int a[maxn];
    int n;
    bool judge(int minn){	//判断能否作为d
    	for(int i = 1; i < n; ++i){
    		if(a[i] % minn != 0){
    			return false;
    		}
    	}
    	return true;
    }
    int main(){
    	scanf("%d", &n);
    	for(int i = 0; i < n; ++i){
    		scanf("%d", &a[i]);
    	}
    	sort(a, a+n);
    	int temp = a[n-1] - a[0];
    	int minn = INF;
    	for(int i = n-1; i >=1; --i){
    		a[i] = a[i] - a[i-1];	//两两做差
    		if(a[i] < minn){
    			minn = a[i];
    		}
    	}
    	if(minn == 0){
    		printf("%d\n", n);
    	}else{
    		while(1){	//枚举最小的差
    			if(judge(minn)){
    				break;
    			}
    			minn--;
    		}
    		printf("%d\n", temp / minn + 1);
    	}
    	
    	return 0;
    }

法二：最大公约数

第二种方法不那么干脆，却不易想到；

算法思想

  1. 任意两项的差$a_j - a_i = k*d(k = 0, 1, …)$，要k尽可能大，则取所有两项差的最大公约数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int gcd(int a, int b){	//最大公约数
    	return b ? gcd(b, a%b) : a;
    }
    int main(){
    	scanf("%d", &n);
    	for(int i = 0; i < n; ++i){
    		scanf("%d", &a[i]);
    	}
    	sort(a, a+n);
    	int temp = a[n-1] - a[0];
    	int minn = 0;
    	for(int i = n-1; i >=1; --i){
    		minn = gcd(minn, a[i] - a[i-1]);
    	}
    	if(minn == 0){
    		printf("%d\n", n);
    	}else{
    		printf("%d\n", temp / minn + 1);
    	}
    	
    	return 0;
    }

I：后缀表达式

题目链接：·【AcWing】·后缀表达式
为此专门有写一篇博客：·【蓝桥】·后缀表达式

算法思想

  1. M == 0
    全为+号，输入的数累加即可
  2. M > 0
    存在至少一个-运算符，后面的运算符可全变为+运算符；
    • 于是有了贪心的思想：
      为确保结果最大，ans先加上最大的数，再减去最小的数，剩下的取绝对值，累加（即实现将运算符可全变为+）

——————————————完整代码————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;

const int maxn = 2e5+5;
ll a[maxn];
int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m+n+1; ++i){
		scanf("%lld", &a[i]);
	}
	if(m == 0){		//无负号
		ll ans = 0;
		for(int i = 0; i < m+n+1; ++i){
			ans += a[i];
		}
		printf("%lld\n", ans);
	}else{
		sort(a, a+m+n+1);
		ll ans = a[m+n] - a[0];		//首先最大值-最小值
		for(int i = 1; i < m+n; ++i){	//依次取绝对值，累加
			ans += abs(a[i]);
		}
		printf("%lld\n", ans);	
	}
	return 0;
}