蓝桥杯第六届c++大学B组详解
前言：
看了很多博客以及视频讲解，感觉都不是很清楚，比较模棱两可，所以干脆自己一边想，一边写博客，也可帮助到其他人，都是根据自己的逻辑来尽量清楚简单的讲清楚题目，喜欢的不要吝啬三连，给博主点动力。
目录
1.奖券数目
3.三羊献瑞
4.移动距离
5.垒骰子
6.生命之树
1.奖券数目
题目解析：
就是判断每一位是否有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.星系炸弹
题目讲解：就是实现一个日期类；
#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.三羊献瑞
题目解析：这题本质就是模拟，根据题目意思依葫芦画瓢，然后进行全排列，得到最后答案。
题目说相同的汉字就是相同的数字，不相同反之。
如果使用到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.移动距离
题目解析：本质就是考数学题目，算出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.垒骰子
题目解析：根据题目意思，下图，我们可以创建一个数组来记录每面的对面是什么，
题目解析: 首先就要创建一个冲突数组将骰子的正面和对面的冲突记录,以及冲突面的数组.还有因为想象一下是一个魔方,那么四个面都可以进行翻转.所以还要乘以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.生命之树
题目解析:采用动态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 100000
int 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给卑微的博主上上三联, 谢谢大家,一起进步学习!!!
原文地址：https://blog.csdn.net/huajiahhhh/article/details/137087416
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！