【第十四届蓝桥杯】第三期官方校内模拟赛B组C++题解(已修正完毕,均可AC100%)

简介: 文章目录写在前面一、字母数(AC100%)题目描述解题报告1、大体思路2、代码详解二、列名(AC100%)题目描述解题报告1、大体思路2、代码详解三、特殊日期(AC100%)题目描述解题报告1、大体思路2、代码详解四、大乘积(AC100%)题目描述解题报告1、大体思路2、代码详解==五、最大连通==(已修正)题目描述解题报告1、大体思路2、代码详解六、星期几(AC100%)题目描述解题报告1、大体思路2、代码详解七、信号覆盖(AC100%)题目描述解题报告1、大体思路2、代码详解八、清理水域(AC100%)题目描述解

写在前面

注:以下题解不一定正确,仅供参考。故只给出大体思路及代码,如有错误,还请大佬多多指正。

2023年3月14日:根据蓝桥官网的评测系统,对题目答案进行了评测,高亮标识的代表未AC100%,之后将给出AC代码。

2023年3月16日~2023年3月17日:参考蓝桥官方解析直播以及一些博主的题解分享对代码进行修改,并在蓝桥官网的评测系统中通过所有样例,感谢博主的分享,所有题目已经修改完成,均可AC100%。

一、字母数(AC100%)

题目描述

请找到一个大于 2022 的最小数,这个数转换成十六进制之后,所有的数位(不含前导 0)都为字母(A 到 F)。

请将这个数的十进制形式作为答案提交。


解题报告

1、大体思路

从2022开始向后枚举,每次都将枚举到的数转化为16进制,然后判断每位数字是否满足条件。


2、代码详解

#include <iostream>

using namespace std;

bool check(int x){

while(x){

 int r=x%16;

 if(r>=0&&r<=9){

  return false;

 }

 x/=16;

}

return true;

}

int main(){

   for(int i=2022;;i++){

    if(check(i)){

     cout<<i;

     break;

 }

}

return 0;

}



参考答案


2730

1

二、列名(AC100%)

题目描述

在 Excel 中,列的名称使用英文字母的组合。前 26 列用一个字母,依次为 A 到 Z,接下来 26*26 列使用两个字母的组合,依次为 AA 到 ZZ。

请问 第 2022 列的名称 是什么?


解题报告

1、大体思路

比赛时将这道题理解错了,以为是最多从A~ZZ,超过的从头再循环。

赛后参考其他大佬的题解发现是走到ZZ之后是每三位是一列:AAA、AAB、…,走完三位就是四位,依次排。错误代码就不写在下面了,下面代码为纠正思路后的代码。

将A~Z映射成1 ~26,也就是一个“26进制的数”,注意这个进制比较特殊,不是从0 ~25,而且是满27进1,这样就将该问题转换成了一个进制转化问题:十进制2022,对应该进制表示为多少。

补:

简单解法:通过Excel软件,在单元格中输入1,然后按住Ctrl往后拉到2022列即可。


2、代码详解

#include <iostream>

using namespace std;

int main(){

   int n;

   cin>>n;

   while(n){

    cout<<n%26<<' ';

    n/=26;

}

return 0;

}

参考答案

上述程序输出是 20 25 2

因为先输出的余数是低位,所以对应的答案应该是 2 25 20 所对应的字母

即BYT

1

2

3


三、特殊日期(AC100%)

题目描述

对于一个日期,我们可以计算出年份的各个数位上的数字之和,也可以分别计算月和日的各位数字之和。请问从 1900 年 1 月 1 日至 9999 年 12 月 31 日,总共有多少天,年份的数位数字之和等于月的数位数字之和加日的数位数字之和。例如,2022年11月13日满足要求,因为 2+0+2+2=(1+1)+(1+3) 。

请提交满足条件的日期的总数量。


解题报告

1、大体思路

暴力枚举,按题目要求进行判断,注意闰年条件(能被4整除不能被100整除或者能够被400整除的年份)。


2、代码详解

#include <iostream>

using namespace std;

int ans;

