作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾
文章目录
- 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
