蓝桥杯刷题冲刺 | 倒计时14天

article/2024/5/23 3:57:13

作者:指针不指南吗
专栏:蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了,最后的这几天尤为重要,不可懈怠哦🐾

文章目录

  • 1.最长递增
  • 2.走迷宫
  • 3.解立方根
  • 4.回文特判
  • 5.修改数组

1.最长递增

  • 题目

    链接: 最长递增 - 蓝桥云课 (lanqiao.cn)

    在数列 a1,a2,⋯,a n 中,如果 ai*<*ai*+1<a**i+2<⋯<a**j,则称 a* ia j 为一段递增序列,长度为 ji+1。

    定一个数列,请问数列中最长的递增序列有多长。

    输入描述

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

    第二行包含 n 个整数 a*1,a2,⋯,*a n,相邻的整数间用空格分隔,表示给定的数列。

    其中, 2≤n≤1000,0≤数列中的数≤10410^4104

    输出描述:

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

    输入输出样例

    输入

    7
    5 2 4 1 3 7 2
    

    输出

    3
    
  • 第一次 AC 100%

    #include<bits/stdc++.h>
    using namespace std;const int N=1010;int n,ans;
    int a[N];int main()
    {scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(a[j]>=a[j+1]){ans=max(ans,j-i+1);i=j+1;}}}cout<<ans;return 0;
    }
    

    生活不易,我的生活里还是有光的hhh

  • 反思

    这道题用的是 双指针

    i 表示 一个递增序列第一个数的下标;j 表示 一个递增序列后面的数的下标,

    j 不断地往下走,如果下一个数不大于现在的数,做出更新:

    ans 取 max,递增数组的第一个数的下标做出改变,更新为 j+1,即j+1是下一个递增序列的第一个数的下标,暴力枚举到最后

    • 动手在纸上模拟,思路就会很清晰,千万别硬想

2.走迷宫

  • 题目

    链接: 走迷宫 - 蓝桥云课 (lanqiao.cn)

    给定一个 N×M 的网格迷宫 G*。G* 的每个格子要么是道路,要么是障碍物(道路用 1 表示,障碍物用 0 表示)。

    已知迷宫的入口位置为 (x1,y1),出口位置为 (x2,y2)。问从入口走到出口,最少要走多少个格子。

    输入描述

    输入第 1 行包含两个正整数 N,M,分别表示迷宫的大小。

    接下来输入一个 N×M 的矩阵。若 G i,j=1 表示其为道路,否则表示其为障碍物。

    最后一行输入四个整数 x1,y1,x2,y2,表示入口的位置和出口的位置。

    1≤N,M≤100。

    输出描述

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

    若无法从入口到出口,则输出 −1。

    输入输出样例

    示例 1

    输入

    5 5 
    1 0 1 1 0
    1 1 0 1 1 
    0 1 0 1 1
    1 1 1 1 1
    1 0 0 0 1
    1 1 5 5 
    

    输出

    8
    
  • 第一次 AC 72%

    #include<bits/stdc++.h>
    using namespace std;typedef pair<int,int> PII;const int N=110;int n,m;
    int x1,y1,x2,y2;int g[N][N]; 
    int d[N][N];
    int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};void bfs()
    {memset(d,-1,sizeof d);d[x1][y1]=0;queue<PII> q;q.push({x1,y1});while(q.size()){auto t=q.front();q.pop();for(int i=0;i<4;i++){int x=t.first+dx[i],y=t.second+dy[i];if(d[x][y]==-1&&x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]==1){q.push({x,y});d[x][y]=d[t.first][t.second]+1;if(x==x2&&y==y2){cout<<d[x][y];return ;}}}}}int main()
    {cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>g[i][j];cin>>x1>>y1>>x2>>y2;	bfs();return 0;
    }
    
  • 第二次 AC 100%

    #include<bits/stdc++.h>
    using namespace std;typedef pair<int,int> PII;const int N=110;int n,m;
    int x1,y1,x2,y2;int g[N][N]; 
    int d[N][N];
    int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};int bfs()
    {memset(d,-1,sizeof d);d[x1][y1]=0;queue<PII> q;q.push({x1,y1});while(q.size()){auto t=q.front();q.pop();for(int i=0;i<4;i++){int x=t.first+dx[i],y=t.second+dy[i];if(d[x][y]==-1&&x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]==1){q.push({x,y});d[x][y]=d[t.first][t.second]+1;if(x==x2&&y==y2){return d[x][y];}}}}return -1;
    }int main()
    {cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>g[i][j];cin>>x1>>y1>>x2>>y2;	cout<<bfs();return 0;
    }
    
  • 反思

    标准的模板题,眼高手低,第一次,没有仔细阅读输出提示,-1 的情况