int pmonth[]={31,28,31,30,31,30,31,31,30,31,30,31};

int rmonth[]={31,29,31,30,31,30,31,31,30,31,30,31};

int ryear(int n){

if(n%100!=0&&n%4==0||n%400==0){

 return true;

}

return false;

}

int num_sum(int x){

int sum=0;

while(x){

 sum+=x%10;

 x/=10;

}

return sum;

}

int main(){

   for(int i=1900;i<=9999;i++){

    int target=num_sum(i);

    bool flag=false;

    if(ryear(i)) flag=true;

    for(int j=1;j<=12;j++){

     int sum=0;

     sum+=num_sum(j);

     if(flag){

     for(int w=1;w<=rmonth[j-1];w++){

        sum+=num_sum(w);

        if(sum==target){

         ans++;

     }

     sum-=num_sum(w);

  }

  }

  else{

   for(int w=1;w<=pmonth[j-1];w++){

        sum+=num_sum(w);

        if(sum==target){

         ans++;

     }

     sum-=num_sum(w);

  }

  }

   

 }

}

   cout<<ans;

return 0;

}



参考答案


70910

1

四、大乘积(AC100%)

题目描述

小蓝有 30 个数,分别为:99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77 。

小蓝可以在这些数中取出两个序号不同的数,共有 30*29/2=435 种取法。

请问这 435 种取法中,有多少种取法取出的两个数的乘积大于等于 2022 。


解题报告

1、大体思路

组合问题,选1号和2号、2号和1号是同一种选法,所以每次选第二个数都从第一个选到的数的后面选就可以避免重复。


2、代码详解

#include <iostream>

using namespace std;

int num[]={99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77};

int ans;

int main(){

   for(int i=0;i<30;i++){

    for(int j=i+1;j<30;j++){

     if(num[i]*num[j]>=2022) ans++;

 }

}

   cout<<ans;

return 0;

}

参考答案

189

1


五、最大连通(已修正)

题目描述

小蓝有一个 30 行 60 列的数字矩阵,矩阵中的每个数都是 0 或 1 。

如果从一个标为 1 的位置可以通过上下左右走到另一个标为 1 的位置,则称两个位置连通。与某一个标为 1 的位置连通的所有位置(包括自己)组成一个连通分块。

请问矩阵中 最大的连通分块有多大


110010000011111110101001001001101010111011011011101001111110

010000000001010001101100000010010110001111100010101100011110

001011101000100011111111111010000010010101010111001000010100

101100001101011101101011011001000110111111010000000110110000

010101100100010000111000100111100110001110111101010011001011

010011011010011110111101111001001001010111110001101000100011

101001011000110100001101011000000110110110100100110111101011

101111000000101000111001100010110000100110001001000101011001

001110111010001011110000001111100001010101001110011010101110

001010101000110001011111001010111111100110000011011111101010

011111100011001110100101001011110011000101011000100111001011

011010001101011110011011111010111110010100101000110111010110

001110000111100100101110001011101010001100010111110111011011

111100001000001100010110101100111001001111100100110000001101

001110010000000111011110000011000010101000111000000110101101

100100011101011111001101001010011111110010111101000010000111

110010100110101100001101111101010011000110101100000110001010

110101101100001110000100010001001010100010110100100001000011

100100000100001101010101001101000101101000000101111110001010

101101011010101000111110110000110100000010011111111100110010

101111000100000100011000010001011111001010010001010110001010

001010001110101010000100010011101001010101101101010111100101

001111110000101100010111111100000100101010000001011101100001

101011110010000010010110000100001010011111100011011000110010

011110010100011101100101111101000001011100001011010001110011

000101000101000010010010110111000010101111001101100110011100

100011100110011111000110011001111100001110110111001001000111

111011000110001000110111011001011110010010010110101000011111

011110011110110110011011001011010000100100101010110000010011

010011110011100101010101111010001001001111101111101110011101


解题报告

1、大体思路

>思路是深搜,但是本题比赛时调了很久,不确定答案是否正确,参考即可。

