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;elsecur++;}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ᵒᵛᵉᵧₒᵤ❤