3.解立方根

  • 题目

    链接: 解立方根 - 蓝桥云课 (lanqiao.cn)

    给定一个正整数 N,请你求 N 的立方根是多少。

    输入描述

    第 1 行为一个整数 T,表示测试数据数量。

    接下来的 T 行每行包含一个正整数 N

    1≤T10510^5105,0≤N10510^5105

    输出描述

    输出共 T 行,分别表示每个测试数据的答案(答案保留 3 位小数)。

    输入输出样例

    输入

    3
    0
    1
    8
    

    输出

    0.000
    1.000
    2.000
    
  • 第一次 AC 100%

    #include<bits/stdc++.h>
    using namespace std;#define eps 1e-5int main()
    {int n;scanf("%d",&n);while(n--){int t;scanf("%d",&t);double x=t; double l=0,r=x;while(r-l>eps){double mid=(l+r)/2;if(mid*mid*mid<x) l=mid;else r=mid;} printf("%.3f\n",r); }return 0;
    }
    
  • 反思

    刚看到这道题是先把原来记的笔记看了一遍才能 AC 的,大家可以移步于这里来看->

    做各种题型的真题,把所有知识点都全部重新复习一遍

    二分

    • 重要的就是把三个板子记住,以及浮点数板子
    • 在浮点数精度问题上,和在某范围内查找某个数的时候特别是大范围就使用二分算法

4.回文特判

  • 题目

    链接: 回文判定 - 蓝桥云课 (lanqiao.cn)

    给定一个长度为 n 的字符串 S。请你判断字符串 S 是否回文。

    输入描述

    输入仅 1 行包含一个字符串 S

    1≤∣S∣≤10610^6106,保证 S 只包含大小写、字母。

    输出描述

    若字符串 S 为回文串,则输出 Y,否则输出 N

    输入输出样例

    示例 1

    输入

    abcba
    

    输出

    Y
    

    示例 2

    输入

    abcbb
    

    输出

    N
    
  • 第一次 AC 100%

    #include<bits/stdc++.h>
    using namespace std;int main()
    {string a;cin>>a;	string t=a;reverse(t.begin(),t.end());string b=t;if(a==b)puts("Y");else puts("N");return 0;
    }
    
  • 补充知识——reverse 函数

    1. reverse是C++下的库函数,可用于翻转字符串,翻转链表等

    2. 使用需要添加头文件

      #include <algorithm>

    3. reverse()会将区间[beg,end)内的元素全部逆序;
      其中区间翻转

      1.reverse(str.begin(),str.end()) 反转字符串2.reverse(vector.begin(),vector.end()) 反转向量3.reverse(a,a+strlen(a)) 反转数组
      
    4. 该函数无返回值

    5. 错误使用

      int main()
      {int a[99];for(int i = 0; i < 10; i++){cin >> a[i];}a.reverse();//错误,所有的类型结构,都是不可以的!for(int i = 0; i < 10; i++){cout << a[i];}
      }
      
  • 反思

    reverse 函数

    无返回值,使用临时变量,不免a原始值发生改变

    注意拼写和使用方法,不要a.reverse()

