2022蓝桥杯B组C++真题题解
目录
A： 九进制转十进制(填空)
本题总分：5分
问题描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
九进制正整数 (2022)9 转换成十进制等于多少？
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
送分题，每一位乘以9的位数减一次方；
#include <iostream>
using namespace std;
int main()
{
cout<<2*1+2*9+2*9*9*9;// 请在此输入您的代码
return 0;
}
B: 顺子日期（填空）
本题总分：5分
问题描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456 等。顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123； 而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022 年份中，一共有多少个顺子日期?
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
首先2022不是闰年，2月有28天；首先该数字共有八位，2022以2结尾，因此不可能出现20223xxx这种顺子日期，因此只考虑后四位即可；顺子日期要求三位连续（包括0），并且月份和日份不肯出现4以及更大的数字，因此只要考虑是否包含012和123这两种情况。
012：一共四位，012绑定在一起，那么只考虑首位和末尾可以添加的数即可；
首位添加：1012 一种
末尾添加：0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127, 0128, 0129 10种
123：同上
首位添加：0123， 1123 2种
末尾添加：1230， 1231 2种
这是所有的顺子日期 1+10+2+2=15，但注意要检查是否有重复的日期，发现标红的日期是重复的，因此有14种顺子日期；
#include <iostream>
using namespace std;
int main()
{
cout<<14;// 请在此输入您的代码
return 0;
}
C: 刷题统计
本题总分：10分
问题描述
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天 做 a 道题目, 周六和周日每天做 b道题目。请你帮小明计算, 按照计划他将在 第几天实现做题数大于等于 nn题?
输入格式
输入一行包含三个整数 a, ,b 和 n.
输出格式
输出一个整数代表天数。
样例输入
10 20 99
样例输出
8
评测用例规模与约定
对于 50% 的评测用例, 1 < a, b, n<
对于 100% 的评测用例, 1 <a, b, n<
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
注意改题目范围已经超出了int范围，因此要开long long，还有注意不要写for循环，否则会卡时间；一开始写for循环通过率在50左右，不能得满分；
#include <iostream>
using namespace std;
int main()
{
long long a,b,n;
cin>>a>>b>>n;
long long m=a*5+2*b; //一周做的题
long long t=n/m*7; //整周的天数
n=n%m; //剩下的题
if(n==0) t=t+0;
else if((n-a)<=0) t=t+1;
else if((n-2*a)<=0) t=t+2;
else if((n-3*a)<=0) t=t+3;
else if((n-4*a)<=0) t=t+4;
else if((n-5*a)<=0) t=t+5;
else if((n-5*a-b)<=0) t=t+6;
else t=t+7;
cout<<t;
return 0;
}
D: 修剪灌木
本题总分：10分
问题描述
爱丽丝要完成一项修剪灌木的工作。
有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌 木, 让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始, 每天向右修剪一棵灌木。当修剪了最右侧的灌木后, 她会调转方向, 下一天开 始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。
灌木每天从早上到傍晩会长高 1 厘米, 而其余时间不会长高。在第一天的 早晨, 所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。
输入格式
一个正整数 N, 含义如题面所述。
输出格式
输出 N 行, 每行一个整数, 第 i 行表示从左到右第 ii 棵树最高能长到多高。
样例输入
3
样例输出
4
2
4
评测用例规模与约定
对于 30% 的数据, N≤10.
对于 100% 的数据, 01<N≤10000.
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
这是一个找规律问题，来回一共减2n棵灌木，某一棵树的最高值是离开到再次减本棵树的差值，两边一个来回在本灌木剪两天，因此最边上的是2n-2，往里依次减二。1，输出0；2输出2,2；3输出4 2 4；以此类推。往中间以公差-2递减；
#include <iostream>
using namespace std;
int a[1005];
int main()
{
int n;
cin>>n;
for(int i=0;i<n/2;i++){ // n/2把标准卡得死死的
a[i]=a[n-i-1]=2*n-2-i*2;
}
if(n%2!=0){
a[n/2]=2*n-(n+1);
}
for(int i=0;i<n;i++){
if(i!=n-1){
cout<<a[i]<<endl;
}else{
cout<<a[i];
}
}
return 0;
} 
E: X 制减法
本题总分:15分
问题描述
进制规定了数字在数位上逢几进一。
X 进制是一种很神奇的进制, 因为其每一数位的进制并不固定！例如说某 种 XX 进制数, 最低数位为二进制, 第二数位为十进制, 第三数位为八进制, 则 XX 进制数 321 转换为十进制数为 65 。
现在有两个 XX 进制表示的整数 AA 和 BB, 但是其具体每一数位的进制还不确 定, 只知道 AA和 B 是同一进制规则, 且每一数位最高为 N 进制, 最低为二进 制。请你算出 A-B的结果最小可能是多少。
请注意, 你需要保证 A和B在X 进制下都是合法的, 即每一数位上的数 字要小于其进制。
输入格式
第一行一个正整数 N, 含义如题面所述。
第二行一个正整数 Ma, 表示 X 进制数 A 的位数。
第三行 Ma 个用空格分开的整数, 表示 X 进制数 A 按从高位到低位顺序各 个数位上的数字在十进制下的表示。
第四行一个正整数 Mb, 表示 X 进制数 B 的位数。
第五行 Mb 个用空格分开的整数, 表示 X 进制数 B 按从高位到低位顺序各 个数位上的数字在十进制下的表示。
请注意, 输入中的所有数字都是十进制的。
输出格式
输出一行一个整数, 表示 XX 进制数 A−B 的结果的最小可能值转换为十进 制后再模 1000000007 的结果。
样
样例输出
94
样例说明
当进制为: 最低位 2 进制, 第二数位 5 进制, 第三数位 11 进制时, 减法 得到的差最小。此时 A 在十进制下是 108, ,B 在十进制下是 14 , 差值是 94。
评测用例规模与约定
对于 30% 的数据, N<=10;Ma，Mb<=8;
对于100% 的数据, 2<=N<=1000,1≤Ma,Mb≤100000;A≥B.
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
某个大佬：321的“1”是2进制，逢2进1，即“2”就意味着数字4=2*2，“2”的进制是10进制，逢10进1，也就是说对于“2”来说，“3”代表着30，而对于“1”来说“3”则代表着60=30*2。通俗的说，假如321整个树是10进制，那么对于“2”而言“3”是30，对于“1”而言，“3”是300=3*10*10.
本题首先要看懂题目，最低位固定乘以一，次低位乘以ma和mb最低位最大值加一，次次低位在乘以最低位最大值加一外，再乘以次低位最大值加一，以此类推。最后相加减，注意不要爆，一
定一定要多取模；
#include <iostream>
#define M 1000000007
using namespace std;
long long sum;
long long max(long long x,long long y){
if(x>=y) return x;
else return y;
}
long long a[100005],b[100005],c[100005];
long long d[100005];
int main()
{
int n,ma,mb;
cin>>n;
cin>>ma;
for(int i=0;i<ma;i++){
cin>>a[i];
}
cin>>mb;
for(int i=ma-mb;i<ma;i++){ //ma-mb的原因是要a和b位数对齐
cin>>b[i];
}
for(int i=ma-1;i>=0;i--){
if(max(a[i],b[i])+1>=2){ //c用来记录差最小时，每位的进制数
c[i]=max(a[i],b[i])+1;
}else c[i]=2;
}
int x=0;
for(int i=ma-1;i>=0;i--){
if(i==ma-1) x=1;
else x=((x%M)*(c[i+1]%M)%M)%M;
sum+=((a[i]-b[i])%M*x%M)%M;
}
cout<<sum%M;
return 0;
}思路清晰，但是不知道为什么只通过80，难道是卡内存了？
然后我们换一种方法：
#include <iostream>
#include <cmath>
using namespace std;
long long M=1000000007;
long long a[100005],b[100005];
long long ans,x,sum=1;
long long n,ma,mb;
int main()
{
cin>>n;
cin>>ma;
for(int i=ma;i>=1;i--){
cin>>a[i];
}
cin>>mb;
for(int i=mb;i>=1;i--){ //左对齐，这种输入方法比上一种更简单
cin>>b[i];
}
for(int i=1;i<=ma;i++){
x=max(a[i],b[i])+1; //该位进制数
if(x<2) x=2;
ans=(ans+(a[i]-b[i])*sum)%M; //sum是截止到上一位的进制乘积
sum=(sum*x)%M;
}
cout<<ans%M;
return 0;
} 
少写了一个循环，用了cmach库的max函数，少开了几个数组，终于100了；
F: 统计子矩阵
本题总分：15
问题描述
给定一个N×M 的矩阵 A, 请你统计有多少个子矩阵 (最小 1×1, 最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K?
输入格式
第一行包含三个整数 N, M,和 K.
之后 N 行每行包含 M 个整数, 代表矩阵 A.
输出格式
一个整数代表答案。
样例输入
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
样例输出
19
样例说明
满足条件的子矩阵一共有 19 , 包含:
大小为 1×1 的有 10 个。
大小为 1×2 的有 3 个。
大小为 1×3 的有 2 个。
大小为 1×4 的有 1 个。
大小为 2×1 的有 3 个。
评测用例规模与约定
对于 30% 的数据, N,M≤20.
对于 70% 的数据, N,M≤100.
对于 100% 的数据, 1≤N,M≤500;0≤Aij≤1000;1≤K≤250000000.
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
本题为二维前缀和问题，首先纯暴力要6个for循环，肯定超时，用动态规划dp，将其二维矩阵和记录下来（以（1,1）为左上点的矩阵）。可以减少2个for循环，以空间换时间；
#include <iostream>
using namespace std;
int n,m,k;
int dp[505][505];
int zanshi,ans;
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>zanshi;
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+zanshi; //记录前二维矩阵和
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int x=i;x<=n;x++){
for(int y=j;y<=m;y++){
if(dp[x][y]-dp[x][j-1]-dp[i-1][y]+dp[i-1][j-1]<=k){ //求包括中间的矩阵和
ans++;
}
}
}
}
}
cout<<ans;
return 0;
} 
嗯，怎么说，四个for循环时间复杂度还是高了点。再怎么优化呢？你想如果一个小的矩阵大于k的话，那么包含该矩阵大矩阵一定大于k，还是有优化空间的，优化一下。
#include <iostream>
using namespace std;
int n,m,k;
int dp[505][505];
long long zanshi,ans; //ans要long long，
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>zanshi;
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+zanshi;
}
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
for(int l=1,r=1;r<=m;r++){
while(l<=r&&(dp[j][r]-dp[j][l-1]-dp[i-1][r]+dp[i-1][l-1]>k)){
l++;
}
if(r>=l){
ans+=r-l+1;
}
}
}
}
cout<<ans;
return 0;
}
终于100了，重点说一下以下代码，某个大佬写的，看了好久才看懂。
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
for(int l=1,r=1;r<=m;r++){
while(l<=r&&(dp[j][r]-dp[j][l-1]-dp[i-1][r]+dp[i-1][l-1]>k)){
l++;
}
if(r>=l){
ans+=r-l+1;
}
}
}
}首先前两层for循环，可以把i，j（横）看做两个木棍，初始化都是1，然后j向下运动，到达底端后，i下降到2，j返回到2，以此类推，最后i，j都到达n结束；再说第三层for循环。初始化l，r也是
看做两个木棍（竖），初始化都为1，也就是矩阵最左边。当r（右棍）>=l（左棍）时，判断四个木棍围成的矩阵是否符合小于k，大于k时左棍向右移动，矩阵变小。直到小于k，小于k时将可行方案加到总方案数种。
最最重要的是ans+=r-l+1；这行代码，我们只考虑列，因为行还在移动。如果r棍不动，那么l棍向r棍靠近，直到l=r。比如r=3，l=1，那么有三个单列矩阵，两个双列矩阵，一个三列矩阵，一共六个解。那么你可以算算，l第一次移动时ans=3，直到l=r，ans=6，刚刚好。但是当r向右移动时就比较复杂了，有两个大矩阵重合，此时ans的值应该等于两个大矩阵解的和减去中间重合矩阵（重合最大的矩阵），比如两个大矩阵边长分别是5和6，中间重合最大矩阵为3，此时ans解为5+4+3+2+1+6+5+4+3+2+1-3-2-1=6+5+4+3+2+1+5+4；你会发现正好是移动后矩阵解加上之前移动矩阵前加上的解。
G: 积木画
本题总分：15
问题描述
小明最近迷上了积木画, 有这么两种类型的积木, 分别为 II 型（大小为 2 个单位面积) 和 LL 型 (大小为 3 个单位面积):
同时, 小明有一块面积大小为 2×N 的画布, 画布由 2×N个 1×1 区域构 成。小明需要用以上两种积木将画布拼满, 他想知道总共有多少种不同的方式? 积木可以任意旋转, 且画布的方向固定。
输入格式
输入一个整数 NN，表示画布大小。
输出格式
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值。
样例输入
3
样例输出
5
样例说明
五种情况如下图所示，颜色只是为了标识不同的积木：
评测用例规模与约定
对于所有测试用例，1≤N≤10000000.
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 2s | 256M |
| C | 2s | 256M |
| Java | 5s | 256M |
| Python3 | 10s | 256M |
动态规划题目，难点在于寻找递推公式。
不过里面有个小错误，不知道大家发现没有
这个结论正确，不过过程有个错误，
应该还要考虑没有剩余时的特殊情况。
#define m 1000000007
int n;
long long dp[10000005];
int main()
{
cin>>n;
dp[0]=1;
dp[1]=1;
dp[2]=2;
dp[3]=5;
for(int i=4;i<=n;i++){
for(int j=0;j<=i-1;j++){
dp[i]+=2*dp[j];
if(j==i-1 || j==i-2){
dp[i]=dp[i]-dp[j];
}
}
}
cout<<(dp[n])%m;
return 0;
} 
答案正确，但是存在超时和爆调的问题，通过率为0，爆 栈后答案就不对了。
#include <iostream>
using namespace std;
#define m 1000000007
int n;
long long dp[10000005];
int main()
{
cin>>n;
dp[0]=1;
dp[1]=1;
dp[2]=2;
dp[3]=5;
for(int i=4;i<=n;i++){
dp[i]=(dp[i-3]%m+2*dp[i-1]%m)%m;
}
cout<<(dp[n])%m;
return 0;
}这个时间复杂度低，重要的是没有减法，可以任意取模，不存在爆栈问题；
H: 扫雷
本题总分：20
问题描述
小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下, 在一个二维平面上放置着 n 个炸雷, 第 i 个炸雷 (xi,yi,ri) 表示在坐标 (xi,yi) 处存在一个炸雷, 它的爆炸范围是以半径为 r的一个圆。
为了顺利通过这片土地, 需要玩家进行排雷。玩家可以发射 m 个排雷火 箭, 小明已经规划好了每个排雷火箭的发射方向, 第 j 个排雷火箭(xj,yj,rj) 表 示这个排雷火箭将会在 (xj,yj) 处爆炸, 它的爆炸范围是以半径为 r 的一个圆, 在其爆炸范围内的炸雷会被引爆。同时, 当炸雷被引爆时, 在其爆炸范围内的 炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷?
你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个 炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。
输入格式
输入的第一行包含两个整数 n 、m
接下来的 n行, 每行三个整数 xi,yi,ri, 表示一个炸雷的信息。
再接下来的 m 行, 每行三个整数 xj,yj,rj, 表示一个排雷火箭的信息。
输出格式
输出一个整数表示答案。
样例输入
2 1
2 2 4
4 4 2
0 0 5
样例输出
2
样例说明
示例图如下，排雷火箭 1 覆盖了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆盖了炸雷 2，所以炸雷 2 也被排除。
评测用例规模与约定
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M】
本题是我采用dfs算法，递归遍历。先遍历每一个火箭，然后搜寻每个炸弹，符合条件的炸弹进入dfs引爆；
#include <iostream>
#include <cmath>
using namespace std;
int n,m;
int ans;
struct zhadan{
int x,y;
int r;
zhadan(){}
zhadan(int xx,int yy,int rr){
x=xx;
y=yy;
r=rr;
}
};
float dd(zhadan a,zhadan b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
zhadan a[50005];
zhadan b[50005];
bool c[50005];
void dfs(zhadan v){
for(int i=0;i<n;i++){
if(dd(a[i],v)<=v.r && !c[i]){
c[i]=1;
ans++;
dfs(a[i]);
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i].x>>a[i].y>>a[i].r;
}
for(int i=0;i<m;i++){
cin>>b[i].x>>b[i].y>>b[i].r;
}
for(int i=0;i<m;i++){
dfs(b[i]);
}
cout<<ans;
return 0;
} 
40通过率，再优化一下，我发现炸弹个数很多，但是爆照范围很小，我们尝试遍历边长为2r的正方形，而不是炸弹个数。遍历整个图形用bfs更好。
#include <iostream>
#include <map>
#include <set>
#include <queue>
using namespace std;
const int N=50005;
int ans;
int n,m;
struct node
{
int x;
int y;
int r;
node(int xx,int yy,int rr)
{
x=xx;
y=yy;
r=rr;
}
};
int get_len(int x,int y,int i,int j)
{
return (x-i)*(x-i)+(y-j)*(y-j);
}
map<pair<int,int>,int> mp;
set<pair<int,int>> s;
queue<node> q;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
int x,y,r;
cin>>x>>y>>r;
int tmp=mp[{x,y}]+100;
mp[{x,y}]=max(tmp,tmp/100*100+r);
}
for(int i=0;i<m;i++)
{
int x,y,r;
cin>>x>>y>>r;
q.push(node(x,y,r));
}
int ans=0;
while(q.size())
{
int xx=q.front().x;
int yy=q.front().y;
int rr=q.front().r;
q.pop();
for(int i=xx-rr;i<=xx+rr;i++)
{
for(int j=yy-rr;j<=yy+rr;j++)
{
pair<int,int> p(i,j);
if(s.count(p))
{
continue;
}
if(!mp.count(p))
{
continue;
}
if(get_len(xx,yy,i,j)>rr*rr)
{
continue;
}
s.insert(p);
q.push(node(i,j,mp[p]%100));
ans=ans+mp[p]/100;
}
}
}
cout<<ans;
}
G: 李白打酒加强版
本题总分：25
问题描述
话说大诗人李白, 一生好饮。幸好他从不开车。
一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱:
无事街上走，提显去打酒。 逢店加一倍, 遇花喝一斗。
这一路上, 他一共遇到店 N 次, 遇到花 M 次。已知最后一次遇到的是花, 他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?
注意: 显里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。
输入格式
第一行包含两个整数 N 和 M.
输出格式
输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果.
样例输入
5 10
样例输出
14
样例说明
如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：
010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100
评测用例规模与约定
对于40% 的评测用例:101≤N,M≤10 。
对于 100% 的评测用例: 1≤N,M≤100 。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
我看到这个题第一时间想到dfs，每次有两种情况可选，一种是店一种是花。花多了或酒多了以及花不是最后一个进行
#include <iostream>
using namespace std;
long long mm=1000000007;
int n,m; //n店，m花
int ans;
void dfs(int jiu,int dian,int hua){
if(jiu==0 && dian==n && hua==m){
ans=(ans+1)%mm;
return;
}
if(hua==m && jiu) return; //没有花但是还有酒
if(hua==m && dian<n) return; //没有花，但是还有店（花不是最后一个）
if(jiu==0 && hua<m) return; //没有酒，但是还有花
if(hua<m) dfs(jiu-1,dian,hua+1);
if(dian<n) dfs(jiu*2,dian+1,hua);
}
int main()
{
cin>>n>>m;
dfs(2,0,0);
cout<<ans%mm;
return 0;
}
由于递归时间复杂度过高，只过了40，想优化只能向dp方向考虑了；
建立dp数组dp[i][j][k],i代表经过了几家店，j代表经过几朵花，k代表酒壶里的酒，那么我们开始进行递推，首先如果这次k是奇数那么，上一次一定是经过了花（遇到了店，k翻倍必定是偶数）。当k是偶数时，上一次可能是遇到店也可能遇到花于是：
当k%2==1&&j>0时：dp[i][j][k]+=dp[i][j-1][k+1]
当k%2==0&&i>0时：dp[i][j][k]+=dp[i][j-1][k+1]+dp[i-1][j][k/2]
include <iostream>
using namespace std;
#define mm 1000000007
int dp[105][105][105];
int n,m;
int main()
{
cin>>n>>m; //n是店，m是花
dp[0][0][2]=1; //dp[i][j][k] i代表店，j代表花，k代表酒
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=m;k++){
if(k%2==1 && j>0){
dp[i][j][k]+=dp[i][j-1][k+1]%mm;
}
if(k%2==0 && i>0){
dp[i][j][k]+=(dp[i][j-1][k+1]%mm+dp[i-1][j][k/2]%mm)%mm;
}
}
}
}
cout<<dp[n][m-1][1]%mm;
return 0;
} 
J: 砍竹子
本题总分25
问题描述
这天, 小明在砍竹子, 他面前有 n 棵竹子排成一排, 一开始第 ii 棵竹子的 高度为 h_{i}hi.
他觉得一棵一棵砍太慢了, 决定使用魔法来砍竹子。魔法可以对连续的一 段相同高度的竹子使用, 假设这一段竹子的高度为 H, 那么
用一次魔法可以 把这一段竹子的高度都变为
, 其中 ⌊x⌋ 表示对 xx 向下取整。小明想 知道他最少使用多少次魔法可 让所有的竹子的高度都变为 1 。
输入格式
第一行为一个正整数 n, 表示竹子的棵数。
第二行共 n 个空格分开的正整数 hi, 表示每棵竹子的高度。
输出格式
一个整数表示答案。
样例输入
6
2 1 4 2 6 7
样例输出
5
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 2s | 256M |
| C | 2s | 256M |
| Java | 3s | 256M |
| Python3 | 10s |
该题目需要用到优先队列，优先队列是一种排序队列，自动将按照大小排列，那么每次最高的都在队首，我们只需要从高往往低开始砍竹子，每次判断最高竹子有无相同高度且连续的竹子，有则一起砍掉插入优先队列中，无则自己砍掉插入队列中；
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
int n;
#define ll long long
long long t;
int nn;
int ans;
struct zhuzi{
long long h;
int b;
zhuzi(long long hh,int bb){
h=hh;
b=bb;
}
bool operator<(const zhuzi &rhs)const {
if(h==rhs.h){
return b>rhs.b;
}
else return h<rhs.h;
}
};
priority_queue<zhuzi> q;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>t;
q.push(zhuzi(t,i));
}
while(q.top().h!=1){
t=q.top().h;
n=q.top().b;
while(q.top().h==t&&q.top().b==n){
q.pop();
q.push(zhuzi(sqrt(t/2+1),n));
n++;
}
ans++;
}
cout<<ans;
return 0;
}
long long sqrt(long long x){
long long ans=0,l=1,r=1e9; //双指针，题目高度最大10的18次方，所以右指针最大10的9次方
while(l<=r){
long long mid=l+r>>1; //右移符号
if(mid*mid <= x){ //小于x证明，求的值在mid右边，左指针移动到mid-1
ans=mid;
l=mid+1;
}
else
r=mid-1;
}
return ans;
}过65，由于cmath库的sqrt函数原型是double，因此会很慢，我们要手写一个二分sqrt函数
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
int n;
long long t;
int nn;
int ans;
long long sqrt(long long x){
long long ans=0,l=1,r=1e9; //双指针，题目高度最大10的18次方，所以右指针最大10的9次方
while(l<=r){
long long mid=l+r>>1; //右移符号
if(mid*mid <= x){ //小于x证明，求的值在mid右边，左指针移动到mid-1
ans=mid;
l=mid+1;
}
else
r=mid-1;
}
return ans;
}
struct zhuzi{
long long h;
int b;
zhuzi(long long hh,int bb){
h=hh;
b=bb;
}
bool operator<(const zhuzi &rhs)const {
if(h==rhs.h){
return b>rhs.b;
}
else return h<rhs.h;
}
};
priority_queue<zhuzi> q;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>t;
q.push(zhuzi(t,i));
}
while(q.top().h!=1){
t=q.top().h;
n=q.top().b;
while(q.top().h==t&&q.top().b==n){
q.pop();
q.push(zhuzi(sqrt(t/2+1),n));
n++;
}
ans++;
}
cout<<ans;
return 0;
} 
- 点赞
- 收藏
- 关注作者
评论（0）