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

第十五届蓝桥杯省赛C/C++大学B组真题及赛后总结

作者：Monodyee | 2024-04-15 21:23:59

赞

踩

第十五届蓝桥杯省赛C/C++大学B组真题及赛后总结

目录

个人总结

C/C++ 组真题

握手问题

小球反弹

好数

R 格式

宝石组合

数字接龙

爬山

拔河

​编辑

再总结及后续规划

个人总结

第一次参加蓝桥杯，大二，以前都在在学技术，没有系统的学过算法。所以，还是花了挺多时间去备战的，因为暑假想找实习，就想拿个奖写简历上。备战了大概一个多月，学了一些基础的算法（dfs bfs 动态规划为主），刷了快200道题吧，但还是因为缺少经验，比赛时有点茫然了，然后大概率是寄了。

C/C++ 组真题

握手问题

这道第一题相对于去年还算是比较简单，排列 + 特殊情况处理即可

(50 * 49) / 2 - (6*7) / 2 = 1204，答案应该是正确的

小球反弹

这个应该是错了哈哈，答案是 1100325199.77，但和这个值挺像的，可惜只看答案。

前两道题都是数学问题，唉，后悔没有静下心来看第二题了。

好数

这道题直接暴力模拟即可，数据量没有很大。

  1. #include <iostream>
  2. using namespace std;
  3. int N;
  4. int main()
  5. {
  6. 	cin >> N;
  7. 	int Count = 0; // 记录总个数
  8. 	for (int i = 1; i <= N; i++)
  9. 	{
  10. 		// 判断某一个数是否是 好数
  11. 		int n = i; // 用 n 记录 i
  12. 		int flag = 1; // 1 此时计算的是 i 的奇数位, 0 表示此时计算的是 i 的偶数位
  13. 		int ret = 1; // 记录当前数否为 好数
  14. 		while (n > 0)
  15. 		{
  16. 			int end = n % 10;
  17. 			if (flag == 1)
  18. 			{
  19. 				if (end % 2 == 0)
  20. 				{
  21. 					ret = 0;
  22. 					break;
  23. 				}
  24. 				flag = 0;
  25. 			}
  26. 			else //  flag = 0
  27. 			{
  28. 				if (end % 2 != 0)
  29. 				{
  30. 					ret = 0;
  31. 					break;
  32. 				}
  33. 				flag = 1;
  34. 			}
  35. 			n /= 10;
  36. 		}
  37. 		if (ret == 1) Count++;
  38. 	}
  39. 	cout << Count << endl;
  40. 	return 0;
  41. }

R 格式

 

这道题看起来挺简单的，但如果要拿满分的话，需要使用字符串模拟，我直接使用 long long 了，应该能拿 50% 的分。

long long  50%代码

  1. #include <iostream>
  2. using namespace std;
  3. double d;
  4. int n;
  5. long long func(int n)
  6. {
  7. 	long long ret = 1;
  8. 	while (n--)
  9. 	{
  10. 		ret *= 2;
  11. 	}
  12. 	return ret;
  13. }
  14. int main()
  15. {
  16. 	cin >> n >> d;
  17. 	cout << (long long)(func(n) * d + 0.5) << endl;
  18. 	return 0;
  19. }

