C++第13届蓝桥杯省b组习题笔记

1.九进制转十进制

九进制正整数 (2022)9转换成十进制等于多少？

第一位乘9的0次方，第二位乘9的1次方，第三位乘9的二次方以此类推

#include <iostream>
using namespace std;


int main()
{
  // 请在此输入您的代码
  int t=2022;
  int res=0;
  int cur=1;
  while(t)
  {
    // res*=10;
    res+=t%10*cur;
    t/=10;
    cur*=9;
  }

  cout<<res<<endl;
  return 0;
}

2. 顺子日期

小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456 等。顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123； 而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022 年份中，一共有多少个顺子日期?

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;

int month[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };


bool check(string s)
{
    for (int i = 0; i + 2 < s.size(); i++)
    {
        if (s[i] + 1 == s[i + 1] && s[i] + 2 == s[i + 2])
            return true;
    }
    return false;
}

int main()
{
    // 请在此输入您的代码
    int cnt = 0;
    for (int i = 20220000; i <= 20230000; i++)
    {
        int y = 2022;
        int m = i / 100 % 100;
        int d = i % 100;


        if (m <= 0 || m > 12)
            continue;
        int day = month[m];

        // if (m == 2)
        //     if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)
        //         day++;

        if (d <= 0 || d > day)
            continue;

        int k = i;

        string s;
        s = to_string(k);//将一串数字转化为string类型字符串。stoi将字符串转化为整数数字，stod转化为double类型

        if (check(s))
        {
            // for (auto c : s)
            //     cout << c << "  ";
            cnt++;
            // cout << endl;
        }
    }
    cout << cnt << endl;
    return 0;
}

3.刷题统计

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天 做 a 道题目, 周六和周日每天做 b 道题目。请你帮小明计算, 按照计划他将在 第几天实现做题数大于等于 n 题?

数据范围很大所以要先计算做题做了几个周，再枚举剩下的天数(开long long)

#include <iostream>
#include<cstdio>
using namespace std;
int main()
{
  // 请在此输入您的代码

  long long a,b,n;
  scanf("%lld%lld%lld",&a,&b,&n);
  long long cur=1;
  long long res=0;
  long long day=0;
  long long week=n/(5*a+2*b);
  n-=week*(5*a+2*b);
  while(res<n)
  {
    if(cur<=5)
    {
      res+=a;
      cur++;
    }
    else if(cur>5)
    {
      res+=b;
      if(cur==7)
      cur=1;
      else
      cur++;
    }
    day++;
  }

  cout<<day+week*7<<endl;
  return 0;
}

4. 修剪灌木

爱丽丝要完成一项修剪灌木的工作。

有 NN 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌 木, 让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始, 每天向右修剪一棵灌木。当修剪了最右侧的灌木后, 她会调转方向, 下一天开 始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。

灌木每天从早上到傍晩会长高 1 厘米, 而其余时间不会长高。在第一天的 早晨, 所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。

我直接暴力了。可以通过模拟来做

#include <iostream>
#include<cstdio>
using namespace std;

int n;
int h[10010];
int maxh[10010];

void add()
{
  for(int i=1;i<=n;i++)
  h[i]++;
}

void left()
{
    for(int i=1;i<=n;i++)
    {
      maxh[i]=max(maxh[i],h[i]);
      add();
      h[i]=0;//修剪为0
    }
}

void right()
{
    for(int i=n;i>=1;i--)
    {
      maxh[i]=max(maxh[i],h[i]);
      add();
      h[i]=0;//修剪为0
    }
}

int main()
{
  // 请在此输入您的代码
  scanf("%d",&n);

  int cur=1;

  int t=2;
  while(t--)
  {
    left();
    right();
  }

  for(int i=1;i<=n;i++)
  cout<<maxh[i]<<endl;

  return 0;
}

5.统计子矩阵

给定一个 N×M 的矩阵 A, 请你统计有多少个子矩阵 (最小 1×1 最大 N×M)满足子矩阵中所有数的和不超过给定的整数 K ?

解题思路

通过记录列的前缀和，然后枚举矩阵的上界和下界，通过双指针来枚举列

AC代码

#include <iostream>
#include<cstdio>
using namespace std;

int n,m,k;
int A[510][510];
int res[510][510];

int main()
{
  // 请在此输入您的代码
  scanf("%d%d%d",&n,&m,&k);
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=m;j++)
    {
      scanf("%d",&A[i][j]);
      res[i][j]=res[i-1][j]+A[i][j];//计算列的前缀和
    }
  }

  // for(int i=1;i<=n;i++)
  // {
  //   for(int j=1;j<=m;j++)
  //   {
  //     cout<<res[i][j]<<" ";
  //   }
  //   cout<<endl;
  // }
  long long cnt=0;
  for(int i=1;i<=n;i++)//枚举第几行
  {
    //枚举下界是第几行
     for(int j=i;j<=n;j++)//
     {
       int sum=0;
       for(int l=1,r=1;r<=m;r++)//枚举
       {
         sum+=res[j][r]-res[i-1][r];//去掉上界以上的列值

         while(sum>k)
         {
           sum-=res[j][l]-res[i-1][l];//不能重复去掉上界的值
            l++;//使矩阵和减少
         }
         cnt+=r-l+1;
       }
     }
  }
  
  cout<<cnt<<endl;
  return 0;
}

6.扫雷

C++：dfs习题四则_c++dfs题目-CSDN博客最后一个题

7. 李白打酒加强版

话说大诗人李白, 一生好饮。幸好他从不开车。

一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱:

无事街上走，提显去打酒。 逢店加一倍, 遇花喝一斗。

这一路上, 他一共遇到店 NN 次, 遇到花 MM 次。已知最后一次遇到的是花, 他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?

注意: 显里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。

解题思路

线性dp 

 AC代码+dfs代码

#include <iostream>
#include<cstdio>
using namespace std;
const long long mod=1000000007;
int n,m;

// long long cnt=0;
// void dfs(int fl,int hs,int sum)//花和店和剩余的酒
// {
//   //1. 还有花,没有酒那以后肯定不合法 2.花没了，还有店也不行。最后遇到的是花
//   if(sum==0&&fl>0||(fl==0&&hs>0))
//   {
//     return;
//   }
//   if(hs==0&&fl==0&&sum==0)//没有店了，没有花了,没有酒了
//   {
//     cnt++;
//     cnt%=mod;
//     return ;
//   }
//   //遇见店
//   if(hs>0)
//   dfs(fl,hs-1,sum*2);
//   //遇见花
//   if(fl>0)
//   dfs(fl-1,hs,sum-1);

//   return;
// }

int f[110][110][110];

int main()
{
  // 请在此输入您的代码
  scanf("%d%d",&n,&m);
  // dfs(m,n,2);
  f[0][0][2]=1;
  for(int i=0;i<=m;i++)//花
  {
      for(int j=0;j<=n;j++)
      {
          for(int k=0;k<=m;k++)//最多是m因为没有酒不能遇见花
          {
              int &v=f[i][j][k];
              if(j&&k%2==0)
              {
                v=(v+f[i][j-1][k/2])%mod;
              }
              if(i)
              v=(v+f[i-1][j][k+1])%mod;
          }
      }
  }
  cout<<f[m-1][n][1];//还剩一个花，一斗酒
    // cout<<cnt<<endl;
  return 0;
}

就到这里啦(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