2021年4月蓝桥杯软件类省赛：题目+解析（完整版）_蓝桥杯比赛题目

---

相关文章：

• 2020年10月蓝桥杯（软件类）省赛：题目+解答
• 2020年4月蓝桥杯（软件类）第二次模拟赛：题目+解答
• 2020年3月蓝桥杯（软件类）第一次模拟赛：题目+解答
• 2019年4月蓝桥杯（软件类）省赛：真题+解答

---

第一题：卡片

解析：

首先要理清题目：从1开始，从小往大按顺序拼，所以总会有一个数字先用完（每一个数字是有限的）。根据题目中例子的提示，不够拼出11，很容易发现1是最先用完的，事实也是如此。所以本题的关键在于：找出刚好用到第2021个1的纸牌！

参考代码：

#include<iostream>
#include<sstream>
#include<algorithm>
using namespace std;

//整型转字符串 
string int_str(int i)
{
	string output;
	stringstream Convert;
	Convert<<i;
	Convert>>output;
	return output;
}

int main()
{
	int i=1;
	int nOne=0;
	while(1)
	{
		string s = int_str(i);
		nOne += count(s.begin(), s.end(), '1');//记录1出现的次数 
		if(nOne>=2021)
			break;
		else
			i += 1; 
	}
	cout<<i<<endl;
	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

代码运行输出是：3181。需要注意的是，3181中有两个1，这个时候需要自己确定一下，哪个1是第2021个1。经过判断可知，3181中的前面那个1是第2020个1，后面的那个1是第2021个1。所以3181是刚好可以拼成的，而3182不能拼成。因此最后的答案是：3181

---

第二题：直线

解析： 总的直线=斜直线+横直线+竖直线。横直线和竖直线很容易统计，分别是21和20个，因此重点统计不同的斜直线个数。每条直线可用：y=kx+b表示，即一组不同的{k, b}代表不同的直线。所以本题的关键点在于用集合来存放并统计不同的斜直线个数。

参考答案： 40257

#include <iostream>
#include <vector>
#include <set>
using namespace std;

struct point
{
	int x; //横坐标
	int y; //纵坐标
};

int main()
{
	vector<point> p;//存放所有点
	for (int i = 0; i <= 19; ++i)
		for (int j = 0; j <= 20; ++j)
			p.push_back({i, j});

	int len = p.size();
	set<pair<double, double>> lines; //存放斜直线y=kx+b
	for (int i = 0; i < len; ++i)
	{
		for (int j = 0; j < len; ++j)
		{
			if (p[i].x != p[j].x && p[i].y != p[j].y) // 统计所有斜直线的情况
			{
				double k = (p[j].y - p[i].y) * 1.0 / (p[j].x - p[i].x);
				double b = (p[j].y * (p[j].x - p[i].x) - (p[j].y - p[i].y) * p[j].x) * 1.0 / (p[j].x - p[i].x);
				//double b = p[j].y - k * p[j].x; 不用这种方法，避免k造成精度爆炸
				lines.insert(pair<double, double>(k, b));
			}

		}
	}
	cout << lines.size() + 20 + 21 << endl; // 总的直线=斜直线+横直线+竖直线
	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

---

第三题：货物摆放

解析： 先找出n的所有因数，再根据因数来判断总的方案数。

参考答案： 2430

#include <iostream>
#include <vector>
using namespace std;
const long long n = 2021041820210418;

int main()
{
	vector<long long> factor; //存放所有因数
	
	for (int i = 1; i < sqrt(n); ++i)
	{
		if (n%i == 0)
		{
			factor.push_back(i);
			factor.push_back(n / i);
		}
	}

	//枚举情况
	int ans = 0;
	int len = factor.size(); //因数的总个数
	for (int i = 0; i < len; ++i)
		for (int j = 0; j < len; ++j)
		{
			if(n%(factor[i]*factor[j])==0)
				ans += 1;
		}
	cout << ans << endl;
	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

---

第四题：路径

题解： 本题考点就是求最小公倍数和最短路径算法dijstra，不过此题也可以用dp做。

参考答案： 10266837

#include <iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll inf = 1e12;
int vis[2050];
ll e[2050][2050], dis[2050];

ll gcd(ll a, ll b)   //求最大公因数
{
	return a % b == 0 ? b : gcd(b, a % b);
}

ll lcm(ll a, ll b)	//求最小公倍数
{
	return a * b / gcd(a, b);
}

int main()
{
	fill(dis, dis + 2050, inf);
	fill(e[0], e[0] + 2050 * 2050, inf);
	for (int i = 1; i <= 2021;i++)
	{
		for (int j = 1; j <= 21;j++)    //21步以内有效
		{
			int k = i + j;  //i为起点，k为终点
			if (k > 2021)
				break;
			e[i][k] = e[k][i] = lcm(i, k);
		}
	}
	dis[1] = 0;
	//最短路径模板  dijstra算法
	for (int i = 1; i <= 2021;i++)
	{
		ll u = -1, minn = inf;
		for (int j = 1; j <= 2021;j++)//找到起点
		{
			if (!vis[j] && dis[j] < minn)
			{
				minn = dis[j];
				u = j;
			}
		}
		if (u == -1)
			break;
		vis[u] = 1;
		for (int v = 1; v <= 2021;v++)
		{
			if (!vis[v])
				dis[v] = min(dis[v], e[u][v] + dis[u]);
		}
	}
	cout << dis[2021];
	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

---

第五题：回路计数

---

第六题：时间显示

解析：

此题比较简单，需要注意两点即可完成：

• 注意单位转换，1天 = 24h = 24x60min = 24x60x60s = 24x60x60x1000ms
• 显示问题，0-9要显示成00-09

参考代码：

#include<iostream>
#include<sstream>
#include<algorithm>
using namespace std;

int main()
{
	long long num;
	cin >> num;
	long long time = num % (24 * 60 * 60 * 1000);
	//时钟 
	int HH = time / (60 * 60 * 1000);
	//分钟 
	int MM = time % (60 * 60 * 1000);
	MM = MM / 60000;
	//秒钟
	int SS = (time / 1000) % 60;
	printf("%02d:%02d:%02d", HH, MM, SS);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

第七题：砝码称重

题解： 采用动态规划，dp[i][j] 表示前 i 个物品，若能称出重量 j 则为 1 ，反之为 0

#include <iostream>
#define N 102
#define MAX_WEIGHT 100005
using namespace std;

int n, m, k, w[N], sum_weight, ans;
bool dp[N][MAX_WEIGHT << 2];

int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
		sum_weight += w[i];
	}
	dp[0][sum_weight * 2] = true;
	for (int i = 1; i <= n; ++i) {
		for (int j = sum_weight; j <= sum_weight * 3; ++j) {
			dp[i][j] = dp[i][j] || dp[i - 1][j] || dp[i - 1][j - w[i]] || dp[i - 1][j + w[i]];
		}
	}
	for (int i = 1; i <= sum_weight; ++i) {
		if (dp[n][sum_weight + i] || dp[n][sum_weight - i]) {
			++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

---

第八题：杨辉三角形

题解：

#include <iostream>
#include <algorithm>
#define ll long long
#define N 100005
using namespace std;

ll n, c[N], p, q;
bool flag;

int main() {
	cin >> n;
	if (n == 1) { //特判 1
		cout << 1 << endl;
		return 0;
	}
	c[0] = c[1] = 1;
	p = 1;
	while (c[2] < n) {
		++p;
		for (int i = p / 2 + 1; i > 0; --i) {
			c[i] += c[i - 1];
		}
		c[p] = 1;
		q = lower_bound(c, c + p / 2, n) - c;
		if (c[q] == n) {
			flag = true;
			break;
		}
	}
	if (flag) {
		cout<<(1 + p) * p / 2ll + q + 1ll;
	}
	else {
		cout<<(1 + n) * n / 2ll + 2ll;
	}
	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

---

第九题：双向排序

题解： 此题比较简单，关键在于灵活应用数组排序，这里可以借助STL算法中的sort()函数，进行升降序排序，非常方便！

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

// 自定义降序排序谓词
bool cmp(int a, int b)
{
	return a > b;
}

int main()
{
	int n = 0; //序列长度
	int m = 0; //操作次数
	cin >> n >> m; //输入序列长度、操作次数
	vector<int> a;
	for (int i = 1; i <= n; i++)
		a.push_back(i); // 原数列
	for (int i = 0; i < m; i++)
	{
		int p, q;
		cin >> p >> q; // 输入排序类型、参数（排序临界点）
		if (p == 0)
			sort(a.begin(), a.begin() + q, cmp); //降序
		else
			sort(a.begin() + q - 1, a.end()); //升序
	}
	for (int i = 0; i < n;i++)
	{
		cout << a[i] << " ";
	}
	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

---

第十题：括号序列

---

由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！

后续正在加紧更新中，祝你们都超常发挥！