枚举每个位置,如果该位置是1就深搜查找,每次枚举它上下左右的数,直到到达的数上下左右都为0,记录答案并回溯,个人感觉这道题和后面第九题很像。

正确思路:利用Flood Fill算法,既可以深搜也可以宽搜,将走到的1标记(或者直接将该位置的值修改),统计出最大连通块中1的个数即可。


2、代码详解

正确思路


深搜实现

#include <iostream>

#include <algorithm>

using namespace std;

int dx[]={-1,1,0,0},dy[]={0,0,-1,1};  //方向数组存储四个方向坐标偏移量

char g[35][65];

int res=1;

int dfs(int x,int y){

   int cnt=1;

g[x][y]='0';      //每次将该位置的1标记为已搜过

for(int i=0;i<4;i++){

 int a=x+dx[i],b=y+dy[i];

 if(a>=0&&a<30&&b>=0&&b<60&&g[a][b]=='1'){    

  cnt+=dfs(a,b);             //深搜统计1的个数

 }

}

return cnt;

}

int main(){

   for(int i=0;i<30;i++){

    for(int j=0;j<60;j++){

  cin>>g[i][j];

 }

}

   for(int i=0;i<30;i++){

    for(int j=0;j<60;j++){

     if(g[i][j]=='1'){       //枚举每个1的位置,进行深搜,答案即为某个1深搜得到的1的总数的最大值

      res=max(dfs(i,j),res);

  }

 }

}

   cout<<res;

return 0;

}



宽搜实现

#include <iostream>

#include <algorithm>

#include <queue>

#include <utility>

using namespace std;

typedef pair<int,int> PII;

int dx[]={-1,1,0,0},dy[]={0,0,-1,1};  //方向数组存储四个方向坐标偏移量

char g[35][65];

int res=1;

queue<PII> q;

//返回从(x,y)开始拓展的最大连通块中1的个数

int bfs(int x,int y){

  q.push({x,y});

  int sum=0;                              

  while(!q.empty()){        

   PII t=q.front();     //每次将队头进行拓展

   q.pop();

   g[t.first][t.second]='0';      //首先将队头设置为已经被遍历过

   sum++;

   for(int i=0;i<4;i++){

   int a=t.first+dx[i],b=t.second+dy[i];

   if(a>=0&&a<30&&b>=0&&b<60&&g[a][b]=='1'){      //如果该点可以被拓展,则将其标记为已经被遍历过

    g[a][b]='0';

    q.push({a,b});                             //将该点入队

   }  

  }

  }

  return sum;

}

int main(){

  for(int i=0;i<30;i++){

   for(int j=0;j<60;j++){

    cin>>g[i][j];

   }

  }

  for(int i=0;i<30;i++){

   for(int j=0;j<60;j++){

    if(g[i][j]=='1'){       //枚举每个1的位置,进行深搜,答案即为某个1深搜得到的1的总数的最大值

     res=max(bfs(i,j),res);

    }

   }

  }

  cout<<res;

  return 0;

}



当时错误代码


#include <iostream>

#include <algorithm>

using namespace std;

int dx[]={-1,1,0,0},dy[]={0,0,-1,1};

char g[35][65];

bool st[35][65];

int sum=1;

int res=1;

int ans=1;

bool check(int x,int y){

for(int i=0;i<4;i++){

 int a=x+dx[i],b=y+dy[i];

 if(!(a>=0&&a<30&&b>=0&&b<60))  continue;

 if(a>=0&&a<30&&b>=0&&b<60&&g[a][b]=='1'&&!st[a][b]) return false;

}

return true;

}

void dfs(int x,int y){

if(check(x,y)){

 res=max(res,sum);

 return ;

}

for(int i=0;i<4;i++){

 int a=x+dx[i],b=y+dy[i];

 if(a>=0&&a<30&&b>=0&&b<60&&g[a][b]=='1'&&!st[a][b]){

  sum++;

  st[a][b]=true;

  dfs(a,b);

  st[a][b]=false;

  sum--;

 }

}

}

