devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

蓝桥杯2020年第十一届C/C++B组（第二次）省赛习题题解_蓝桥杯2020年省赛b组

作者：AllinToyou | 2024-04-04 23:08:44

赞

踩

蓝桥杯2020年省赛b组

目录

试题A.门牌制作（拆分数字）

试题 B 既约分数（gcd）

试题C 蛇形填数（数学）

试题D 跑步锻炼（模拟） 

试题E 七段码（图论+并查集）

 试题F：成绩统计（格式化输出）

 试题G：回文日期（模拟）

试题H：子串分值和（哈希+乘法原理+数学）

试题I：平面切分（数学）

 试题J：字串排序（dp）

试题来源：蓝桥杯2020第十一届C语言B组省赛习题题解_shall_zhao的博客-CSDN博客_蓝桥杯c语言题目

试题A.门牌制作（拆分数字）

 思路解析：遍历1~2020，统计每个数字中2的次数，运用到拆分数字的基本算法

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int cal(int num)
  5. {
  6. 	int cnt = 0;
  7. 	while (num)
  8. 	{
  9. 		int j = num % 10;
  10. 		if (j == 2) cnt++;
  11. 		num /= 10;
  12. 	}
  13. 	return cnt;
  14. }
  15.  
  16. int main()
  17. {
  18. 	int res = 0;
  19. 	for (int i = 1; i <= 2020; i++)
  20. 	{
  21. 		res += cal(i);
  22. 	}
  23.  
  24. 	cout << res << endl;//答案为624
  25.  
  26. 	return 0;
  27. }

试题 B 既约分数（gcd）

 思路解析：两层内外循环遍历1~2020，用欧几里得算法判断是否是两数的最大公约数为1，统计个数即可

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int gcd(int a, int b)
  5. {
  6. 	return b ? gcd(b, a % b) : a;
  7. }
  8.  
  9. int main()
  10. {
  11. 	int res = 0;
  12. 	for(int i=1;i<=2020;i++)
  13. 		for (int j = 1; j <= 2020; j++)
  14. 		{
  15. 			if (gcd(i, j) == 1) res++;
  16. 		}
  17. 	cout << res << endl;//答案为：2481215
  18.  
  19. 	return 0;
  20. }

试题C 蛇形填数（数学）

问题： 根据此规律，推断第20行20列的数字是多少，其中第2行第2列的数字为5

 思路解析：

（1）对于奇数行有：比如说数字‘4’的那一行，则有：从它向它的右上角方向依次+1

（2）对于偶数行有：比如说数字‘10’的那一行，则有：从它向它的右上角方向依次-1

那么同理：

（3）对于奇数列有：比如说数字‘6’的那一列，则有：从它向它的左下角方向依次-1

（4）对于偶数列有：比如说数字‘7’的那一列，则有：从它向它的左下角方向依次+1

那么就有：

定义一个计数器cnt=1，循环for一次，同时枚举（i）行数和列数，如果这个（i）为奇数，那么就让它对应（1）情况，让它向右上角方向++；同理如果这个（i）为偶数，那么就让它对应（4）情况，让它向它的左下角方向++，其中是将cnt的值赋给这个二维数组，并++，最后输出对应行数和列数即可

  1. #include<iostream>
  2. using namespace std;
  3. const int N = 110;
  4. int a[N][N];
  5.  
  6. int main()
  7. {
  8. 	int cnt = 1;
  9. 	int x, y;
  10. 	for (int i = 1; i <= N; i++)
  11. 	{
  12. 		if (i % 2 == 1)
  13. 		{
  14. 			for (x = i, y = 1; x >= 1 && y <= i; x--, y++)
  15. 			{
  16. 				a[x][y] = cnt++;
  17. 			}
  18. 		}
  19. 		else
  20. 		{
  21. 			for (x = 1, y = i; x <= i && y >= 1; x++, y--)
  22. 			{
  23. 				a[x][y] = cnt++;
  24. 			}
  25. 		}
  26. 	}
  27. 	cout << a[20][20] << endl;
  28.  
  29. 	return 0;
  30. }

试题D 跑步锻炼（模拟） 

问题：

 思路解析：

