蓝桥杯算法总结
序章
现处于大学生阶段，蓝桥杯算法竞赛算是我们的入门级竞赛，所以我们必须重视起来。
在这个算法总结中，我会用通俗易懂的语言，细致地讲述相关算法，希望能通过我的笔记，为大家带来一些帮助。
内容持续更新，坚持日更！
有任何想法可以在评论区提出，感谢观看。
递推和递归
递推
先简单介绍一下
递推算法：自底向上，由已知条件推导出位置结果的一种算法
核心：状态转移 边界+关系式
废话不多说，直接从题目入手理解递推思想
在这里选用信息学奥赛一本通的题：https://ybt.ssoier.cn/problem_show.php?pid=1314
题目意思理解：
从A点到B点的路径数，并且经过马能到达的点都无效，我们先做好前期的工作准备
//马走日，移动的位置（马能到达的点） int mx[] = {-1,-1,-2,-2,1,1,2,2}; int my[] = {-2,2,-1,1,-2,2,-1,1}; int vis[110][110]={0};//标记数组 int rd[110][110]={0};//记录每个点的路径数 //将马能到达的位置全标记成1 for(int i=0;i<=7;i++){ //马的坐标(cx,cy) int nx=cx+mx[i]; int ny=cy+my[i]; if(nx<0 || ny<0 || nx>n || ny>m)continue; vis[nx][ny]=1; } //别忘了把马的初始位置也标记成1 vis[cx][cy]=1;然后我们准备初始化边界，满足
//起点置为一 rd[0][0]=1; //初始化左边界和上边界 for(int i=1;i<=n;i++){ rd[i][0]=rd[i-1][0]; if(vis[i][0]==1)rd[i][0]=0; } for(int i=1;i<=m;i++){ rd[0][i]=rd[0][i-1]; if(vis[0][i]==1)rd[0][i]=0; }注意题目，棋子卒能挪动的方向只有向下和向右，说明在某个点K上，到达K的路径数为K上面的点+K左面的点
所以我们可以列出关系式： rd[i][j] = rd[i-1][j]+rd[i][j-1]
for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ //注意：马能到达的标记处 卒无法通过 if(vis[i][j]==1)continue; rd[i][j]=rd[i-1][j]+rd[i][j-1]; } }经过上述理解，我们就得到了完整代码
#include<bits/stdc++.h> using namespace std; int mx[] = {-1,-1,-2,-2,1,1,2,2}; int my[] = {-2,2,-1,1,-2,2,-1,1}; int vis[110][110]={0}; int rd[110][110]={0}; int main(){ int n,m,cx,cy; cin>>n>>m>>cx>>cy; vis[cx][cy]=1; for(int i=0;i<=7;i++){ int nx=cx+mx[i]; int ny=cy+my[i]; if(nx<0 || ny<0 || nx>n || ny>m)continue; vis[nx][ny]=1; } rd[0][0]=1; for(int i=1;i<=n;i++){ rd[i][0]=rd[i-1][0]; if(vis[i][0]==1)rd[i][0]=0; } for(int i=1;i<=m;i++){ rd[0][i]=rd[0][i-1]; if(vis[0][i]==1)rd[0][i]=0; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(vis[i][j]==1)continue; rd[i][j]=rd[i-1][j]+rd[i][j-1]; } } cout<<rd[n][m]<<endl; return 0; }但是，我们提交后的运行结果
并没有完全AC,但其实我们的代码逻辑是没有问题的，那到底错在哪儿了？
解答一下：其实是我们的数组越界/数据范围溢出了
我们只需要修改两处
插入 #define int long long
将 int main() 修改为 signed main()
以下是真正的正确代码
#include<bits/stdc++.h> using namespace std; #define int long long int mx[] = {-1,-1,-2,-2,1,1,2,2}; int my[] = {-2,2,-1,1,-2,2,-1,1}; int vis[110][110]={0}; int rd[110][110]={0}; signed main(){ int n,m,cx,cy; cin>>n>>m>>cx>>cy; vis[cx][cy]=1; for(int i=0;i<=7;i++){ int nx=cx+mx[i]; int ny=cy+my[i]; if(nx<0 || ny<0 || nx>n || ny>m)continue; vis[nx][ny]=1; } rd[0][0]=1; for(int i=1;i<=n;i++){ rd[i][0]=rd[i-1][0]; if(vis[i][0]==1)rd[i][0]=0; } for(int i=1;i<=m;i++){ rd[0][i]=rd[0][i-1]; if(vis[0][i]==1)rd[0][i]=0; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(vis[i][j]==1)continue; rd[i][j]=rd[i-1][j]+rd[i][j-1]; } } cout<<rd[n][m]<<endl; return 0; }小总结：
递推有两要素：边界条件和关系式
只要正确推出这两个要素，再从已知推未知，就可以轻松解决递推问题啦
递归
递归的经典引入
先简单介绍一下
递归算法：直接或间接地调用自身函数，循环回溯解决小问题，最后得出大问题的答案。
核心思想:找到终止条件（没有终止条件的递归会陷入无限循环）
我们还是结合经典例题来理解递归思想，我将先讲述一个简单的例题来让大家理解。
这里给出的例题是一本通中斐波那契数列：https://ybt.ssoier.cn/problem_show.php?pid=1201
理解题目意思：
斐波那契数列我们应该非常熟悉了，就是 f(n) = f(n-1)+f(n-2) ,其中 n != 1 ，n != 2
所以在这道题中，我们的必备公式就是： f(n) = f(n-1)+f(n-2)
放到函数中，就是让当前第n位函数回过头来调用它之前的两个函数，再让第n-1位函数回过头来调用它之前的两个函数，再让第n-2个函数......直到调用到最底层函数（也就是第一位函数），再一层一层返回结果
听起来有点抽象，我们结合代码理解一下
int fb(int x){ if(x==1 || x==2)return 1; return fb(x-1)+fb(x-2); }是不是逻辑清晰了很多？
#include<bits/stdc++.h> using namespace std; int fb(int x){ if(x==1 || x==2)return 1; return fb(x-1)+fb(x-2); } int main(){ int n;//测试数据的组数 cin>>n; while(n--){ int num; cin>>num; cout<<fb(num)<<endl; } } 这里给出完整代码
看到这里，大家应该对递归已经有了初步了解，接下来我们再深入理解一下
递归的深入理解
这里选用的是17年蓝桥杯省A组的真题：https://www.luogu.com.cn/problem/P8650
题目理解：
正则表达式中的 “（ ） ”以及括号内容物可以看成一组
“ | ”可以看成分界线，分界线两边的字符串长度互不干扰且相互独立
“ x ”就是普通的一个字符
让我们结合样例理解一下
((xx|xxx)x|(x|xx))xx
第一步：先拆分成组，寻找第一组
则第一组为(xx|xxx)
将“ | ”看成分界线，左右两边的字符串长度分别是2和3，所以取最大为3
第二步：往下正常找寻第二组
往下接着看(xx|xxx)x 遇见普通字符 x ，直接长度+1
紧接着遇见“ | ”，看成分界线，左边字符串长度为4 即(xx|xxx)x
右边找到第二组 (x|xx)
沿用上面的方法，这组字符串的最大长度为2
所以这个分界线得到的最大长度是4
第三步：接着找组
找到((xx|xxx)x|(x|xx))为一组
已经算出这组的结果为4
最后加上xx两个普通字符的长度
((xx|xxx)x|(x|xx))xx 的能接受的最长字符串长度为6
可以看出，我们的中心思想就是不断找组，然后根据不同符号进行不同判断
因为这个代码较为完整，不好拆分，所以我直接将完整代码贴给大家，并标明注释
#include<bits/stdc++.h> using namespace std; int i=0;//用于找寻字符串中的每个字符 string s; int Longest(){ int m_cnt=0;//当前组字符串最大长度 int cnt=0;//当前字符串长度 while(i < s.size()){ //遇见‘( ’ ,标志着新的一组的开始 if(s[i] == '('){ i++; //递归调用，算出新组的最长字符串长度 int n = Longest(); cnt += n; } else if(s[i] == 'x'){ //普通字符长度正常+1 cnt++; i++; } else if(s[i] == '|'){ //遇到分界线，就要比较左边界和右边界的大小了 //这里属于先记录下左边界的大小 //再将cnt清零记录右边界的大小 m_cnt = max(m_cnt,cnt); cnt=0; i++; } else {//遇见‘) ’,标志着这一组的结束 i++; break; } } return max(cnt,m_cnt);//组外可能存在普通的x，别忘了加上 } int main(){ cin>>s; cout<<Longest(); } 小总结：
递归最重要的一步：找到终止条件
我们找到式子之间的关系，再循环调用就可以解决问题啦
bfs广度优先搜索
基础模板
首先介绍一下bfs算法
bfs:是一种图的遍历算法，就是找到一个节点的相邻节点，再找相邻节点的相邻节点
核心思想：从浅到深，宽度遍历
从一个节点开始，找它的邻居，再找邻居的邻居....
bfs算法这里我会给两种基础模板
在不同情况下使用
用邻接矩阵实现时，它的结构较为简单，适合初学者去理解，但是空间复杂度大，
而且二维数组不能存储过大的数据
当遇见数据量庞大的时候，我们就可以选择邻接表来实现bfs了
临界矩阵实现bfs (代码加详细注释已给出)
注意：此模板是在无向图中，无向图有n个点，m条边
#include<bits/stdc++.h> using namespace std; int g[105][105];//建立邻接矩阵 int vis[105]; int n,m; void bfs(int start){ //建立队列 queue<int> q; q.push(start); vis[start] = 1; while(!q.empty()){ int cur = q.front(); q.pop(); //选定 cur 作为当前节点 //我们要找 cur 能够直接抵达哪些点 //i本质是在找下一个去哪 for(int i=1;i<=n;i++){ if(g[cur][i] == 1 && vis[i] == 0){//点cur和点i有通路，并且没有被标记过 vis[i] = 1; //把i点标记上 q.push(i); } } } } int main(){ cin >> n >> m; //无向图，没有边权 //若为有向图 ，就只存u点->v点一个通路就行 for(int i=1;i<=m;i++){ int u,v; cin >> u >> v; //u,v之间有通路，都给标记成1 g[u][v] = 1; g[v][u] = 1; } bfs(1);//遍历从1出发能到达的所有节点 return 0; }邻接表实现bfs
注意：此模板是在无向图中，无向图有n个点，m条边
#include<bits/stdc++.h> using namespace std; vector<int> adj[105]; //创建动态数组adj[i],在adj[i]中存储i能到达的所有点 int vis[105]; int n,m; void bfs(int start){ queue<int> q; q.push(start); vis[start] = 1; while(!q.empty()){ int cur = q.front(); q.pop(); //选定 cur 作为当前节点 //我们要找 cur 能够直接抵达哪些点 for(int i=0;i<adj[cur].size();i++){ int nxt = adj[cur][i]; if(vis[nxt] == 0){ vis[nxt] = 1; q.push(nxt); } } } } int main(){ cin >> n >> m; //无向图，没有边权 for(int i=1;i<=m;i++){ int u,v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } bfs(1); return 0; } 以上两个模板就是bfs算法的基础使用
接下来讲述bfs的常见用法
bfs最短路问题
我们根据具体问题，理解一下bfs的最短路题型
题目很简单，在无向图中，假设存在两个点a,b，求a点到b点的最短路径
#include<bits/stdc++.h> using namespace std; vector<int> adj[105]; int vis[105]; int n,m; int a,b; struct node{ int id; int step; }; void bfs(int start){ queue<node> q; node tmp;//表示初始节点 tmp.id = start; tmp.step = 0; q.push(tmp); vis[start] = 1; //开始BFS while(!q.empty()){ //队首节点的编号 int curId = q.front().id; //起点到队首节点的步数 int curStep = q.front().step; q.pop(); for(int i=0;i<adj[curId].size();i++){ //构造下一个节点 node nxt; nxt.id = adj[curId][i];//下一步去哪的编号 nxt.step = curStep + 1;// 去下个位置的步数 等于 当前步数+1 //如果下一个节点就是 b，那么直接输出答案就可以了 if(nxt.id == b){ cout << nxt.step << endl; return; } if(vis[nxt.id] == 0){//判断这个点去没去过 vis[nxt.id] = 1; q.push(nxt); } } } } int main(){ cin >> n >> m;//无向图有n个点，m条边 //无向图，没有边权 (看成是1) for(int i=1;i<=m;i++){ int u,v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } cin >> a >> b; bfs(a); return 0; } 相信看到这里，大家对bfs算法已经有了一定的了解，接下来我会介绍dfs算法，并在期间穿插讲解bfs真题，帮助大家更深入的理解。
dfs深度优先搜索
基础模板
先介绍一下
dfs算法：纵向搜索，深入搜索，尽可能深的探入搜索，直到无法搜索，然后回溯。
核心思想：递归调用
这里仍旧是两种实现方法
两种方法的优势同bfs算法，有忘记的请移步bfs基础模板章节
就个人而言，我认为dfs算法的模板更好理解，更简洁一点，但是大家不要被里面的逻辑绕晕了
先给出邻接矩阵实现dfs的基础模板，这里直接给出代码配以详细注释
（n个点，m条边的无向图）
#include<bits/stdc++.h> using namespace std; const int N=1000; int a[N][N]; int vis[N];//标记数组，初始为0，用来标记这个点是否访问过 void dfs(int cur){ vis[cur]=1;//标记当前点 //寻找下一个点去哪 for(int i=1;i<=n;i++){ //cur和i之间必须有边，并且i点没有访问过 if(a[cur][i]==1 && vis[i]==0){ dfs(i);//回溯找下一个点 } } } int main(){ cin >> n >> m;//无向图有n个点，m条边 //无向图，没有边权 (看成是1) for(int i=1;i<=m;i++){ int u,v; cin >> u >> v; a[u][v]=1; a[v][u]=1; } dfs(1); return 0; } 邻接表实现dfs的基础模板，这里直接给出代码配以详细注释
（n个点，m条边的无向图）
#include<bits/stdc++.h> using namespace std; const int N=1000; vector<int>a[N]; int vis[N];//标记数组，初始为0，用来标记这个点是否访问过 void dfs(int cur){ vis[cur]=1;//标记当前点 //寻找下一个点去哪 for(int i=1;i<a[cur].size();i++){ //a[cur]数组里存储的已经是和它有通路的点了 int nxt=a[cur][i]; if(vis[nxt]==0){ dfs(i);//回溯找下一个点 } } } int main(){ cin >> n >> m;//无向图有n个点，m条边 //无向图，没有边权 (看成是1) for(int i=1;i<=m;i++){ int u,v; cin >> u >> v; a[u].push_back(v); a[v].push_back(u); } dfs(1); return 0; } 迷宫问题
dfs版
简单介绍一下什么是迷宫问题：通常题型是要求从某点走到终点，期间有阻碍和正常通路，我们要做的就是判断能否走到终点。
我们结合例题理解一下
这里给出一本通中的例题：https://ybt.ssoier.cn/problem_show.php?pid=1215
照例我们来分析一下题目
从A点到达B点，期间可以上下左右移动，但是只能走‘路’，不能“撞墙”，有多组测试数组
开始答题
第一步：
我们把输入问题解决了，
已经知道有k组，其实直接while循环 + k--即可
如果你想要代码高级一点也可以格外设置一个输入函数，这里不做示例
并且我们要创建一个二维字符数组，用来存储迷宫
这里采用普通数组矩阵，我来解答一下为什么不用邻接表来解决这个问题？
还是哪个问题，我们有多组输入
如果我们用邻接表动态数组来做，除了第一组数据外的其他迷宫数据会直接填入，而不是清空后再填入
用邻接矩阵就很好地解决了这个问题，在输入新数据时，旧数据直接被清空了
然后我们还需要一个标记数组，标记这段路我们走过了，因为可以上下左右移动，如果不标记会反复移动在可以走的路的区间内，造成死循环
int n;//迷宫规模 char maze[110][110];//记录迷宫 int vis[110][110];//标记数组 int xA,yA,xB,yB; //控制上下左右移动的方向数组 int nx[]={-1,0,0,1}; int ny[]={0,-1,1,0}; int k;//测试的组数 cin>>k; while(k--){ cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ char c; cin>>c; maze[i][j]=c;//创建迷宫 vis[i][j]=0; } }第二步：
写dfs解决（其中一个解法）
这里结合代码和注释来直接给大家
bool dfs(int sx,int sy){ int cur_x=sx; int cur_y=sy; vis[cur_x][cur_y]=1;//把当前搜索点标记出来 if(cur_x == xB && cur_y == yB)return true;//返回终点值 for(int i=0;i<4;i++){ //记录搜寻的上下左右点的位置 int nxt_x=cur_x+nx[i]; int nxt_y=cur_y+ny[i]; //进行判断 if(judge(nxt_x,nxt_y) && vis[nxt_x][nxt_y]==0){ //接收dfs的返回值 if(dfs(nxt_x,nxt_y))return true; } } return false; }第三步：
判断的书写
相信大家在浏览上述代码的时候注意到了judge()函数
现在我来讲述一下这个判断函数的意义：
1.保证搜寻的点在迷宫内，没有出界限
2.保证走到的是路而不是墙
bool judge(int x,int y){ if(x<0 || y<0 || x>=n || y>=n)return false; if(maze[x][y]=='.')return true; else return false; } 到这里我们的基本思路已经理顺完成，下面给出完整代码
#include<bits/stdc++.h> using namespace std; int n;//迷宫规模 char maze[110][110];//记录迷宫 int vis[110][110];//标记数组 int xA,yA,xB,yB; //控制上下左右移动的方向数组 int nx[]={-1,0,0,1}; int ny[]={0,-1,1,0}; bool judge(int x,int y){ if(x<0 || y<0 || x>=n || y>=n)return false; if(maze[x][y]=='.')return true; else return false; } bool dfs(int sx,int sy){ int cur_x=sx; int cur_y=sy; vis[cur_x][cur_y]=1;//把当前搜索点标记出来 if(cur_x == xB && cur_y == yB)return true;//返回终点值 for(int i=0;i<4;i++){ //记录搜寻的上下左右点的位置 int nxt_x=cur_x+nx[i]; int nxt_y=cur_y+ny[i]; //进行判断 if(judge(nxt_x,nxt_y) && vis[nxt_x][nxt_y]==0){ //接收dfs的返回值 if(dfs(nxt_x,nxt_y))return true; } } return false; } int main(){ int k;//测试的组数 cin>>k; while(k--){ cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ char c; cin>>c; maze[i][j]=c;//创建迷宫 vis[i][j]=0; } } cin>>xA>>yA>>xB>>yB; bool ans=dfs(xA,yA); if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; } bfs版
上述bfs版本已经可以AC了，是不是感觉不错？
那这里我们讲一下bfs版
迷宫最短路问题：
dfs需要把所有可能路径罗列出来，指数级复杂度
bfs第一次走到那个点一定就是最短路，O(n)复杂度
基本思路是没有任何区别的，我们直接给出代码和注释
#include<iostream> #include<queue> using namespace std; int n;//迷宫规模 char maze[110][110];//记录迷宫 int vis[110][110];//标记数组 int xA, yA, xB, yB; //控制上下左右移动的方向数组 int nx[] = {-1, 0, 0, 1}; int ny[] = {0, -1, 1, 0}; bool judge(int x, int y) { if (x < 0 || y < 0 || x >= n || y >= n) return false; if (maze[x][y] == '.') return true; else return false; } void bfs(int sx, int sy) { queue<pair<int, int>> q; q.push({sx, sy}); vis[sx][sy] = 1; while (!q.empty()) { int cur_x = q.front().first; int cur_y = q.front().second; q.pop(); if (cur_x == xB && cur_y == yB) { return; } for (int i = 0; i < 4; i++) { int nxt_x = cur_x + nx[i]; int nxt_y = cur_y + ny[i]; if (judge(nxt_x, nxt_y) && vis[nxt_x][nxt_y] == 0) { q.push({nxt_x, nxt_y}); vis[nxt_x][nxt_y] = 1; } } } } int main() { int k;//测试的组数 cin >> k; while (k--) { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { char c; cin >> c; maze[i][j] = c;//创建迷宫 vis[i][j] = 0; } } cin >> xA >> yA >> xB >> yB; bfs(xA, yA); if (vis[xB][yB]) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }以上就是迷宫问题的基本思路和解法，希望带给大家一点启发。
