作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾
文章目录
- 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≤数列中的数≤ 1 0 4 10^4 104。
输出描述:
输出一行包含一个整数，表示答案。
输入输出样例
输入
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≤ 1 0 5 10^5 105，0≤N≤ 1 0 5 10^5 105。
输出描述
输出共 T 行，分别表示每个测试数据的答案（答案保留 3 位小数）。
输入输出样例
输入
3 0 1 8输出
0.000 1.000 2.000 -
第一次 AC 100%
#include<bits/stdc++.h> using namespace std; #define eps 1e-5 int 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∣≤ 1 0 6 10^6 106，保证 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≤ 1 0 5 10^5 105，1≤A i≤ 1 0 6 10^6 106。
输出描述
输出 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]]; //把操作完的元素放进去 } else p[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