int main(){

   for(int i=0;i<30;i++){

    for(int j=0;j<60;j++){

  cin>>g[i][j];

 }

}

   for(int i=0;i<30;i++){

    for(int j=0;j<60;j++){

     res=1;

     if(g[i][j]=='1'){

      dfs(i,j);

      ans=max(ans,res);

  }

 }

}

   cout<<ans;

return 0;

}


参考答案


148

1

六、星期几(AC100%)

题目描述

问题描述


给定一天是一周中的哪天,请问 n 天后是一周中的哪天?


输入格式


输入第一行包含一个整数 w,表示给定的天是一周中的哪天,w 为 1 到 6 分别表示周一到周六,w 为 7 表示周日。


第二行包含一个整数 n。


输出格式


输出一行包含一个整数,表示 n 天后是一周中的哪天,1 到 6 分别表示周一到周六,7 表示周日。


样例输入


6

10

1

2


样例输出

2

1


评测用例规模与约定

对于所有评测用例,1 <= n <= 1000000。


解题报告

1、大体思路

如果当前是周w,算上该周天数则就相当于总共过了n+w天,问现在是周几,所以直接取模7即可,注意结果为0需要特判一下,结果为0应该输出7。


2、代码详解

#include <iostream>

using namespace std;

int w;

int n;

int main(){

   cin>>w>>n;

   int ans=(n+w)%7;

if(!ans) cout<<7;

else cout<<ans;

return 0;

}


七、信号覆盖(AC100%)

题目描述

问题描述


小蓝负责一块区域的信号塔安装,整块区域是一个长方形区域,建立坐标轴后,西南角坐标为 (0,

0), 东南角坐标为 (W, 0), 西北角坐标为 (0, H), 东北角坐标为 (W, H)。其中 W, H 都是整数。

他在 n 个位置设置了信号塔,每个信号塔可以覆盖以自己为圆心,半径为 R 的圆形(包括边缘)。

为了对信号覆盖的情况进行检查,小蓝打算在区域内的所有横纵坐标为整数的点进行测试,检查信号状态。

其中横坐标范围为 0 到 W,纵坐标范围为 0 到 H,总共测试 (W+1) * (H+1) 个点。

给定信号塔的位置,请问 这 (W+1)*(H+1) 个点中有多少个点被信号覆盖。


输入格式

输入第一行包含四个整数 W, H, n, R,相邻整数之间使用一个空格分隔。

接下来 n 行,每行包含两个整数 x, y,表示一个信号塔的坐标。信号塔可能重合,表示两个信号发射器装在了同一个位置。


输出格式

输出一行包含一个整数,表示答案。


评测用例规模与约定

对于所有评测用例,1 <= n <= 100,每个单词的长度不超过 100。


样例输入

10 10 2 5

0 0

7 0


样例输出

57

1


解题报告

1、大体思路

模拟,利用两点间距离公式,距离小于等于半径满足题意,将该位置标记即可,统计标记位置的个数。


2、代码详解

#include <iostream>

#include <cmath>

using namespace std;

const int N=110;

bool g[N][N];

int W,H,n,R;

int ans;

int main(){

   cin>>W>>H>>n>>R;

   while(n--){

    int x,y;

    cin>>x>>y;

    for(int i=0;i<=W;i++){

     for(int j=0;j<=H;j++){

      if(abs(x-i)*abs(x-i)+abs(y-j)*abs(y-j)<=R*R) g[i][j]=true;

  }

 }

}

   for(int i=0;i<=W;i++){

    for(int j=0;j<=H;j++){

     if(g[i][j]) ans++;

 }

}

   cout<<ans;

return 0;

}


八、清理水域(AC100%)

题目描述

问题描述


小蓝有一个 n * m 大小的矩形水域,小蓝将这个水域划分为 n 行 m 列,行数从 1 到 n 标号,列数从 1 到 m 标号。每行和每列的宽度都是单位 1 。

现在,这个水域长满了水草,小蓝要清理水草。

每次,小蓝可以清理一块矩形的区域,从第 r1 行(含)到第 r2 行(含)的第 c1 列(含)到 c2 列(含)。