宝石组合

 这道题没有学过网上的那些公式算法，第一个想到的是暴击解法，时间复杂度O(N^3)，但思考了一会，发现是可以用哈希表来优化的，时间复杂度可以降到 O(N^2)。不过貌似依然过不了很多数据，第二个比较麻烦的点就是如果 S 相同的情况下要按字典序排顺序。

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <unordered_map>
  4. using namespace std;
  5. long long N;
  6. long long nums[100010];
  7. long long func(long long a, long long b, long long c = 1)
  8. {
  9. 	long long Max = max(a, max(b, c));
  10. 	long long i = 0;
  11. 	for (i = Max; i >= 0; i += Max)
  12. 	{
  13. 		if (i % a == 0 && i % b == 0 && i % c == 0) break;
  14. 	}
  15. 	return i;
  16. }
  17. long long get_S(long long a, long long b, long long c)
  18. {
  19. 	long long tmp = a * b * c * func(a, b ,c);
  20. 	long long ret = tmp / (func(a, b) * func(a, c) * func(b, c));
  21. 	return ret;
  22. }
  23. int main()
  24. {
  25. 	
  26. 	cin >> N;
  27. 	for (long long i = 1; i <= N; i++) cin >> nums[i];
  28. 	unordered_map<long long, pair<long long, long long>> hash;
  29. 	for (long long i = 2; i <= N; i++)
  30. 	{
  31. 		for (long long j = i - 1; j >= 1; j--)
  32. 			hash[nums[i] * nums[j]] = { j, i };
  33. 	}
  34. 	long long ret[3] = {100010, 100010, 100010};
  35. 	long long S = 0;
  36. 	for (long long i = 1; i <= N; i++)
  37. 	{
  38. 		for (auto& e : hash)
  39. 		{
  40. 			if (e.second.first != i && e.second.second != i)
  41. 			{
  42. 				long long tmp = get_S(nums[i], nums[e.second.first], nums[e.second.second]);
  43. 				if (tmp > S)
  44. 				{
  45. 					S = tmp;
  46. 					ret[0] = nums[i];
  47. 					ret[1] = nums[e.second.first];
  48. 					ret[2] = nums[e.second.second];
  49. 				}
  50. 				else if (tmp == S)
  51. 				{
  52. 					if (ret[0] > nums[i])
  53. 					{
  54. 						ret[0] = nums[i];
  55. 						ret[1] = nums[e.second.first];
  56. 						ret[2] = nums[e.second.second];
  57. 					}
  58. 					else if (nums[i] == ret[0] && ret[1] > nums[e.second.first])
  59. 					{
  60. 						ret[0] = nums[i];
  61. 						ret[1] = nums[e.second.first];
  62. 						ret[2] = nums[e.second.second];
  63. 					}
  64. 					else if (nums[i] == ret[0] && ret[1] == nums[e.second.first] && ret[2] > nums[e.second.second])
  65. 					{
  66. 						ret[0] = nums[i];
  67. 						ret[1] = nums[e.second.first];
  68. 						ret[2] = nums[e.second.second];
  69. 					}
  70. 				}
  71. 			}
  72. 		}
  73. 	}
  74. 	cout << ret[0] << " " << ret[1] << " " << ret[2] << endl;
  75. 	return 0;
  76. }
  77.

数字接龙

这道题，打眼一看是 dfs ，觉得自己会，就开始做，没想到做到最后，不会判断路径是否交叉，有点懵逼了，就直接将得到的所有可以走完的路径按字典序排序后取了第一个，最后估计还没有直接输出 - 1的人得的分多。还是比赛经验不够，应该先好好看完题再开始写代码的。

这里就不放我的错代码了，唉，看到正确答案就在自己负责调试的 vector 里，却没有办法去除错错误的答案...

知乎正确答案：

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int N = 11;
  5. int a[N][N];
  6. int dt[8][2] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };
  7. int n, k;
  8. vector<int> path;
  9. vector<int> res;
  10. bool ban[N][N][N][N];
  11. bool vis[N][N];
  12. void dfs(int sx, int sy)
  13. {
  14. 	if (!res.empty()) return;
  15. 	if (sx == n - 1 && sy == n - 1)
  16. 	{
  17. 		if (path.size() == n * n - 1) res = path;
  18. 		return;
  19. 	}
  20. 	if (path.size() == n * n - 1) return;
  21. 	for (int i = 0; i < 8; i++)
  22. 	{
  23. 		if (!res.empty()) return;
  24. 		int dx = dt[i][0], dy = dt[i][1];
  25. 		int x = sx + dx, y = sy + dy;
  26.  
  27. 		if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y] && a[x][y] == (a[sx][sy] + 1) % k)
  28. 		{
  29. 			if (dx != 0 && dy != 0 && ban[sx + dx][sy][sx][sy + dy]) continue;
  30.  
  31. 			ban[sx][sy][x][y] = ban[x][y][sx][sy] = true;
  32. 			vis[x][y] = true;
  33. 			path.push_back(i);
  34. 			dfs(x, y);
  35. 			path.pop_back();
  36. 			vis[x][y] = false;
  37. 			ban[sx][sy][x][y] = ban[x][y][sx][sy] = false;
  38. 		}
  39. 	}
  40. }
  41. int main()
  42. {
  43. 	scanf("%d%d", &n, &k);
  44. 	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &a[i][j]);
  45. 	vis[0][0] = true;
  46. 	dfs(0, 0);
  47. 	if (!res.empty())
  48. 	{
  49. 		for (auto x : res) printf("%d", x);
  50. 	}
  51. 	else
  52. 	{
  53. 		puts("-1");
  54. 	}
  55. 	return 0;
  56. }