5.修改数组

  • 题目

    链接: 修改数组 - 蓝桥云课 (lanqiao.cn)

    给定一个长度为 N 的数组 A*=[A1,A2,⋅⋅⋅,AN*],数组中有可能有重复出现的整数。

    现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2,A3,⋅⋅⋅,A N

    当修改A i 时,小明会检查 A i 是否在 A1 ∼ A i−1 中出现过。如果出现过,则小明会给 A i 加上 1 ;如果新的 A i 仍在之前出现过,小明会持续给 A i 加 1 ,直 到 A i 没有在 A1 ∼A i−1 中出现过。

    A N 也经过上述修改之后,显然 A 数组中就没有重复的整数了。

    现在给定初始的 A 数组,请你计算出最终的 A 数组。

    输入描述

    第一行包含一个整数 N

    第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN

    其中,1≤N10510^5105,1≤A i10610^6106

    输出描述

    输出 N 个整数,依次是最终的 A*1,A2,⋅⋅⋅,*AN。

    输入输出样例

    示例

    输入

    5
    2 1 1 3 4
    

    输出

    2 1 3 4 5
    
  • 第一次 AC 0%

    #include<bits/stdc++.h>
    using namespace std;const int N=1e5+10;int n;
    int a[N];
    int p[N];int main()
    {	scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]); p[a[0]]=a[0];for(int i=1;i<n;i++){if(p[a[i]]==p[a[0]]) //说明重复{do{a[i]++;}while(p[a[i]]==p[a[0]]); //加完之后的元素还是重复就继续,否则跳出来 p[a[i]]=p[a[0]];}}for(int i=0;i<n;i++)printf("%d ",a[i]); return 0;} 
    

    没有对 p 初始化;

    当元素不同的时候,没有把该元素放进去集合里面,所以集合里面只有以a[0]及和a[0]重复之后,操作加进去的数

  • 第二次 AC 80% + 超时 20%

    思路

    1. 遍历整个数组,判断每个元素是否和前面重复

    2. 不重复:直接放进集合里面

      重复:元素+1,直到与集合里面的元素不重复,然后放进集合里面去

    #include<bits/stdc++.h>
    using namespace std;const int N=1e5+10;int n;
    int a[N];
    int p[N];int main()
    {memset(p,-1,sizeof p);  //初始化数组,在后面判断是否重复的时候使用scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]); p[a[0]]=a[0];  //以起始元素为 祖宗for(int i=1;i<n;i++)  //遍历整个数组{if(p[a[i]]==p[a[0]]) //说明重复{do{a[i]++; //元素自身+1}while(p[a[i]]==p[a[0]]); //加完之后的元素还是重复就继续,否则跳出来 p[a[i]]=p[a[0]]; //把操作完的元素放进去}elsep[a[i]]=p[a[0]];  //和前面不重复的元素,也是需要放到集合里面去的}for(int i=0;i<n;i++)printf("%d ",a[i]); return 0;} 
    
  • 题解

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>using namespace std;const int N = 1100010;int n;
    int a[N];int find(int x)                                 // 寻找父节点 + 路径压缩
    {if(a[x] != x) a[x] = find(a[x]);            // 如果不指向父节点return a[x];
    }int main()
    {for (int i = 1; i <= N; i ++) a[i] = i;     // 初始化,自己是自己的父节点cin >> n;for (int i = 1; i <= n; i ++){int x;scanf("%d", &x);x = find(x);                            // 找到 x 指向的父节点printf("%d ", x);a[x] = x + 1;                           // 将 x 的父节点更新为 x+1}return 0;
    }
    
  • 补充知识——并查集使用场景

    1. 两个元素是否在同一个集合里面出现过;
    2. 合并两个集合
  • 反思

    已经比较满意了,AC 80%

    这个题,我开始的思路,是比较混乱的,没有理清楚关系,考虑全面

    第二次之后,我觉得重复元素不断+1,是可以优化的,

    取前面所有元素的最大值,然后让重复元素max+1,AW,T_T

    这个题解:

    • 更新父节点真是妙,每一个对应的父节点+1,正好修正我用 max

Alt


http://www.ngui.cc/article/show-1007574.html

相关文章

pip安装及国内源更换

# pip安装 python3&#xff1a; curl https://bootstrap.pypa.io/get-pip.py -o get-pip.py python3 get-pip.py python2: curl https://bootstrap.pypa.io/pip/2.7/get-pip.py -o get-pip2.py python2 get-pip2.py # pip国内的一些镜像 阿里云 http://mirrors.aliyu…

vue2 和vue3动态绑定src

vue2&#xff1a; webpack 创建的vue2可以通过 require对图片进行动态绑定 <script> export default{data(){return{list:[{id:1,img:require("./assets/logo.png")},{id:2,img:require("./assets/logo.png")},{id:3,img:require("./assets/l…

java并发-通信工具类

文章目录1 Semaphore1.2 Semaphore简介1.2 Semaphore案例1.3 Semaphore原理2 Exchanger3 CountDownLatch3.1 CountDownLatch简介3.2 CountDownLatch案例4 CyclicBarrier4.1 CyclicBarrier简介4.2 CyclicBarrier Barrier被破坏4.4 CyclicBarrier原理在java.util.concurrent包下&…

浅谈Dubbo的异步调用

之前简单写了一下dubbo线程模型&#xff0c;提到了Dubbo底层是基于NIO的Netty框架实现的&#xff0c;通过IO线程池和Work线程池实现了请求和业务处理之间的异步从而提升性能。 这篇文章要写的是Dubbo对于消费端调用和服务端接口业务逻辑处理的异步&#xff0c;在2.7版本中Dubb…

1650_MIT 6.828 open函数的简单梳理

全部学习汇总&#xff1a; GreyZhang/g_unix: some basic learning about unix operating system. (github.com) 一个shell的例程分析了很长时间&#xff0c;里面的基础知识一层嵌套一层。不过&#xff0c;这也是补充基本知识的很好的机会。既然自己日常接触的更多的还是这种通…

C++ 15 string容器

目录 一、string容器 1.1 简介 1.2 构造函数 1.3 赋值操作 1.4 字符串拼接 1.5 字符串查找和替换 1.6 字符串比较 1.7 字符串存取 1.8 字符串插入和删除 1.9 子串获取 一、string容器 1.1 简介 ① string是C风格的字符串&#xff0c;而string本质上是一个类。 ② s…

TryHackMe-Sustah(boot2root)

Sustah 开发人员在他们的游戏中添加了反作弊措施。你是 能否突破限制以访问其内部 CMS&#xff1f; 端口扫描 循例 nmap Web枚举 80端口没啥东西&#xff0c;看一下8085端口 gobuster扫一下 /ping似乎没什么东西 回来home&#xff0c;看看burp 使用bash生成数字字典 使用ff…

【mongodb 基础2】Install MongoDB Community Edition on macOS

文章目录一. 安装准备Install Xcode Command-Line ToolsInstall Homebrew二. Installing MongoDB 6.0 Community Edition1. 下载MongoDB Homebrew 组件包2. 更新组件包3. 安装MongoDBTo install MongoDB三. 安装后包含的组件四. Run&stop MongoDB1. 作为macOS服务的方式运行…

计算机二级考试(C++)复习

文章目录基础知识部分C知识点部分C流操作基础知识部分 指令周期&#xff1a; 一般把计算机完成一条指令所花费的时间称为一个指令周期。指令周期越短&#xff0c;指令执行就越快。 顺序程序&#xff1a; 顺序程序具有顺序性、封闭性和可再现性的特点&#xff0c;使得程序设…

用 Java 演奏千千阙歌是什么体验?

JFugue简介 ​JFugue 是一个开放源代码编程库&#xff0c;它允许人们使用 Java 编程语言来编程音乐&#xff0c;而无需 MIDI 的复杂性。它由 David Koelle 于 2002 年首次发布。当前版本是 JFugue 5.0&#xff0c;已于 2015 年 3 月发布。Brian Eubanks 将 JFugue 描述为 “对于…