第十二届蓝桥杯2021年C++A组省赛题解_蓝桥杯省赛题目c++a组2021

---

注

官方题解：蓝桥杯近 3 年省赛真题讲解（C&C++ 大学 A 组）_数据结构 - 蓝桥云课

历届真题：蓝桥杯大赛历届真题 - C&C++ 大学 A 组 - 蓝桥云课

---

考生须知

---

试题A：卡片

#include<bits/stdc++.h>
using namespace std;

int cnt[15];
 

int main()
{
	for(int i = 0 ; i <= 9 ; i ++ ) cnt[i] = 2021;
	
	for(int i = 1 ; ; i ++ )
	{
		int k = i;
		while(k != 0)
		{
			if( cnt[k % 10] != 0 ) cnt[k % 10] --;
			else
			{
				cout << i - 1;
				return 0;
			}
			k /= 10;
		}
	}
}
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

---

试题B：直线

题解

• 注意map是数组类型，按key值查询value值，因此是二维的，而set是集合，没有value值，因此是一维的。

  • set<pair<double, double> > ss;
    map<pair<double, double>, int> mp; 		//必须要有一个int或者其他类型的value值
    1
    2

• 这道题的本质是对所有的直线进行一个去重处理，因此map和set都可以使用，set更简单点。

• 需要着重注意的是细节类问题

  • 每一条直线对应一个唯一的斜率和截距，二者都是double类型的，因此最好直接求其结果，不要交替复用，以免精度不够。
  • 坐标是整数值，k和b都是double值，因此不要忘记强转类型。
  • 讨论所有情况中有垂直x轴的直线（斜率不存在），防止除零错误（continue）。

代码（set + map）

//set
#include<bits/stdc++.h>
using namespace std; 

set<pair<double, double> > ss;

pair<int, int> point[500];
int idx;


int main()
{
	for(int i = 0 ; i < 20 ; i ++ )
		for(int j = 0 ; j < 21 ; j ++ )
			point[idx ++] = {i, j};
	
	for(int i = 0 ; i < idx ; i ++ )
		for(int j = i + 1 ; j < idx ; j ++ )
		{
			int x1 = point[i].first, y1 = point[i].second;
			int x2 = point[j].first, y2 = point[j].second;
			if(x2 == x1) continue;
			double k = (double)(y2 - y1)/(x2 - x1);
			double b = (double)(x2*y1 - x1*y2)/(x2 - x1);
			
			ss.insert({k, b});
		}
	
	cout << ss.size() + 20;
	
	return 0;
}

// map
#include<bits/stdc++.h>
using namespace std; 

map<pair<double, double>, int> mp;

pair<int, int> point[500];
int idx;

int ans = 20;

int main()
{
	for(int i = 0 ; i < 20 ; i ++ )
		for(int j = 0 ; j < 21 ; j ++ )
			point[idx ++] = {i, j};
	
	for(int i = 0 ; i < idx ; i ++ )
		for(int j = i + 1 ; j < idx ; j ++ )
		{
			int x1 = point[i].first, y1 = point[i].second;
			int x2 = point[j].first, y2 = point[j].second;
			if(x2 == x1) continue;
			double k = (double)(y2 - y1)/(x2 - x1);
			double b = (double)(x2*y1 - x1*y2)/(x2 - x1);
			
			if(mp[{k, b}] == 0)
			{
				mp[{k, b}] = 1;
				ans ++;
			}
		}
	
	cout << ans;
	
	return 0;
}
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
59
60
61
62
63
64
65
66
67
68
69
70

---

试题C：货物摆放

题解

• 一个数由三个数的乘积组成，求不同乘积方案数。
• 最暴力的办法应该是三层循环，从1到n遍历，然后统计i*j*k == n的count。然后数据量太大，考虑优化。
• 首先需要开longlong。
• 然后应该想到没必要遍历1到n之间的所有数。
• 应该想到的是不论由几个数相乘而得，其中的每一个数都必然出自他的因数中。因此可以预处理出其所有因数，然后暴力寻找不同组合。

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> vv;

ll n = 2021041820210418;

ll ans = 0;

int main()
{
	for(ll i = 1 ; i < sqrt(n) ; i ++ )
	{
		if(n % i == 0)
		{
			vv.push_back(i);
			if(n / i != i)
				vv.push_back(n / i);
		}
	}
	
	int len = vv.size();
	for(ll i = 0 ; i < len ; i ++ )
		for(ll j = 0 ; j < len ; j ++ )
			for(ll k = 0 ; k < len ; k ++ )
				if(vv[i] * vv[j] * vv[k] == n) ans ++;
	
	cout << ans;
	
	return 0;
}
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

---

试题D：路径

题解

• dijkstra算法搜索最短路，邻接矩阵就可以
• 需要知道 a和b的最小公倍数 = a乘b除以a和b的最大公约数 最大公约数(a, b) = a * b / gcd(a, b) 。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 2022;

int g[N][N];

int gcd(int x, int y)
{
	return x == 0 ? y : gcd(y % x, x);
}

int dist[N];
bool st[N];

int dijkstra()
{
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	
	for(int i = 1 ; i <= 2021 ; i ++ )
	{
		int t = -1;
		for(int j = 1 ; j <= 2021 ; j ++ )
			if(!st[j] && (t == -1 || dist[j] < dist[t]))
				t = j;
		
		st[t] = true;
		
		for(int j = 1 ; j <= 2021 ; j ++ )
			dist[t] = min(dist[t], dist[j] + g[j][t]);
	}
	
	return dist[2021];
}

int main()
{
	memset(g, 0x3f, sizeof g);
	
	for(int i = 1 ; i <= 2021 ; i ++ )
		for(int j = i + 1 ; j <= 2021 ; j ++ )
		{
			if(abs(i - j) <= 21)
			{
				g[i][j] = g[j][i] = i * j / gcd(i, j);
			}
		}
	
	cout << dijkstra();
	
	return 0;
}
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

---

试题E：回路计数

题解

同类题目题解见AcWing 91. 最短Hamilton路径 - AcWing

• 注意：位运算的优先级较低，因此一定要带括号，或者预先定义一个变量来存储。
• f[state][j] 表示按state方案走，最终到达j点的所有走法

代码

//881012367360
//集合表示：f[state][j] 表示按state方案走，最终到达j点的所有走法
//			如state = 0001100101，j = 0，则有6种不同走法，CFGA,CGFA,GCFA,GFCA,FGAC,FCGA。（其中第0~n-1个点由对应的A~Z表示）
//属性：count
//初始化：f[1][0] = 1； 表示按state = 000..001时，走到第0个节点的方案是一种，A。（即从0点出发）
//结果，要求从0出发回到0的哈夫曼回路，则需要累加从0出发走所有节点一次后最终停留的节点
//
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/302875