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

蓝桥杯2015年第六届C/C++ B组省赛习题题解_2015年蓝桥杯c语言b组题解

作者：我家小花儿 | 2024-04-26 11:30:33

赞

踩

2015年蓝桥杯c语言b组题解

目录

第一题：奖券数目

第二题：星系炸弹（日期计算）

第三题：三羊献瑞（全排列）

第四题：格子中输出

第五题：九数组分数（dfs）

 第六题：加法变乘法（枚举）

第七题：牌型种数（dfs+dp）

第八题：移动距离（数学+多情况+曼哈顿距离）

第九题：垒骰子（矩阵快速幂）

第十题：生命之树（dfs）

题目来源：

2015年第六届C/C++ B组蓝桥杯省赛真题_元气算法的博客-CSDN博客_2015年蓝桥杯c语言b组试题

第一题：奖券数目

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. bool check(int num)
  5. {
  6. 	while (num)
  7. 	{
  8. 		int j = num % 10;
  9. 		if (j == 4) return false;
  10. 		num /= 10;
  11. 	}
  12. 	return true;
  13. }
  14.  
  15. int main()
  16. {
  17. 	int cnt = 0;
  18. 	for (int i = 10000; i <= 99999; i++)
  19. 	{
  20. 		if (check(i)) cnt++;
  21. 	}
  22.  
  23. 	cout << cnt << endl;//52488
  24.  
  25. 	return 0;
  26. }

第二题：星系炸弹（日期计算）

 解析：

其实1000天也不难算，手算即可，但还是严谨的用代码给出答案

  1. #include<iostream>
  2. using namespace std;
  3. int months[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
  4. bool is_leap(int year)
  5. {
  6. 	return (year % 400 == 0 || (year % 100 != 0 && year % 4 == 0));
  7. }
  8.  
  9. int main()
  10. {
  11. 	int year = 2014;
  12. 	int month = 11;
  13. 	int day = 9;
  14. 	
  15. 	int T = 1000;
  16. 	while (T--)
  17. 	{
  18. 		day++;
  19. 		if (month == 2)
  20. 		{
  21. 			if (is_leap(year)) months[2] = 29;//如果是闰年
  22. 		}
  23. 		if (day > months[month])//如果天数已经大于该月的天数时
  24. 		{
  25. 			if (month == 12)//如果该月是12月，那么就++年
  26. 			{
  27. 				year++;
  28. 				month = 1;//月份重新变为1
  29. 				day = 1;
  30. 			}
  31. 			else month++, day = 1;//否则只是月份++
  32. 		}
  33. 		months[2] = 28;//还原
  34. 	}
  35.  
  36. 	printf("%d-%02d-%02d\n", year, month, day);//2017-08-05
  37.  
  38. 	return 0;
  39. }

第三题：三羊献瑞（全排列）

 解析：

由小学数学可知：

三：一定是数字1，这个不要问为什么，就是这样的，自己模拟一下

然后就是全排列找出所有的可能，然后进行对应数字之间的判断即可

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7. 	int num[9] = { 0,2,3,4,5,6,7,8,9 };
  8. 	do {
  9. 		if (num[0] != 0)//数字的开头不能为0
  10. 		{
  11. 			int a = num[0] * 1000 + num[1] * 100 + num[2] * 10 + num[3];
  12. 			int b = 1000 + num[4] * 100 + num[5] * 10 + num[1];
  13. 			int c = 10000 + num[4] * 1000 + num[2] * 100 + num[1] * 10 + num[6];
  14. 			if (a + b == c)
  15. 			{
  16. 				cout << "1" << num[4] << num[5] << num[1] << endl;
  17. 				break;//1085
  18. 			}
  19. 		}
  20. 	} while (next_permutation(num, num + 9));
  21.  
  22. 	return 0;
  23. }

第四题：格子中输出

