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

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

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

1.最长递增

• 题目

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

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

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

  输入描述

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

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

  其中， 2≤n≤1000，0≤数列中的数≤$10^4$。

  输出描述:

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

  输入输出样例

  输入

  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≤T≤$10^5$，0≤N≤$10^5$。

  输出描述

  输出共 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∣≤$10^6$，保证 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≤N≤$10^5$，1≤A i≤$10^6$。

  输出描述

  输出 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