爬山

 由于上一题浪费了太多时间，这道题也没有认真看，想了一下动态规划，感觉有点复杂，凭感觉写了一下...出来后看了答案才发现是 优先级队列 + 贪心

这是知乎上的贪心答案，但这个做法对于有的测试用例也是过不了的，我感觉还是应该用动态规划哈哈。

  1. int main()
  2. {
  3. 	priority_queue<int> heap;
  4. 	scanf("%d%d%d",&n,&P,&Q);
  5. 	for(int i=1;i<=n;i++) scanf("%d",&a[i]),heap.push(a[i]);
  6.  
  7. 	while(P||Q)
  8. 	{
  9. 		auto x=heap.top();
  10. 		heap.pop();
  11.  
  12. 		if(P&&Q)
  13. 		{
  14. 			int yl=_sqrt(x);
  15. 			int y2=x/2;
  16. 			if(y2<=yl)
  17. 			{
  18. 				Q--;
  19. 				heap.push(y2);
  20. 			}
  21. 			else
  22. 			{
  23. 				P--;
  24. 				heap.push(yl);
  25. 			}
  26. 		}
  27. 		else if(P)
  28. 		{
  29. 			int yl=_sqrt(x);
  30. 			P--;
  31. 			heap.push(yl);
  32. 		}
  33. 		else
  34. 		{
  35. 			int y2=x/2;
  36. 			Q--;
  37. 			heap.push(y2);
  38. 		}
  39. 	}
  40.  
  41. 	ll res=0;
  42. 	while(!heap.empty())
  43. 	{
  44. 		int x=heap.top();
  45. 		heap.pop();
  46. 		res+=x;
  47. 	}
  48. 	printf("%lld\n",res);
  49. 	return 0;
  50. }

拔河

这道题看都没看，唉，应该先看一下的......，起码得个暴力分

标准答案：指针 + 二分

  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. using namespace std;
  5. typedef long long ll;
  6. const int N = 1003;
  7. int a[N];
  8. int n;
  9. ll s[N];
  10. int main()
  11. {
  12. 	scanf("%d", &n);
  13. 	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), s[i] = s[i - 1] + a[i];
  14.  
  15. 	multiset<ll> S;
  16. 	for (int l = 1; l <= n; l++)
  17. 	{
  18. 		for (int r = l + 1; r <= n; r++)
  19. 		{
  20. 			S.insert(s[r] - s[l]);
  21. 		}
  22. 	}
  23. 	ll res = 0x3f3f3f3f;
  24. 	for (int r = 1; r < n; r++)
  25. 	{
  26. 		for (int l = 0; l < r; l++)
  27. 		{
  28. 			ll val = s[r] - s[l];
  29.  
  30. 			auto it = S.lower_bound(val);
  31. 			if (it != S.end())
  32. 			{
  33. 				ll ans = abs(*it - val);
  34. 				res = min(res, ans);
  35. 			}
  36. 			if (it != S.begin())
  37. 			{
  38. 				it--;
  39. 				ll ans = abs(*it - val);
  40. 				res = min(res, ans);
  41. 			}
  42. 		}
  43.  
  44. 		for (int r2 = r + 1; r2 <= n; r2++)
  45. 		{
  46. 			S.erase(S.find(s[r2] - s[r]));
  47. 		}
  48. 	}
  49. 	printf("%lld\n", res);
  50. 	return 0;
  51. }

再总结及后续规划

总结：自己算法还是太菜了（毕竟练习时长只有一个月），本次大概率可能是省二 ~ 省三了，省一的概率不大，不知道大三还有没有机会再打蓝桥杯，那时候应该要实习 / 考研吧。

接下来的安排，下周六还有一场天梯赛，打完后就要继续学技术了，冲一下暑假的日常实习，到时候就开始佛系做力扣每日一题了，不再花时间集中学算法了，算法竞赛的帮助，对于找开发的工作，有帮助，但最重要的还是技术得学到手，做项目。

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

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

  

闽ICP备14008679号