第五题：九数组分数（dfs）

  1. #include <stdio.h>
  2. void test(int x[])
  3. {
  4. 	int a = x[0]*1000 + x[1]*100 + x[2]*10 + x[3];
  5. 	int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];
  6. 	
  7. 	if(a*3==b) printf("%d / %d\n", a, b);
  8. }
  9.  
  10. void f(int x[], int k)
  11. {
  12. 	int i,t;
  13. 	if(k>=9){
  14. 		test(x);
  15. 		return;
  16. 	}
  17. 	
  18. 	for(i=k; i<9; i++){
  19. 		{t=x[k]; x[k]=x[i]; x[i]=t;}
  20. 		f(x,k+1);
  21. 		_____________________________________________ // 填空处
  22. 	}
  23. }
  24. 	
  25. int main()
  26. {
  27. 	int x[] = {1,2,3,4,5,6,7,8,9};
  28. 	f(x,0);	
  29. 	return 0;
  30. }
  31.

解析：

我已经看到蓝桥杯的f函数就已经知道它是dfs了，没毛病啊兄弟们，毕竟还有个return，都知道是递归了，递归之后要还原，那么就要知道上一步是干什么，交换是吧，那么再交换一次就还原了，即可

所以答案是：{t=x[k]; x[k]=x[i]; x[i]=t;}

 第六题：加法变乘法（枚举）

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6. 	for (int i = 1; i < 49; i ++)                                 // 枚举第一个 * 左边的数字
  7. 		for (int j = i + 2; j < 49; j ++)                         // 枚举第二个 * 左边的数字
  8. 		{
  9. 			if(1225 - 2*i-1 - 2*j-1 + i*(i+1) + j*(j+1) == 2015) 
  10. 			   cout << i << endl;
  11. 		}	
  12. 	
  13. 	return 0;
  14. }

第七题：牌型种数（dfs+dp）

 DFS：

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int ans;
  5.  
  6. void dfs(int kind, int sum)
  7. {
  8. 	if (sum > 13) return;
  9. 	if (kind == 14)
  10. 	{
  11. 		if (sum == 13) ans++;
  12. 		return;
  13. 	}
  14. 	for (int i = 0; i <= 4; i++)
  15. 	{
  16. 		dfs(kind + 1, sum + i);//这种类型，选多少张牌
  17. 	}
  18. }
  19.  
  20. int main()
  21. {
  22. 	dfs(1, 0);
  23. 	cout << ans << endl;
  24. 	return 0;
  25. }

动态规划dp：

dp分析：

（1）dp数组的含义：dp[i][k]，i：牌的种类，共13种；k：剩余需要选取多少张牌

（2）dp数组的属性：方案数

（3）dp数组的递推公式：dp[i][k]=

<1>上一类牌，选了0张，dp[i-1][k];

<2>上一类牌，选了一张，dp[i-1][k+1];

<3>上一类牌，选了两张，dp[i-1][k+2];

<3>上一类牌，选了三张，dp[i-1][k+3];

<4>上一类牌，选了四张，dp[i-1][k+4];

这样枚举有些麻烦，所以用一层for循环代替

（4）dp数组的初始化：

由递推公式可知，必须要初始化一个dp[1][一个比较大的数]，那么这个比较大的数是多少呢？

对于第一类牌，可以拿0~4张，那么就有：

  1. for(int i=9; i<=13; i++){
  2. 		num[1][i] = 1;

需要倒过来想：

（5）dp数组的遍历顺序：

无特殊要求，两层正序即可

（6）dp数组的返回值：

根据定义从前13类牌中选，当剩余需求排数为0时，即可满足题意要求

  1. #include<iostream>
  2. using namespace std;
  3. int dp[14][14];
  4.  
  5. int main()
  6. {
  7. 	for (int i = 9; i <= 13; i++) dp[1][i] = 1;//当剩余9~13张要选时，均初始化方案数为1
  8.  
  9. 	for(int i=2;i<=13;i++)//枚举牌的种类
  10. 		for(int k=0;k<=13;k++)//枚举剩余需要选的牌的数量
  11. 			for (int prek = k; prek <= k + 4 && prek <= 13; prek++)//只能选1~4张该种牌
  12. 			{
  13. 				dp[i][k] += dp[i - 1][prek];//该类牌的数量=原本+上一类牌选取的四种方案数
  14. 			}
  15. 	cout << dp[13][0] << endl;
  16.  
  17. 	return 0;
  18. }

第八题：移动距离（数学+多情况+曼哈顿距离）

  1. #include <cstring>
  2. #include <iostream>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     int w, m, n;
  9.     cin >> w >> m >> n;
  10.     m --, n -- ;//为了对应
  11.  
  12.     int x1 = m / w, x2 = n / w;
  13.     int y1 = m % w, y2 = n % w;
  14.     if (x1 % 2) y1 = w - 1 - y1;//奇偶情况
  15.     if (x2 % 2) y2 = w - 1 - y2;
  16.  
  17.     cout << abs(x1 - x2) + abs(y1 - y2) << endl;
  18.  
  19.     return 0;
  20. }

