2021年十二届蓝桥杯省赛A组（C++）

发表于2022-02-28字数统计1.7k阅读时长14分

第十二届蓝桥杯（2021 省赛A组（C/C++）真题总结，（博客中真题来自CSDN）

2021年第十二届蓝桥杯省赛A组（C/C++）

填空题 30’

A: 卡片 5’

在这里插入图片描述

答案：3181

解题思路：

将问题解释来说，就是统计从1到n的整数中，0-9的十个数字一共出现过几次的问题。

具体实现可以通过建立大小为10的数组储存0-9十个数字的个数，并从1开始增加，将每个数字都拆成一个个0-9的数字并且在数组中减去相应的数量，一旦数组中有数字的个数下降到负数（即小于0），就可说明数字不够用，则当前的数字无法拼出，所以能拼出的最大正整数就是当前数字减一。

B: 直线 5’

在这里插入图片描述

答案：40257

解题思路：

填空题没有内存和运行时间限制，我们可以暴力解题，通过横纵坐标得到每一点的直角坐标，通过两点的直角坐标计算出两点连线直线的直角坐标方程$y=kx+b$，通过与之前计算出的直线的方程对比，如果没有重复就push入链表，最后输出链表的长度。

注意：浮点数在比较大小时，因为浮点数储存的原因，不可以直接判断两者是否相等，应判断两浮点数的差是否小于一个足够小的数（如1e-5）

C: 货物摆放 10’

在这里插入图片描述

答案：2430

解题思路：

该题涉及到质数分解，将n分解成若干质数的积，将这些质数分成三份相乘成为三个数字，并且保证每组都不相同。

编写程序将n分解成质数积形式，可以得到$n=23331713128575882353$，可以发现把3个3排除，剩下的五个不相同的质数不管怎么组合都不会出现相同的数字，所以将这五个数字分成三组可以类比成将5个小球放进三个袋子，一共有35种分法，所以这五个质数可以组成35种类型。而3个3的分组可以类比成3个一样的小球进三个袋子，一共有1+6+3种结果，二者相乘得到答案$3^510=2430$

D: 路径 10’

在这里插入图片描述

答案：10266837

解题思路：

读题可以得知要求是求图的最短路径问题，考虑使用Floyd算法（点击可以查看我的相关博客）。

首先初始化矩阵，根据初始化条件，当两个数i和j相差小于等于21，则m[i][j] = i * j / __gcd(i, j)，__gcd(int x, int y)为求最大公约数函数。初始化后调用Floyd算法即可

样例代码：

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<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

int minMult(int a,int b){
	int mult = a * b;
	int temp = 0;
	if(b > a){
		temp = b;
		b = a;
		a = temp;
	}
	while(a % b){
		a = a % b;
		temp = b;
		b = a;
		a = temp;
	}
	return mult / b;
}

int main(){
	vector< vector< int > > m(2022, vector<int>(2022, INF));
	for(int i = 1; i < 2022; i++){
		for(int j = i; j <= i + 21 && j < 2022; j++){
			if(j == i){
				m[i][j] = 0;
				continue;
			}
			int num = i * j / __gcd(i, j);
			m[i][j] = num;
			m[j][i] = num;
		}
	}
	printf("|");
	for(int i = 0; i < 100; i++) printf("=");
	printf("|\n|");
	for(int k = 1; k < 2022; k++){
		for(int x = 1; x < 2022; x++){
			for(int y = 1; y < 2022; y++){
			    m[x][y] = min(m[x][y], m[x][k] + m[k][y]);
			}
		}
		if(k % (int)(2022 / 99) == 0){
			printf("*");
		}
	}
	printf("|\n%d",m[1][2021]);
}

E: 回路计数

在这里插入图片描述

程序题 70’

F: 砝码称重 15’

在这里插入图片描述

解题思路：

可以将题目理解成从一个正整数集合中挑选任意数量的数，加减操作后得出一个正整数，求一共有几种组合的问题。可以使用动态规划的思想来解决，将问题拆分成更小的问题。

假如有数组中有n - 1个数字，很容易想到在集合中加入一个正整数后，目前已知可以称出的质量肯定不会变的（可以认为虽然加了一个砝码，但是不使用），所以需要考虑的就是集合中加上第n数字后会对结果产生什么影响。

假设有数组dp，dp[n - 1, i]为当前n - 1个数字是否能拼出数字i，显然如果i可以被拼出并且新加入第n个数字a[n]后，则能多拼出的数字有i + a[n] |i - a[n]|（不确定两者谁大谁小），所以可以得出dp的方程
$$
dp[n, i] = dp[n - 1,i] \and dp[n - 1,\abs{i - a[n]}]\and dp[n-1,i+a[n]]
$$
样例代码：

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
#include<bits/stdc++.h>
using namespace std;
int sumWeight(int* count, int i){
	int sum = 0;
	for(int j = 0; j <= i; j++){
		sum += count[j];
	}
	return sum;
}
bool getByDefault(const vector<bool> &array, int index){
	if(index >= array.size() || index < 0){
		return false;
	}else{
		return array[index];
	}
}

int main(){
	int count;
	scanf("%d", &count);
	int * weights = new int [count];
	for(int i = 0; i < count; i++){
		scanf("%d", &weights[i]);
	}
	vector<bool> last, now;
	last.push_back(true);
	for(int i = 0; i < count; i++){
		for(int j = 0; j <= sumWeight(weights, i); j++){
            bool temp = getByDefault(last, j)
				 	   | getByDefault(last, abs(j - weights[i]))
	 				   | getByDefault(last, j + weights[i]);
			now.push_back(temp);
		}
		printf("\n");
		last = now;
		now.clear();
	}
	int sumCount = 0;
	for(vector<bool>::iterator b = last.begin() + 1; b != last.end(); b++){
		if(*b)
		    sumCount++;
	}
	printf("\n%d", sumCount);
}

代码中使用两个数组代表n-1个数字时是否能拼出的数和n个数时是否能拼出的数，getByDefault()函数用于获取砝码集合对应索引的值，在超出数组范围后返回false。sumWeight()函数返回前i个砝码的总重量，用于循环的范围，因为超出当前所有砝码的总重量的物品是不可能称出重量来的。

G: 异或数列 20’

G

在这里插入图片描述

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
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
unsigned int T;
vector< vector< unsigned int > > quary;

// 获得最高位
int getHigh(unsigned int num){
	int i = 0;
	unsigned int cur = 1;
	while(num >= cur){
		cur = cur << 1;
		i++;
	}
	return i - 1;
}

int main(){
	cin >> T;
	for(int i = 0; i < T; i++){
		int count;
		cin >> count;
		vector< unsigned int > nums;
		for(int j = 0; j < count; j++){
			unsigned int num;
			cin >> num;
			nums.push_back(num);
		}
		quary.push_back(nums);
	}
	for(int i = 0; i < T; i++){
		unsigned int sum = 0;
		for(int j = 0; j < quary[i].size(); j++){
			sum = sum ^ quary[i][j];
		}
		if(sum == 0){
			cout << 0 << endl;
			continue;
		}
		int high = getHigh(sum);
		int num0 = 0, num1 = 0;
		for(int j = 0; j < quary[i].size(); j++){
			if((quary[i][j] >> high) % 2 == 0){
				num0++;
			}else{
				num1++;
			}
		}
		if(num1 == 1){
			cout << 1 << endl;
			continue;
		}
		if((num0 + num1) % 2){
			cout << 1 << endl;
		}else{
			cout << -1 << endl;
		}
	}
}