最外层循环枚举年份，接着二判断是否是闰年，如果是闰年，那么就让原先定义好的二月天数改为29，接着内循环枚举月份，接着内循环枚举月份中的天数，如果天数是1，或者为周一，那么就让sum+=2，否则则为普通日子：让sum+=1，枚举完一天后，让星期++，并对7取模，注意枚举该年份后，需要将2月的天数重新修改为28

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int months[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
  5. int main()
  6. {
  7. 	int year1 = 2000, year2 = 2020;
  8. 	int month1 = 1, month2 = 10;
  9. 	int day1 = 1, day2 = 1;
  10. 	int week = 6;
  11.  
  12. 	long long sum = 0;
  13.  
  14. 	for (year1; year1 <= year2; year1++)
  15. 	{
  16. 		if ((year1 % 400 == 0) || (year1 % 4 == 0 && year1 % 100 != 0))
  17. 		{
  18. 			months[2] = 29;
  19. 		}
  20. 		for (int i = 1; i <= 12; i++)
  21. 		{
  22. 			for (int day = 1; day <= months[i]; day++)
  23. 			{
  24. 				if (day == 1 || week == 1)
  25. 				{
  26. 					sum += 2;
  27. 				}
  28. 				else
  29. 				{
  30. 					sum += 1;
  31. 				}
  32. 				week = (week + 1) % 7;
  33. 				if (year1 == 2020 && i == 10 && day == 1)
  34. 				{
  35. 					cout << sum << endl;//答案为：8879
  36. 					return 0;
  37. 				}
  38. 			}
  39. 		}
  40. 		months[2] = 28;
  41. 	}
  42.  
  43. 	return 0;
  44. }

试题E 七段码（图论+并查集）

 

 题目概述：

必须要相邻才能发光，也就是所有开着的灯必须是连通的，才能算是一种合法方案，求合法的方案数

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int use[10];
  5. int ans, e[10][10], father[10];
  6.  
  7. void init()
  8. {
  9.     //连边建图
  10.     //a b c d e f g
  11.     //1 2 3 4 5 6 7
  12.     e[1][2] = e[1][6] = 1;
  13.     e[2][1] = e[2][7] = e[2][3] = 1;
  14.     e[3][2] = e[3][4] = e[3][7] = 1;
  15.     e[4][3] = e[4][5] = 1;
  16.     e[5][4] = e[5][6] = e[5][7] = 1;
  17.     e[6][1] = e[6][5] = e[6][7] = 1;
  18. }
  19.  
  20. int  find(int a)
  21. {
  22.     //并查集
  23.     return (a == father[a]) ? a : father[a] = find(father[a]);
  24.  
  25. }
  26. void dfs(int d)
  27. {
  28.     if (d > 7)//一个七段管的所有灯的状态已经列举完了
  29.     {
  30.         for (int i = 1; i <= 7; i++)
  31.         {
  32.             father[i] = i;//初始化
  33.         }
  34.         for (int i = 1; i <= 7; i++)
  35.         {
  36.             for (int j = 1; j <= 7; j++)
  37.             {//如果存在这条边 且 开i节点 且 开j节点
  38.                 if (e[i][j] && use[i] && use[j])
  39.                 {
  40.                     int fa = find(i), fb = find(j);//寻找i，j对于的祖宗节点
  41.                     if (fa != fb)//如果祖宗节点不同，证明未连通
  42.                     {
  43.                         father[fa] = fb;//连通 a b
  44.                     }
  45.                 }
  46.             }
  47.         }
  48.  
  49.         int k = 0;
  50.         for (int i = 1; i <= 7; i++)
  51.         {
  52.             if (use[i] && i == father[i])//如果它被用过 且 它等于它的祖宗节点
  53.                 k++;
  54.         }
  55.         if (k == 1)//只有一个父节点，就说明他们是相连的
  56.             ans++;
  57.         return;
  58.     }
  59.  
  60.     use[d] = 0;//不选
  61.     dfs(d + 1);
  62.  
  63.     use[d] = 1; //选
  64.     dfs(d + 1);
  65.     use[d] = 0;//归位
  66. }
  67. int main()
  68. {
  69.     init();
  70.     dfs(1);
  71.     cout << ans << endl;
  72.     return 0;
  73. }

 试题F：成绩统计（格式化输出）

 

格式化输出的陷阱：//格式化输出%的陷阱：要输入%%才表示 %

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5. 	int n;
  6. 	cin >> n;
  7. 	double a = 0;
  8. 	double b = 0;
  9. 	int x;
  10. 	for (int i = 1; i <= n; i++)
  11. 	{
  12. 		cin >> x;
  13. 		if (x >= 60) a++;
  14. 		if (x >= 85) b++;
  15. 	}
  16.     //格式化输出%的陷阱：要输入%%才表示 %
  17. 	printf("%.0lf%%\n%.0lf%%", a / (n/100.0), b / (n/100.0));
  18.  
  19. 	return 0;
  20. }

 试题G：回文日期（模拟）

 

