自学内容网 自学内容网

蓝桥杯第六届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 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)!