作者:指针不指南吗
专栏:蓝桥杯倒计时冲刺🐾马上就要蓝桥杯了,最后的这几天尤为重要,不可懈怠哦🐾
文章目录
- 1.最长递增
- 2.走迷宫
- 3.解立方根
- 4.回文特判
- 5.修改数组
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≤数列中的数≤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≤T≤10510^5105,0≤N≤10510^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 函数
-
reverse是C++下的库函数,可用于翻转字符串,翻转链表等
-
使用需要添加头文件
#include <algorithm>
-
reverse()会将区间[beg,end)内的元素全部逆序;
其中区间翻转1.reverse(str.begin(),str.end()) 反转字符串2.reverse(vector.begin(),vector.end()) 反转向量3.reverse(a,a+strlen(a)) 反转数组
-
该函数无返回值
-
错误使用
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≤10510^5105,1≤A i≤10610^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,直到与集合里面的元素不重复,然后放进集合里面去
#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; }
-
补充知识——并查集使用场景
- 两个元素是否在同一个集合里面出现过;
- 合并两个集合
-
反思
已经比较满意了,AC 80%
这个题,我开始的思路,是比较混乱的,没有理清楚关系,考虑全面
第二次之后,我觉得重复元素不断+1,是可以优化的,
取前面所有元素的最大值,然后让重复元素max+1,AW,T_T
这个题解:
- 更新父节点真是妙,每一个对应的父节点+1,正好修正我用 max