思路解析：

本题于与Acwing上的回文日期差不多   466. 回文日期 - AcWing题库

通过Acwing的这题，可以得到的经验是：遍历前四位数，然后进行回文构造，然后再判断构造出来的回文串是否满足日期的标准，即判断它是否是合法的日期，即可

先贴一下Acwing上的回文日期的答案：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int months[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
  9.  
  10. bool check(int date)
  11. {
  12.     int year = date / 10000;
  13.     int month = date % 10000 / 100;
  14.     int day = date % 100;
  15.  
  16.     if (!month || month >= 13 || !day) return false;
  17.  
  18.     if (month != 2 && day > months[month]) return false;
  19.     if (month == 2)
  20.     {
  21.         bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;
  22.         if (day > 28 + leap) return false;
  23.     }
  24.  
  25.     return true;
  26. }
  27.  
  28. int main()
  29. {
  30.     int date1, date2;
  31.     cin >> date1 >> date2;
  32.  
  33.     int res = 0;
  34.     for (int i = 1000; i < 10000; i++)
  35.     {
  36.         int x = i, r = i;//构造后四个：先构造回文串，再判断其是否合法
  37.         for (int j = 0; j < 4; j++) r = r * 10 + x % 10, x /= 10;
  38.  
  39.         if (r >= date1 && r <= date2 && check(r)) res++;
  40.     }
  41.  
  42.     printf("%d\n", res);
  43.     return 0;
  44. }

那么此题与Acwing上不同的地方在于：

输入是一个合法的八位数的日期

第一个输出是，这个日期之后的第一个合法的回文日期

第二个输出是，这个日期之后的第一个符合ABABBABA的日期

注意注释的一些细节即可

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4.  
  5. int months[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
  6.  
  7. bool check(int date)//判断是否位合法日期
  8. {
  9. 	int year = date / 10000;
  10. 	int month = date % 10000 / 100;
  11. 	int day = date % 100;
  12.  
  13. 	//如果月份为0 || 月份大于等于13 || 日数为0
  14. 	if (!month || month >= 13 || !day) return false;
  15.  
  16. 	//如果月份！=2   && 日数大于该月的天数
  17. 	if (month != 2 && day > months[month]) return false;
  18. 	if (month == 2)
  19. 	{
  20. 		bool leap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
  21. 		if (day > 28 + leap) return false;//如果二月的天数>大于原本的二月天数+（可能的闰年+1的天数）
  22. 	}
  23. 	return true;
  24. }
  25.  
  26. bool checkAB(int s)//判断AB
  27. {
  28. 	bool flag = false;
  29. 	int y, m, d;
  30. 	y = s / 10000;   // 得到年份 
  31. 	m = (s / 100) % 100; // 得到月份  (BA)
  32. 	d = s % 100;  // 得到日  (BA)
  33.  
  34. 	int k, n;
  35. 	k = y / 100;  // AB 
  36. 	n = y % 100; // AB 
  37. 	if (k == n && m == d)  // 判断是否为ABABBABA 
  38. 	{
  39. 		flag = true;
  40. 	}
  41. 	return flag;
  42. }
  43.  
  44. int main()
  45. {
  46. 	int date;
  47. 	cin >> date;
  48.  
  49. 	int flag = 0;
  50. 	for (int i = (date/10000) +1; i <= 9999; i++)//枚举四位数的年份
  51. 	{		//举例 i=1234
  52. 		int left = i;
  53. 		int right = i;//构造出来的回文串，构造出来的回文串即：12344321
  54. 		for (int j = 0; j < 4; j++)
  55. 		{
  56. 			right = right * 10 + left % 10;//1234*10+1234%10
  57. 			left = left / 10;//得到left的下一位
  58. 		}//因为是按顺序进行的枚举，所以先符合条件的第一个必然是顺序最小的那一个
  59. 		if (check(right))
  60. 		{
  61. 			flag++;//保证第一个符合的回文串只有一个输出
  62. 			if (flag == 1) cout << right << endl;
  63. 			if (checkAB(right))
  64. 			{
  65. 				cout << right << endl;
  66. 				return 0;
  67. 			}
  68. 		}
  69. 	}
  70. }

试题H：子串分值和（哈希+乘法原理+数学）

 （1）暴力思路解析：哈希表存储字母出现的次数，查看哈希表中是否有多个字母即可

最外层循环枚举一次走的步长

        第二层循环枚举左端点

                第三层循环将左端点~~~左端点+步长的这一段距离 赋值

                查找哈希表中是否存在元素，如果存在即 res++

                memset：重新初始化哈希表

cout<<res<<endl;

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<string>
  5. using namespace std;
  6.  
  7. int main()
  8. {
  9. 	string s;
  10. 	cin >> s;
  11.  
  12. 	int n = s.size();
  13. 	int cnt[27] = { 0 };
  14. 	int res = 0;
  15.  
  16. 	for (int len = 1; len <= n; len++)//枚举长度
  17. 	{
  18. 		for (int i = 0; i + len <= n; i++)//枚举左端点
  19. 		{
  20. 			for (int j = i; j < i + len; j++)//将该段进行填充
  21. 			{
  22. 				cnt[s[j] - 'a']++;
  23. 			}
  24. 			for (int k = 0; k < 26; k++)//查找
  25. 			{
  26. 				if (cnt[k] != 0) res++;
  27. 			}
  28. 			memset(cnt, 0, sizeof cnt);//重新赋值为：0
  29. 		}
  30. 	}
  31.  
  32. 	cout << res << endl;
  33.  
  34. 	return 0;
  35. }

 （2）小优化：变成两层循环

  1. #include<iostream>
  2. #include<string>
  3. #include<cstring>
  4. using namespace std;
  5.  
  6. const int N = 10010;
  7. char str[N];
  8. bool st[26];
  9.  
  10. int main()
  11. {
  12. 	scanf("%s", str + 1);
  13. 	int n = strlen(str + 1);
  14.  
  15. 	long long ans = 0;
  16. 	for (int i = 1; i <= n; i++)
  17. 	{
  18. 		memset(st, 0, sizeof st);
  19. 		int t = str[i] - 'a';
  20. 		st[t] = true;
  21. 		int cnt = 1;
  22. 		ans += cnt;
  23. 		for (int j = i - 1; j >= 1; j--)
  24. 		{
  25. 			int t = str[j] - 'a';
  26. 			if (!st[i])
  27. 			{
  28. 				cnt++;
  29. 				st[t] = true;
  30. 			}
  31. 			ans += cnt;
  32. 		}
  33. 	}
  34.  
  35. 	printf("%lld\n", ans);
  36.  
  37. 	return 0;
  38. }

 （3）大优化

第十一届蓝桥杯 ——子串分值和_六级不考550+不改名-CSDN博客

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4. typedef long long ll;
  5. int last[127];
  6.  
  7. int main()
  8. {
  9. 	string s;
  10. 	cin >> s;
  11.  
  12. 	int n = s.size();
  13. 	s = ' ' + s;
  14.  
  15. 	ll ans = 0;
  16. 	for (int i = 1; i <= n; i++)
  17. 	{
  18. 		ans += (ll)(i - last[s[i]]) * (n - i + 1);
  19. 		last[s[i]] = i;
  20. 	}
  21.  
  22. 	cout << ans << endl;
  23.  
  24. 	return 0;
  25. }

试题I：平面切分（数学）

  1. #include<iostream>
  2. #include<set>
  3. using namespace std;
  4.  
  5. typedef pair<double, double> pdd;
  6. set<pdd> lines;
  7. int res = 1;
  8.  
  9. int cmp(double c, double d)//求此条直线与之前所有直线的交点的个数
  10. {
  11. 	set<pdd> points;
  12. 	pdd it;
  13. 	for (auto i = lines.begin(); i != lines.end(); i++)
  14. 	{
  15. 		double a = i->first;
  16. 		double b = i->second;
  17. 		if (a != c)//斜率不同，则两条直线不重合
  18. 		{
  19. 			it.first = (d - b) / (a - c);//求交点的横坐标
  20. 			it.second = c * it.first + d;//纵坐标
  21. 			points.insert(it);
  22. 		}
  23. 	}
  24. 	return points.size();
  25. }
  26.  
  27. int main()
  28. {
  29. 	int n;
  30. 	cin >> n;
  31.  
  32. 	while (n--)
  33. 	{
  34. 		double a, b;
  35. 		cin >> a >> b;
  36. 		int count1 = lines.size();
  37. 		lines.insert({ a,b });
  38. 		if (lines.size() != count1)
  39. 		{
  40. 			res++;
  41. 			res += cmp(a, b);
  42. 		}
  43. 	}
  44.  
  45. 	cout << res << endl;
  46.  
  47. 	return 0;
  48. }

 试题J：字串排序（dp）

在这里插入图片描述

 第十一届蓝桥杯——字串排序（DP）_Dripping Blog-CSDN博客_字串排序

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/361777
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号