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

灰太狼 2023-01-15 11:24 129阅读 0赞

### 文章目录 ###

*   *  第一题：卡片
     *  第二题：直线
     *  第三题：货物摆放
     *  第四题：路径
     *  第五题：回路计数
     *  第六题：时间显示
     *  第七题：砝码称重
     *  第八题：杨辉三角形
     *  第九题：双向排序
     *  第十题：括号序列

--------------------

**相关文章：**

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

--------------------

## 第一题：卡片 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]  
**解析：**

首先要理清题目：从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;
    }

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

--------------------

## 第二题：直线 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]  
**解析：** **总的直线=斜直线+横直线+竖直线**。横直线和竖直线很容易统计，分别是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;
    }

--------------------

## 第三题：货物摆放 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 2]  
**解析：** 先找出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;
    }

--------------------

## 第四题：路径 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 3]  
**题解：** 本题考点就是求最小公倍数和最短路径算法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;
    }

--------------------

## 第五题：回路计数 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 4]

--------------------

## 第六题：时间显示 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 5]  
**解析：**

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

*  注意单位转换，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;
    }

--------------------

## 第七题：砝码称重 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 6]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 7]  
**题解：** 采用动态规划，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;
    }

--------------------

## 第八题：杨辉三角形 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 8]  
**题解：**

#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;
    }

--------------------

## 第九题：双向排序 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 9]  
**题解：** 此题比较简单，关键在于灵活应用数组排序，这里可以借助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;
    }

--------------------

## 第十题：括号序列 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 10]

--------------------

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

![在这里插入图片描述][2020090613542669.png_pic_center]  
***后续正在加紧更新中，祝你们都超常发挥！***

[2020_10]: https://ai-wx.blog.csdn.net/article/details/109214863
[2020_4]: https://ai-wx.blog.csdn.net/article/details/109067927
[2020_3]: https://ai-wx.blog.csdn.net/article/details/109108840
[2019_4]: https://blog.csdn.net/wjinjie/article/details/115747848?spm=1001.2014.3001.5501
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]: /images/20221022/1c08166996d74bdab6d445da397c6c80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]: /images/20221022/74946dd8530843158efdf3a70c12215d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 2]: /images/20221022/134bcf639a3e4dc58723edb4249ed4f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 3]: /images/20221022/0617b06b1f054746b4d9d475115eb813.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 4]: /images/20221022/212789aee6b3453bb867820aa1fb46a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 5]: /images/20221022/44fec4f835a74e4ea0a3ac99a38f8c7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/2021050800454766.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 7]: /images/20221022/0fa51d325873402d978f9fe6a8c3fd7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 8]: /images/20221022/31462f53eb6941e0b322c3c1f6d0bf9a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 9]: /images/20221022/a25c8cbb4c4f4f03a15897914175a131.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 10]: /images/20221022/e1787719b34d45e08ff947293d78bc59.png
[2020090613542669.png_pic_center]: /images/20221022/947fd7f6609f4f26bff01e77ce9569a5.png