经过一段时间清理后,请问 还有多少地方没有被清理过。


输入格式

输入第一行包含两个整数 n, m,用一个空格分隔。

第二行包含一个整数 t ,表示清理的次数。

接下来 t 行,每行四个整数 r1, c1, r2, c2,相邻整数之间用一个空格分隔,表示一次清理。请注意输入的顺序。


输出格式

输出一行包含一个整数,表示没有被清理过的面积。

评测用例规模与约定

对于所有评测用例,1 <= r1 <= r2 <= n <= 100, 1 <= c1 <= c2 <= m <= 100, 0 <= t <= 100。


样例输入

2 3

2

1 1 1 3

1 2 2 2


样例输出

2

1


样例输入

30 20

2

5 5 10 15

6 7 15 9


样例输出

519

1


解题报告

1、大体思路

乍一看像二维差分,但看了下数据范围,好像可以暴力过,直接暴力模拟了。


2、代码详解

#include <iostream>

using namespace std;

const int N=110;

bool g[N][N];

int n,m;

int ans;

int main(){

   cin>>n>>m;

   int t;

   cin>>t;

   while(t--){

    int r1,c1,r2,c2;

    cin>>r1>>c1>>r2>>c2;

    for(int i=r1;i<=r2;i++){

     for(int j=c1;j<=c2;j++){

      g[i][j]=true;

  }

 }

}

   for(int i=1;i<=n;i++){

    for(int j=1;j<=m;j++){

     if(!g[i][j]) ans++;

 }

}

   cout<<ans;

return 0;

}


九、滑行(已修正)

题目描述

问题描述


小蓝准备在一个空旷的场地里面滑行,这个场地的高度不一,小蓝用一个 n 行 m 列的矩阵来表示场地,矩阵中的数值表示场地的高度。

如果小蓝在某个位置,而他上、下、左、右中有一个位置的高度 (严格)低于当前的高度,小蓝就可以滑过去,滑动距离为 1 。

如果小蓝在某个位置,而他上、下、左、右中所有位置的高度都大于等于当前的高度,小蓝的滑行就结束了。

小蓝不能滑出矩阵所表示的场地。

小蓝可以任意选择一个位置开始滑行,请问 小蓝最多能滑行多远距离。


输入格式

输入第一行包含两个整数 n, m,用一个空格分隔。

接下来 n 行,每行包含 m 个整数,相邻整数之间用一个空格分隔,依次表示每个位置的高度。


输出格式

输出一行包含一个整数,表示答案。

评测用例规模与约定

对于 30% 评测用例,1 <= n <= 20,1 <= m <= 20,0 <= 高度 <= 100。

对于所有评测用例,1 <= n <= 100,1 <= m <= 100,0 <= 高度 <= 10000。


解题报告

1、大体思路

个人感觉和第五题很类似,思路是深搜,枚举每个点,然后如果满足条件就继续深搜,到达某一个点时不满足条件了,就收获答案并回溯。

不确定是否正确,样例可以过。

正确思路:本题直接dfs会超时,所以需要dfs+记忆化搜索。也相当于是dp,只不过每次计算状态的时候是用深搜来计算的。

(1)f[i][j]表示从(i,j)开始滑,可以滑行的最大距离。

(2)f[i][j]可以滑向它上下左右的四个方向,所以有四种状态,假设第一步滑行到了(x,y),每种状态都可以先将第一步的滑行去掉,然后就转化成了求从(x,y)开始滑行,可以滑行的最大距离,根据定义可知,这个就是f[x][y]的定义,所以,我们可以得到转移方程:f[i][j]=max(f[i][j],f[x][y]+1)。而由于每个状态,我们需要深搜求得,所以本题就在转移过程中又利用了深搜。

本题与AcWing官网901. 滑雪十分相似,感兴趣的同学可以去看一下,还有y总的精彩讲解。


2、代码详解

正确思路

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

const int N=110;

int dx[]={1,-1,0,0},dy[]={0,0,1,-1};   //方向数组,记录四个方向的偏移量

