本文主要是介绍蓝桥杯第六届c++大学B组详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言:
看了很多博客以及视频讲解,感觉都不是很清楚,比较模棱两可,所以干脆自己一边想,一边写博客,也可帮助到其他人,都是根据自己的逻辑来尽量清楚简单的讲清楚题目,喜欢的不要吝啬三连,给博主点动力。
目录
1.奖券数目
2.星系炸弹
3.三羊献瑞
4.移动距离
5.垒骰子
6.生命之树
1.奖券数目
0奖券数目 - 蓝桥云课 (lanqiao.cn)
题目解析:
就是判断每一位是否有4,将不含4的数进行累加。
#include <iostream>
using namespace std;bool is_four(int i)
{while(i > 0){int t = i % 10;if(t == 4)return false;i = i / 10;}return true;
}int main()
{int ret = 0;for(int i = 10000; i <= 99999; i++){if(is_four(i)){ret++;}}cout << ret << endl;return 0;
}
2.星系炸弹
0星系炸弹 - 蓝桥云课 (lanqiao.cn)
题目讲解:就是实现一个日期类;
#include<iostream>
using namespace std;class Date
{public:Date(int year, int month, int day): _year(year),_month(month),_day(day){}int getmonthday(int year, int month){int Month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int day = Month[month];//闰年情况;if(month == 2 && ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))){day++;}return day;}Date& operator+=(int day){_day += day;//将day全部转化为年和月while(_day > getmonthday(_year, _month)){_day -= getmonthday(_year, _month);_month++;if(_month == 13){_year++;_month = 1;}}return *this;}void print(){cout << _year << _month << _day << endl;}private:int _year;int _month;int _day;
};int main()
{int year, month, day, addday;cin >> year >> month >> day >> addday;Date d1(year,month,day);d1 += addday;d1.print();return 0;
}
3.三羊献瑞
0三羊献瑞 - 蓝桥云课 (lanqiao.cn)
题目解析:这题本质就是模拟,根据题目意思依葫芦画瓢,然后进行全排列,得到最后答案。
题目说相同的汉字就是相同的数字,不相同反之。
如果使用到algorithm库函数里面的next_permutation就会很好做,那我们看看这个接口。
本质就是一个用来全排列的接口,但是前提是数组有序。可以将排列的数用下面图表示
#include <iostream>
#include<algorithm>
using namespace std;int main()
{//0-9个数字进行排列;int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};int sum1 = 0, sum2 = 0, sum3 = 0;while(next_permutation(a, a + 10)){//细节处理if(a[0] != 0 && a[4] != 0){//处理算数sum1 = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];sum2 = a[4] * 1000 + a[5] * 100 + a[6] * 10 + a[1];sum3 = a[4] * 10000 + a[5] * 1000 + a[2] * 100 + a[1] * 10 + a[7];if(sum1 + sum2 == sum3){cout << a[4] << a[5] << a[6] << a[1];break;}}}return 0;
}
4.移动距离
0移动距离 - 蓝桥云课 (lanqiao.cn)
题目解析:本质就是考数学题目,算出m号房间和n号房间之间的距离,由于这个题目是按照Z字形来安置房间的。那么就会分为奇偶排楼的不同区别。
先来看房间的行号,row = m % w;
列号就要分奇偶来划分了;注意这里列是从1开始排楼的。
偶数列发现是递减序列,我们可以根据找到第一个位置的房间号(行号*w)减去要找的房间号得到列号,下标从1开始还要+1. col = rol * w - m + 1;
奇数列是递增序列,先找到最后一个房间号(行号*w)减去找的房间号的差值,再用w为房间个数 - 差值就是列号。col = w - (rol * w -m +1);
#include <iostream>
using namespace std;int main()
{//先搞定输入;int w, m, n;cin >> w >> m >> n;int rowM = m % w == 0 ? m / w : m / w + 1;int rowN = n % w == 0 ? n / w : n / w + 1;int colM = 0, colN = 0;//偶数情况if(rowM % 2 == 0){colM = rowM * w - m + 1;}else{colM = w - (rowM * w - m);}if(rowN % 2 == 0){colN = rowN * w - n + 1;}else{colN = w - (rowN * w - n);}int sum = abs(colM - colN) + abs(rowM - rowN);cout << sum << endl; return 0;
}
5.垒骰子
0垒骰子 - 蓝桥云课 (lanqiao.cn)
题目解析:根据题目意思,下图,我们可以创建一个数组来记录每面的对面是什么,
题目解析: 首先就要创建一个冲突数组将骰子的正面和对面的冲突记录,以及冲突面的数组.还有因为想象一下是一个魔方,那么四个面都可以进行翻转.所以还要乘以4.
第一种代码只可以通过一个用例,因为dfs进行太多层那么就要优化.
#include<iostream>
using namespace std;const long long MOD = 1000000007;
int op[7];//记录对立面;
bool conflict[7][7];
int m, n;void init()
{op[1] = 4;op[2] = 5;op[3] = 6;op[4] = 1;op[5] = 2;op[6] = 3;
}long long int f(int up, int n)
{if(n == 0)return 4;long long int ans = 0;for(int uup = 1; uup <= 6; uup++){if(conflict[op[up]][uup])continue;ans = (ans + f(uup, n -1)) % MOD;}return ans;
}int main()
{init();cin >> n >> m;for(int i = 0; i < m; i++){int a, b;cin >> a >> b;conflict[a][b] = true;conflict[b][a] = true;}long long int ans = 0;for(int up = 1; up <= 6; up++){ans = (ans + 4 * f(up, n -1)) % MOD;}cout << ans << endl;return 0;
}
使用第二种方法是动态规划.dp[i][j]表示有i层,限定朝上的数字为j的稳定方案数.
#include<iostream>
#include<map>
#include<cmath>
using namespace std;
long long dp[2][7];//dp[i][j]表示有i层,限定朝上的数字为j的稳定方案数
#define mod 1000000007
//int op[7];//记录对立面
bool conflict[7][7];//判断是否冲突
map<int, int>op;
int n, m;
void Init()
{op[1] = 4;op[2] = 5;op[3] = 6;op[4] = 1;op[5] = 2;op[6] = 3;
}
int main()
{Init();cin >> n >> m;int x, y;long long ants = 0;for (int i = 0; i < m; i++){cin >> x >> y;conflict[x][y] = true;conflict[y][x] = true;}//输入完成for (int j = 1; j <= 6; j++){dp[0][j] = 1;}int cur = 0;//迭代层数for (int level = 2; level <= n; level++){cur = 1 - cur;//尝试把6个面放在当前一层朝上的方向for (int j = 1; j <= 6; j++){dp[cur][j] = 0;//将与op[j]不冲突的上一层格子里面的数累加起来for (int i = 1; i <= 6; i++){if (conflict[op[j]][i])continue;//冲突的面朝上是不可取的dp[cur][j] = (dp[cur][j] + dp[1 - cur][i]) % mod;}}}long long sum = 0;for (int k = 1; k <= 6; k++){sum = (sum + dp[cur][k] )% mod;}//快速冥求4的次方long long ans = pow(4, n);cout << (sum * ans) % mod << endl;return 0;
}
6.生命之树
0生命之树 - 蓝桥云课 (lanqiao.cn)
题目解析:采用动态dp, dp[i][2]表示i结点选和不选情况下最大评分.
dp表的初始化,dp[i][1] = i 结点的权值.dp[i][0] = 0; 并且标记一下这个结点已经被使用过了.
dp[i][1] 分两个情况一个就是当前结点没有被使用过那么就是dp[i][1] = max(dp[i][0],dp[联通i结点][1]);
已经使用过,那么就是dp[i][1] = max(dp[i][1], 结点的权值); dp[i][0] = max(dp[i][0], 0);
#include <iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<cstring>
#define N 100000int n;
vector<int> node[N];//标记结点
int vis[N];//结点标记
int a, b;
int dp[N][2];//表示i结点选和不选的最大评分.
int v[N];//权值void init()
{memset(v, 0, sizeof(v));memset(dp, 0, sizeof(dp));cin >> n;for(int i = 1; i <= n; i++)//下标从1开始{cin >> v[i];}for(int i = 1; i < n; i++){cin >> a >> b;//结点连通node[a].push_back(b);node[b].push_back(a);}
}void dfs(int pos)
{//初始化.dp[pos][1] = v[pos];dp[pos][0] = 0;vis[pos] = 1;//结点连接数for(int i = 0; i < node[pos].size(); i++){if(!vis[node[pos][i]])//没被使用过{//递归相邻结点.dfs(node[pos][i]);dp[pos][1] += max(dp[node[pos][i]][0], dp[node[pos][i]][1]);}else{dp[pos][1] = max(dp[pos][1], v[pos]);dp[pos][0] = max(dp[pos][0], 0); }}
}int main()
{init();dfs(1);int ans = -1;//可能有负数for(int i = 1; i <= n; i++){ans = max(ans, dp[i][0]);ans = max(ans, dp[i][1]);}cout << ans << endl;return 0;
}
xdm给卑微的博主上上三联, 谢谢大家,一起进步学习!!!
这篇关于蓝桥杯第六届c++大学B组详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!