第九题：垒骰子（矩阵快速幂）

第六届蓝桥杯【省赛试题9】垒骰子 ( 矩阵快速幂 )_i逆天耗子丶的博客-CSDN博客

 AcWing 1217. 垒骰子 - AcWing

第十题：生命之树（dfs）

 

解析：

[AcWing蓝桥杯]之复杂DP（C++题解）_lihua777的博客-CSDN博客

vector模拟单链表：

  1. #include<iostream>
  2. #include<vector>
  3. #include<cmath>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. const int N = 1e5 + 5;
  8.  
  9. int n, w[N];
  10. ll f[N];
  11. vector<int>e[N];
  12.  
  13.  
  14. void dfs(int u, int fa)
  15. {
  16.     f[u] = w[u];
  17.     int len = e[u].size();
  18.     for (int i = 0; i < len; i++)
  19.     {
  20.         int j = e[u][i];
  21.         if (j != fa)
  22.         {
  23.             dfs(j, u);
  24.             f[u] += max(0ll, f[j]);
  25.         }
  26.     }
  27.     return;
  28. }
  29.  
  30.  
  31. int main()
  32. {
  33.     cin >> n;
  34.     for (int i = 1; i <= n; i++)
  35.     {
  36.         cin >> w[i];
  37.     }
  38.     for (int i = 0; i < n - 1; i++)
  39.     {
  40.         int x, y;
  41.         cin >> x >> y;
  42.         e[x].push_back(y);
  43.         e[y].push_back(x);
  44.     }
  45.     dfs(1, -1);
  46.     ll res = f[1];
  47.     for (int i = 2; i < n; i++)res = max(res, f[i]);
  48.     printf("%lld",res);
  49. }

数组模拟单链表：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long LL;
  8.  
  9. const int N = 100010, M = N * 2;
  10.  
  11. int n;
  12. int w[N];
  13. int h[N], e[M], ne[M], idx;
  14. LL f[N];
  15.  
  16. void add(int a, int b)
  17. {
  18.     e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
  19. }
  20.  
  21. void dfs(int u, int father)
  22. {
  23.     f[u] = w[u];
  24.     for (int i = h[u]; i != -1; i = ne[i])
  25.     {
  26.         int j = e[i];
  27.         if (j != father)
  28.         {
  29.             dfs(j, u);
  30.             f[u] += max(0ll, f[j]);
  31.         }
  32.     }
  33. }
  34.  
  35. int main()
  36. {
  37.     scanf("%d", &n);
  38.     memset(h, -1, sizeof h);
  39.  
  40.     for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
  41.     for (int i = 0; i < n - 1; i ++ )
  42.     {
  43.         int a, b;
  44.         scanf("%d%d", &a, &b);
  45.         add(a, b), add(b, a);
  46.     }
  47.  
  48.     dfs(1, -1);
  49.  
  50.     LL res = f[1];
  51.     for (int i = 2; i <= n; i ++ ) res = max(res, f[i]);
  52.  
  53.     printf("%lld\n", res);
  54.  
  55.     return 0;
  56. }

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

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

  

闽ICP备14008679号