int g[N][N];

int f[N][N];

int n,m;  

//dfs(x,y)返回从(x,y)开始滑行,可以滑行的最大距离

int dfs(int x,int y){

   if(f[x][y]!=-1) return f[x][y];     //如果该状态已经被计算过则直接返回

   f[x][y]=1;        //当前状态最少是1(当前位置)

   //枚举上下左右四个方向

for(int i=0;i<4;i++){

    int a=x+dx[i],b=y+dy[i];

    //如果该方向在范围内且可以滑过去

    if(a>=1&&a<=n&&b>=1&&b<=m&&g[a][b]<g[x][y])

       f[x][y]=max(f[x][y],dfs(a,b)+1);   //转移方程

}

return f[x][y];

}

int main(){

   cin>>n>>m;

   for(int i=1;i<=n;i++){

    for(int j=1;j<=m;j++){

     cin>>g[i][j];

 }

}

int ans=1;

memset(f,-1,sizeof f);      //初始化每个状态都为-1,表示为都没有计算过

//枚举每个点,从每个点开始滑行,求出最大滑行距离,最后再取一个最大值,即为答案

for(int i=1;i<=n;i++){

 for(int j=1;j<=m;j++){

  ans=max(ans,dfs(i,j));

 }

}

cout<<ans;

return 0;

}


AC30%

#include <iostream>

#include <algorithm>

using namespace std;

const int N=110;

int dx[]={1,-1,0,0},dy[]={0,0,1,-1};

int g[N][N];

bool st[N][N];

int n,m;  

int sum=1;

int ans=1;

int res=1;

bool check(int x,int y){

for(int i=0;i<4;i++){

 int a=x+dx[i],b=y+dy[i];

 if(!(a>=0&&a<n&&b>=0&&b<m)) continue;

  if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]<g[x][y]&&!st[a][b]) return false;

}

return true;

}

void dfs(int x,int y){

if(check(x,y)){

 res=max(res,sum);

 return ;

}

for(int i=0;i<4;i++){

 int a=x+dx[i],b=y+dy[i];

 if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]<g[x][y]&&!st[a][b]){

  sum++;

  st[a][b]=true;

  dfs(a,b);

  st[a][b]=false;

  sum--;

 }

}

}

int main(){

   cin>>n>>m;

   for(int i=0;i<n;i++){

    for(int j=0;j<m;j++){

     cin>>g[i][j];

 }

}

   for(int i=0;i<n;i++){

    for(int j=0;j<m;j++){

     res=1;

     dfs(i,j);

     ans=max(ans,res);

 }

}

cout<<ans;

return 0;

}


十、附近最小(已修正)

题目描述

问题描述

小蓝有一个序列 a[1], a[2], …, a[n]。

给定一个正整数 k,请问对于每一个 1 到 n 之间的序号 i,a[i-k], a[i-k+1], …, a[i+k] 这 2k+1 个数中的 最小值 是多少?当某个下标超过 1 到 n 的范围时,数不存在,求最小值时只取存在的那些值。


输入格式

输入的第一行包含一整数 n。

第二行包含 n 个整数,分别表示 a[1], a[2], …, a[n]。

第三行包含一个整数 k 。


输出格式

输出一行,包含 n 个整数,分别表示对于每个序号求得的最小值。

评测用例规模与约定

对于 30% 的评测用例,1 <= n <= 1000,1 <= a[i] <= 1000。

对于 50% 的评测用例,1 <= n <= 10000,1 <= a[i] <= 10000。

对于所有评测用例,1 <= n <= 1000000,1 <= a[i] <=1000000。


解题报告

1、大体思路

每次将这2k+1个数的最大值记录下来,然后输出。

数据应该最多过一半,比赛时没有想到优化方法,果断结束了,赛后了解到好像需要使用线段树,没有学过。

正确思路:可以用线段树和st表,但可惜都没学过,所以利用单调队列进行了优化。

思路参考博客:感谢博主的分享

该题可以利用两个单调队列来分别求出每个数左边k个数(包含自己)的最小值,再求出每个数右边k个数(包含自己)的最小值,两者取一个min即为区间[i-k,i+k]的最小值。


2、代码详解

正确思路

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=1000010;

int a[N],ans1[N],ans2[N];    //ans1[]存储每个元素前k个(包含自己)元素中的最小值,ans2[]存储每个元素后k个元素(包含自己)元素中的最小值

int q1[N],q2[N];

int n,k;

int main(){

   cin>>n;

   for(int i=1;i<=n;i++) cin>>a[i];

cin>>k;

int hh=0,tt=-1;

//窗口从前往后滑动,每次窗口中的最小值代表的是窗口中末元素前k个(包含自己)的最小值

for(int i=1;i<=n;i++){

 while(hh<=tt&&q1[hh]<i-k) hh++;

 while(hh<=tt&&a[q1[tt]]>=a[i]) tt--;

 q1[++tt]=i;

 ans1[i]=a[q1[hh]];

}

hh=0,tt=-1;

reverse(a+1,a+n+1);     //我们为了方便可以复用上面的代码,将数组反转

//窗口也是从前往后滑动,因为已将数组反转,所以每次窗口中的最小值代表的是窗口中末元素前k个(包含自己)的最小值 ,也就是原序列中该元素后k个(包含自己)的最小值

for(int i=1;i<=n;i++){

 while(hh<=tt&&q2[hh]<i-k) hh++;

 while(hh<=tt&&a[q2[tt]]>=a[i]) tt--;

 q2[++tt]=i;

 ans2[n-i+1]=a[q2[hh]];

}

for(int i=1;i<=n;i++) cout<<min(ans1[i],ans2[i])<<' ';    //该元素前k个元素和后k个元素(包含自己)中的最小值,即[i-k,i+k]中的最小值

return 0;

}


AC80%

#include <iostream>

#include <algorithm>

using namespace std;

const int N=1000010;

int a[N];

int n;

int k;

int main(){

   cin>>n;

   for(int i=1;i<=n;i++){

    cin>>a[i];

}

cin>>k;

for(int i=1;i<=n;i++){

    int ans=0x3f3f3f3f;

 int l,r;

 l=max(1,i-k);

 r=min(n,i+k);

 for(int j=l;j<=r;j++){

  ans=min(ans,a[j]);

 }

 cout<<ans<<' ';

}

return 0;

}


目录
相关文章
|
1月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
1月前
|
人工智能 算法 BI
第十四届蓝桥杯省赛大学C组(C/C++)三国游戏
第十四届蓝桥杯省赛大学C组(C/C++)三国游戏
|
1月前
|
人工智能 C++
第十四届蓝桥杯省赛大学B组(C/C++)整数删除
第十四届蓝桥杯省赛大学B组(C/C++)整数删除
|
1月前
|
机器学习/深度学习 算法 关系型数据库
第十五届蓝桥杯C++B组省赛
第十五届蓝桥杯C++B组省赛
66 14
|
1月前
|
算法 C++
2022年第十三届蓝桥杯大赛C/C++语言B组省赛题解
2022年第十三届蓝桥杯大赛C/C++语言B组省赛题解
34 5
|
6月前
|
算法 测试技术 C++
小唐开始刷蓝桥(八)2013年第四届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(八)2013年第四届C/C++ B组蓝桥杯省赛真题
|
6月前
|
算法 C++ 数据格式
小唐开始刷蓝桥(七)2014年第五届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(七)2014年第五届C/C++ B组蓝桥杯省赛真题
|
6月前
|
算法 C++
小唐开始刷蓝桥(五)2016年第七届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(五)2016年第七届C/C++ B组蓝桥杯省赛真题
|
6月前
|
算法 C++
小唐开始刷蓝桥(六)2015年第六届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(六)2015年第六届C/C++ B组蓝桥杯省赛真题
|
6月前
|
数据安全/隐私保护 C++
小唐开始刷蓝桥(九)2012年第三届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(九)2012年第三届C/C++ B组蓝桥杯省赛真题