30个题型+代码(冲刺2023蓝桥杯)(中)

2023.3.13~8.13持续更新

AcW需要付费的题，可以考虑上洛谷，New Oj找替代，或者花点钱

目录

🍎注意

🌼前言

🌼十，KMP（留坑）

🌼十一，Trie（留坑）

🌼十二，BFS

👊(一)1562. 微博转发

🌳AC  BFS暴力 + queue + stack(未完成)

🌳AC  Floyd-Warshall暴力

👊（二）机器人的运动范围

🌳BFS  AC  40%

🌳BFS  AC  75%

🌳BFS  AC  100%

🌳DFS  AC  100%

👊（三）188. 武士风度的牛

👊（四）P1451 求细胞数量

🌳暴力BFS

🌳暴力DFS

👊（五）1810: [NewOJ Week 4] 超级骑士

🌳广搜  AC

🌳深搜  AC

🌼十三，DFS

👊（一）3502. 不同路径数

🌳Wrong Answer

🌳Accepted

👊（二）P1036 [NOIP2002 普及组] 选数

👊（三）P9011 [USACO23JAN] Air Cownditioning II B

🌳DFS + 二分  AC  100%

🌳暴力DFS  AC  82%

👊（四）1116: 组合的输出

👊（五）1117: 素数环

👊（六）1118: 自然数的拆分

🌼十四，拓扑排序（未更新）

🌼十五，Dijkstra

🌼十七，Floyd

👊（一）1488. 最短距离（未完待续）

👊（二）P2935 [USACO09JAN]Best Spot S

🌳Dijstra  AC

🌳Floyd  AC 

👊（三）P1119 灾后重建

🌼十六，SPFA（未更新）

🌼十八，最小生成树（未更新）

🌼十九，最近公共祖先（未更新）

🌼二十，二分图（未更新）

🍋总结 

🍎注意

本篇博客写了4个题型就31063字了，所以，剩下的我决定再写第四个博客

每10个题型写一个博客，分为上中下三个博客，12万字收尾

后续再补充剩下两个博客地址

(上)(1条消息) 30个题型+代码(冲刺2023蓝桥杯)(上)_码龄?天的博客-CSDN博客

(下)(2条消息) 30个题型+代码(冲刺2023蓝桥杯)(下)_千帐灯无此声的博客-CSDN博客

🌼前言

前缀和√，差分√，二分√，双指针√，递归√，递推√，BFS√，DFS√，Dijkstra√, Floyd√，质数筛，最大公约数，背包dp，线性dp，区间dp，组合计数，快速幂，哈希√，并查集√，博弈论 

每个类型第一题来自AcWing蓝桥杯集训-每日一题

1，花5块钱

2，上洛谷找替代 / 原题 

题型有

前缀和，差分，二分，双指针，递推，递归，并查集，哈希，单调队列，
KMP，Trie，BFS，DFS，拓扑排序，Dijkstra，Floyd，最小生成树，
最近公共祖先，二分图，筛质数，最大公约数，快速幂，组合计数，博弈论，
背包DP，线性DP，区间DP，树型DP，树状数组，线段树，矩阵乘法 

如果你想冲省一，拿22年A组为例，你得拿60分，也就是2道填空题 + 4道编程题

5 + 5 + 10 + 10 + 15 + 15

省赛需要掌握的有：

前缀和，差分，二分，双指针，递归，递推，BFS，DFS，Dijkstra, Floyd，质数筛，最大公约数，背包dp，线性dp，区间dp，组合计数，快速幂，哈希，并查集，博弈论

围绕省赛需要掌握的类型，针对性地下手

先给大家看个时间复杂度（来源于AcWing）

🌼十，KMP（留坑）

👂 Secret Base (吉他版)（未闻花名(绝美指弹吉他)） - uBio高尾和树 - 单曲 - 网易云音乐 

→ KMP算法笔记 - AcWing

→ KMP 算法详解 - AcWing

→ 字符串匹配 - OI Wiki (oi-wiki.org)

→ 前缀函数与 KMP 算法 - OI Wiki (oi-wiki.org)

→ KMP算法详解-彻底清楚了(转载+部分原创) - sofu6 - 博客园 (cnblogs.com)

→ KMP算法详解_小轩爱学习的博客-CSDN博客

→ KMP 算法详解 - 知乎 (zhihu.com)

→ 数据结构KMP算法配图详解（超详细）_kmp算法图解_哈顿之光的博客-CSDN博客

🌼十一，Trie（留坑）

👂 想去海边 - 夏日入侵企画 - 单曲 - 网易云音乐

🌼十二，BFS

👂 逝年 - 夏小虎 - 单曲 - 网易云音乐

👇BFS科普博客

→ 《啊哈算法第四章之bfs》（17张图解）_码龄?天的博客-CSDN博客

先将科普博客敲一遍

就是将迷宫按二维数组输入，0表示空地，1表示障碍物，输出起点到终点的步数

由于是一步一步扩展的，这个步数就是最短路

⚠ 只有边权为1，才能用用BFS求最短路

//迷宫2维数组里, 1障碍, 0未走过的空地, -1走过的空地
#include<cstdio> //scanf(), printf()
int a[51][51];
struct note
{int x, y, s; //横坐标,纵坐标,步数
};
int main()
{struct note que[2501]; //声明队列为结构体int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组int n, m; //n行m列scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)scanf("%d", &a[i][j]);int startx, starty, p, q; //起点终点坐标scanf("%d%d%d%d", &startx, &starty, &p, &q);//队列初始化int head = 1, tail = 1;//往队列插入迷宫入口坐标que[tail].x = startx;que[tail].y = starty;que[tail].s = 0; //入口步数为0tail++;a[startx][starty] = -1; //标记走过int flag = 0; //标记是否到达终点//当队列不为空int tx, ty; //临时变量while(head < tail) {//枚举四个方向for(int i = 0; i < 4; ++i) {tx = que[head].x + next[i][0];ty = que[head].y + next[i][1];//判断越界if(tx < 1 || ty < 1 || tx > n || ty > m)continue;//判断不为障碍且未走过if(a[tx][ty] == 0) {//bfs每个点只入队一次a[tx][ty] = -1;//新的点入队que[tail].x = tx;que[tail].y = ty;que[tail].s = que[head].s + 1; //上一步再+1tail++; //放最后}//到达终点if(tx == p && ty == q) {flag = 1;break;}}if(flag) break;head++; //继续后续点的扩展}//tail指向队尾下一位, 要-1printf("%d", que[tail - 1].s);return 0;
}

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3
7

👇看动图 

→ 图文详解 DFS 算法 和 BFS 算法 - 墨天轮 (modb.pro)

→ 熬夜怒肝，图解算法！BFS和DFS的直观解释_Jack-Cui的博客-CSDN博客

👇bfs适用场景

→ 什么时候用DFS，什么时候用BFS? - 菜鸟龙* - 博客园 (cnblogs.com)

→ (1条消息) DFS和BFS应用场景（什么时候用）_bfs与dfs应用场景_binddddd的博客-CSDN博客

👊(一)1562. 微博转发

1562. 微博转发 - AcWing题库

标签：图论，BFS，中等，PAT甲级

思路

由样例可知，求最大转发量，就是求L层以内，关注这个用户的人数（不包括用户自己）

所以是有向图的多源最短路

嗯。。我不会邻接表，邻接矩阵和堆优化，所以只能暴力了，所幸这题数据量不大，暴力似乎也能过

🌳AC  BFS暴力 + queue + stack(未完成)

对每个点BFS一次

⚠ 只有边权为1，才能用用BFS求最短路

1，每个点要记录当前层数

2，同时用 st 数组判断是否访问过，防止重复入队

但是暴力bfs结合queue和stack，以减少代码量

bla...
//水一下，不会用Bfs做，先空着

🌳AC  Floyd-Warshall暴力

1，用一个二维数组存储图

2，Floyd，O(n^3)时间复杂度--暴力

3，最后要开O2优化

👇floyd科普博客（核心代码只有5行）

→ 最短路之Floyd-Warshall（10张图解）_码龄?天的博客-CSDN博客

再默写一遍floyd

#include<cstdio>
int e[10][10], k,i,j,n,m, t1,t2,t3, inf = 1e9;
int main()
{scanf("%d%d", &n, &m);//初始化地图for(i = 1; i <= n; ++i)for(j = 1; j <= n; ++j)if(i != j)e[i][j] = inf;//读入边for(i = 0; i < m; ++i) {scanf("%d%d%d", &t1, &t2, &t3);e[t1][t2] = t3;}//Floyd核心代码5行for(k = 1; k <= n; ++k)for(i = 1; i <= n; ++i)for(j = 1; j <= n; ++j)if(e[i][j] > e[i][k] + e[k][j])e[i][j] = e[i][k] + e[k][j];//打印i到j的最短路for(i = 1; i <= n; ++i) {for(j = 1; j <= n; ++j)printf("   %d", e[i][j]);printf("\n");}return 0;
}

注意AC代码有个小坑，因为输入的第i组数据，表示i所关注的几个人，所以

代码第34行是 e[j][i] <= L，而不是 e[i][j] <= L

样例过了，再编一组测试

8 2
3 3 4 7
3 4 8 1
1 6
1 5
2 6 4
0
0
2 3 4
8 1 2 3 4 5 6 7 8
1
0
3
4
4
5
2
1

说下AC之前的2次错误吧

1，Segmentation Fault，内存超限，e[10][10] --> e[1010][1010]

2，Time Limit Exceeded，时间超限，可我寻思别人也能Floyd过，我咋不行

因为第一行没加#pragma GCC optimize(2)

这个是什么呢，类似洛谷的O2优化，而且蓝桥杯是支持的

它的好处是常数优化，卡极限AC，当然也有坏处

据说PAT不开O2优化能过，但是AcW不开就time limit

AC  代码

#pragma GCC optimize(2)
#include<cstdio>
int e[1010][1010], k,i,j,n,q, t1, inf = 1e9;
int main() //询问q次
{int L;scanf("%d%d", &n, &L);//初始化图for(i = 1; i <= n; ++i)for(j = 1; j <= n; ++j)if(i != j)e[i][j] = inf; //infinity无穷//读入边for(i = 1; i <= n; ++i) { //读入n次关注的人scanf("%d", &j); //关注j个人while(j) {j--;scanf("%d", &t1);e[i][t1] = 1; //顶点i到顶点t1距离为1}}//Floyd核心代码for(k = 1; k <= n; ++k)for(i = 1; i <= n; ++i)for(j = 1; j <= n; ++j)if(e[i][j] > e[i][k] + e[k][j])e[i][j] = e[i][k] + e[k][j];//q次询问scanf("%d", &q);while(q) {q--;int ans = 0;scanf("%d", &i);for(int j = 1; j <= n; ++j)if(i != j && e[j][i] <= L) //注意是j指向ians += 1;printf("%d\n", ans);}return 0;
}

所以说，Floyd的O(n^3)做这种数据量的题，也是有点勉强的，但放在蓝桥杯，数据量不太大的情况，足以骗到80%的分 

👊（二）机器人的运动范围

24. 机器人的运动范围 - AcWing题库

标签：BFS，DFS，简单，剑指offer

我一开始想，谁这么傻，不是两层暴力就出来了吗

🌳BFS  AC  40%

class Solution {
public:int get_num(int x, int y){int s = 0;while(x) {s += x % 10;x /= 10;}while(y) {s += y % 10;y /= 10;}return s;}int movingCount(int threshold, int rows, int cols){int ans = 0;for(int i = 0; i < rows; ++i)for(int j = 0; j < cols; ++j) {int now = get_num(i, j);if(now <= threshold)ans += 1;}return ans;}
};

但我忽略了现实条件，有个真实不虚的机器人在移动，它是不可以飞的，而由于判断小于k的要求是，每一位相加判断（而不是两数相加），所以存在get_num(i, j) <= k但机器人无法到达的情况

所以还是得用BFS

🌳BFS  AC  75%

class Solution {
public:int getnum(int x, int y){int s = 0;while(x) {s += x % 10;x /= 10;}while(y) {s += y % 10;y /= 10;}return s;}struct node{int x, y, s; //横坐标,纵坐标,路程};int movingCount(int k, int rows, int cols){int book[51][51] = {0};struct node q[2510]; //队列扩展大于50*50即可//初始化队列int head = 0, tail = 0;q[tail].x = 0;q[tail].y = 0;q[tail].s = 1;tail++;book[0][0] = 1; //标记起点走过int tx, ty; //临时变量int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组//当队列不为空while(head < tail) {for(int i = 0; i < 4; ++i) {tx = q[head].x + next[i][0];ty = q[head].y + next[i][1];//判断边界if(tx < 0 || ty < 0 || tx >= rows || ty >= cols)continue;//未到达过//此处if是所有bfs区别的地方if(book[tx][ty] == 0 && getnum(tx, ty) <= k) {book[tx][ty] = 1;q[tail].x = tx;q[tail].y = ty;q[tail].s = q[tail - 1].s + 1; //路程+1tail++; //放最后}}head++; //继续其他点的扩展}return q[tail - 1].s; //tail指向队尾下一位, 要-1}
};

有个坑，如果行或列任一为0，说明方格不存在，只能输出0，最后需要分类讨论

🌳BFS  AC  100%

AcW代码

class Solution {
public:int getnum(int x, int y){int s = 0;while(x) {s += x % 10;x /= 10;}while(y) {s += y % 10;y /= 10;}return s;}struct node{int x, y, s; //横坐标,纵坐标,路程};int movingCount(int k, int rows, int cols){int book[51][51] = {0};struct node q[2510]; //队列扩展大于50*50即可//初始化队列int head = 0, tail = 0;q[tail].x = 0;q[tail].y = 0;q[tail].s = 1;tail++;book[0][0] = 1; //标记起点走过int tx, ty; //临时变量int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组//当队列不为空while(head < tail) {for(int i = 0; i < 4; ++i) {tx = q[head].x + next[i][0];ty = q[head].y + next[i][1];//判断边界if(tx < 0 || ty < 0 || tx >= rows || ty >= cols)continue;//未到达过//此处if是所有bfs区别的地方if(book[tx][ty] == 0 && getnum(tx, ty) <= k) {book[tx][ty] = 1;q[tail].x = tx;q[tail].y = ty;q[tail].s = q[tail - 1].s + 1; //路程+1tail++; //放最后}}head++; //继续其他点的扩展}if(rows == 0 || cols == 0)return 0;elsereturn q[tail - 1].s; //tail指向队尾下一位, 要-1}
};

本地编译器代码

#include<iostream>
using namespace std;
int book[51][51];
struct node
{int x, y, s; //横坐标,纵坐标,路程
};
int getnum(int x, int y)
{int s = 0;while(x) {s += x % 10;x /= 10;}while(y) {s += y % 10;y /= 10;}return s;
}
int main()
{struct node q[2510]; //队列扩展大于50*50即可int k, rows, cols;cin>>k>>rows>>cols;//初始化队列int head = 0, tail = 0;q[tail].x = 0;q[tail].y = 0;q[tail].s = 1;tail++;book[0][0] = 1; //标记起点走过int tx, ty; //临时变量int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组//当队列不为空while(head < tail) {for(int i = 0; i < 4; ++i) {tx = q[head].x + next[i][0];ty = q[head].y + next[i][1];//判断边界if(tx < 0 || ty < 0 || tx >= rows || ty >= cols)continue;//未到达过//此处if是所有bfs区别的地方if(book[tx][ty] == 0 && getnum(tx, ty) <= k) {book[tx][ty] = 1;q[tail].x = tx;q[tail].y = ty;q[tail].s = q[tail - 1].s + 1; //路程+1tail++; //放最后}}head++; //继续其他点的扩展}if(rows == 0 || cols == 0)cout<<0;elsecout<<q[tail - 1].s; //tail指向队尾下一位, 要-1return 0;
}

🌳DFS  AC  100%

貌似剑指offer还是可以声明全局变量，力扣不可以

尽管可以声明，给来的movingCount依旧是核心代码模式，所以

我给dfs函数整了5个参数

当然，据说可以

1，直接int dfs()，在函数里操作

2，通过取地址符传参

AcW代码

没有办法，只能给dfs整5个参数，取地址符不会用，dfs函数里直接操作也不会

class Solution {
public:
int book[51][51], vis[51][51], ans = 0;
int tx, ty;int getnum(int x, int y){int s = 0;while(x) {s += x % 10;x /= 10;}while(y) {s += y % 10;y /= 10;}return s;}void dfs(int x, int y, int k, int rows, int cols){int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//枚举4个方向for(int i = 0; i < 4; ++i) {//下一点坐标tx = x + next[i][0];ty = y + next[i][1];//超出范围if(tx < 0 || ty < 0 || tx >= rows || ty >= cols)continue;//没访问过且小于kif(book[tx][ty] == 0 && getnum(tx, ty) <= k) {book[tx][ty] = 1; //标记dfs(tx, ty, k, rows, cols); //递归book[tx][ty] = 0; //取消标记}}//切记, ans += 1的if判断放外面if(vis[x][y] == 0) {ans += 1;vis[x][y] = 1;}}int movingCount(int k, int rows, int cols){book[0][0] = 1;dfs(0, 0, k, rows, cols);if(rows == 0 || cols == 0)return 0;elsereturn ans;}
};

本地编译代码

#include<iostream>
using namespace std;
int book[51][51], vis[51][51], ans = 0;
int k, rows, cols, tx, ty;
int getnum(int x, int y)
{int s = 0;while(x) {s += x % 10;x /= 10;}while(y) {s += y % 10;y /= 10;}return s;
}
void dfs(int x, int y)
{int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//枚举4个方向for(int i = 0; i < 4; ++i) {//下一点坐标tx = x + next[i][0];ty = y + next[i][1];//超出范围if(tx < 0 || ty < 0 || tx >= rows || ty >= cols)continue;//没访问过且小于kif(book[tx][ty] == 0 && getnum(tx, ty) <= k) {book[tx][ty] = 1; //标记dfs(tx, ty); //递归book[tx][ty] = 0; //取消标记}}//切记, ans += 1的if判断放外面if(vis[x][y] == 0) {ans += 1;vis[x][y] = 1;}
}
int main()
{cin>>k>>rows>>cols;book[0][0] = 1;dfs(0, 0);if(rows == 0 || cols == 0)cout<<0;elsecout<<ans;return 0;
}

-- -- --梳理-- -- --

bfs核心是扩展，dfs核心是递归

相同点

1，方向数组next[4][2]        2,getnum()按题意写（当然有时不需要getnum）

区别

bfs构造完getnum()后，直接进入主函数，通过队列和开头的while(head < tail)得到答案

dfs构造完getnum()后，还要构造dfs()，这才进入主函数，然后调用函数得到答案 

bfs的主体是在主函数里通过队列实现的(也可放函数外)，dfs主体在主函数外通过递归实现 

其实很多迷宫题，都需要getnum()这个函数，当然实现会有点区别

👊（三）188. 武士风度的牛

188. 武士风度的牛 - AcWing题库

标签：搜索，BFS，简单

BFS模板，因为不熟悉，我写了50分钟才写出来，然后样例没对。。

找了20分钟，没找到哪里错了，后来别人说，方向数组错了

一开始写成

int next[8][2] = {{1,0},{-1,0},{2,0},{-2,0},{0,1},{0,-1},{0,2},{0,-2}};
...
...
int dd = abs(next[i][0]) - abs(next[i][1]);//超出范围或不符合马走势if(tx < 0 || ty < 0 || tx >= r || ty >= c || dd == 0)continue;

但是dd == 0，并不能保证按马的走，会出现很多(2, 0)，(-2, 0)，(0, 2)，(0, 1)这种玩意

明明之前用过类似的，比如

int next[4][2] = {{-1, 0}, //上{1, 0},  //下{0, -1}, //左{0, 1}}; //右

但这个是迷宫中，每次走一步，结果这次只是换了点东西就错了

思维定势太严重，，，还得多接触下不同的题，培养思考习惯，而不是套模板习惯

方向数组改成这个后

int next[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};

我又编了一组测试

6 5
.....
K....
.....
..*..
.....
.*.H.
3

然后提交，AC了

AC  代码

#include<iostream>
#include<cmath> //abs()
using namespace std;
char a[151][151];
int startx, starty, p, q, tx, ty, flag = 0; //p,q 终点坐标
struct node
{int x, y, s; //横坐标,纵坐标,步数
};
int main()
{//方向数组struct node que[22510];int next[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};int c, r; //c列r行cin>>c>>r;//读入地图//记得是从0开始, 后续都受这个影响for(int i = 0; i < r; ++i)for(int j = 0; j < c; ++j) {cin>>a[i][j];if(a[i][j] == 'K')startx = i, starty = j; //起点if(a[i][j] == 'H')p = i, q = j; //终点}//队列初始化int head = 0, tail = 0;que[tail].x = startx;que[tail].y = starty;que[tail].s = 0;tail++;a[startx][starty] = '*'; //标记走过//当队列不为空while(head < tail) {//枚举四个方向for(int i = 0; i < 8; ++i) {tx = que[head].x + next[i][0];ty = que[head].y + next[i][1];int dd = abs(next[i][0]) - abs(next[i][1]);//超出范围或不符合马走势if(tx < 0 || ty < 0 || tx >= r || ty >= c || dd == 0)continue;//不为障碍且没走过if(a[tx][ty] == '.') {//bfs每个点只入队一次a[tx][ty] = '*'; //标记走过que[tail].x = tx;que[tail].y = ty;que[tail].s = que[head].s + 1;tail++;}if(tx == p && ty == q) {flag = 1;break;}}if(flag) break;head++; //继续后续队列扩展}cout<<que[tail - 1].s; //tail指向队尾下一位, 要-1return 0;
}

👊（四）P1451 求细胞数量

P1451 求细胞数量 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：搜索，BFS，DFS，普及-

一开始看到分成几块，第一时间以为可以用并查集，想了大半小时没结果，因为一个元素分横纵坐标两个变量，可以考虑用结构体，但比BFS难实现多了

所以没有最好的算法，只有最合适的算法

🌳暴力BFS

基础思路：写个bfs函数，访问过的点标记好

主函数中两层for循环遍历每个点直到所有非0点都遍历过

最后输出细胞数

这里不用book数组，我们直接在存储地图的二维数组a上直接操作，访问过的点赋值为0即可

还要注意下输入问题，可以按我的，转整型再放进二维数组

也可以直接按char[][]输入，直接对字符判断

哪个熟练用哪个

额外的测试

5 7
1024540
0314350
1230123
1213010
1230230
2

AC  代码

#include<iostream>
using namespace std; //string s;
int a[110][110], ans = 0, n, m, tx, ty;
struct node
{int x, y; //横坐标, 纵坐标, 编号
};
struct node que[10010]; //100*100
void bfs(int x, int y)
{int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组//初始化队列int head = 0, tail = 0;que[tail].x = x;que[tail].y = y;tail++;a[x][y] = 0; //标记//队列不为空while(head < tail) {//枚举4个方向for(int i = 0; i < 4; ++i) {tx = que[head].x + next[i][0];ty = que[head].y + next[i][1];//超出范围或不为细胞if(tx < 0 || ty < 0 || tx >= n || ty > m || a[tx][ty] == 0)continue;a[tx][ty] = 0; //标记que[tail].x = tx;que[tail].y = ty;tail++;}head++; //继续后续点的扩展}
}
int main()
{cin>>n>>m;string s[n];//按字符串读入for(int i = 0; i < n; ++i)cin>>s[i];//2维数组建表for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j) {a[i][j] = s[i][j] - '0'; //字符转10进制整数}//对所有点BFSfor(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j) {if(a[i][j] != 0) {bfs(i, j);ans += 1;}}cout<<ans;return 0;
}

🌳暴力DFS

由于代码第15行，我不确定是否要按模板常规的取消标记（标记，递归，取消标记的套路）

所以，第一次保留了取消标记，输出错误

第二次，去掉了取消标记，输出正确，但是不放心，就又试了一次

额外的测试

4 5
11110
11101
11001
01010
3

居然对了，忘了dfs遇到死胡同，会自动递归回上一步，直到有通路的全部点访问完

AC  代码

#include<iostream>
using namespace std; //string s;
int a[110][110], ans = 0, n, m, tx, ty;
void dfs(int x, int y)
{a[x][y] = 0; //标记int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组for(int i = 0; i < 4; ++i) {tx = x + next[i][0];ty = y + next[i][1];if(tx < 0 || ty < 0 || tx >= n || ty >= m || a[tx][ty] == 0)continue;a[tx][ty] = 0; //标记dfs(tx, ty); //递归}
}
int main()
{cin>>n>>m;string s[n];//按字符串读入for(int i = 0; i < n; ++i)cin>>s[i];//2维数组建表for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j) {a[i][j] = s[i][j] - '0'; //字符转10进制整数}//对所有点BFSfor(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j) {if(a[i][j] != 0) {dfs(i, j);ans += 1;}}cout<<ans;return 0;
}

才39行，比bfs少了20行，虽然很多人说dfs难，但好实现

👊（五）1810: [NewOJ Week 4] 超级骑士

P1810 - [NewOJ Week 4] 超级骑士 - New Online Judge (ecustacm.cn)

👂 今晚约会吧（踩着落日余晖） - SORROW - 单曲 - 网易云音乐

标签：进阶题，深搜，广搜

 DFS，BFS都可以，都尝试下

思路

一开始也一头雾水，看了大佬的文字解释，自己再开干

1，如何判断一个骑士可以走遍整个空间？

只要这个骑士能从(x, y)走到(x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1)

则骑士可以走遍平面

2，由于每步坐标不超过100，可以从(100, 100)出发，暴力走(0 ~ 200, 0 ~ 200)的二维平面，最后检查(100, 100)四周是否被标记(走过)

思路来源NewOJ Week 4题解_[newoj week 4] 减一_傅志凌的博客-CSDN博客

里的E题

🌳广搜  AC

第一次提交

运行错误，一般是数组超限

struct node que[40010]; 
--> struct node que[41000];

不够严谨哈，算数也算错，一开始是想到201*201的，但是201 * 201 != 40001， 

200*201 = 200*200+1*200 = 40200，而201*201还得加上201，== 40401

你个菜鸡

修改后提交，AC 90%，时间超限

AC  90%

#include<iostream>
#include<cstring> //memset()
using namespace std;
int vis[205][205]; //标记
int dx[110], dy[110]; //direction方向
int tx, ty; //临时变量
struct node
{int x, y; //横纵坐标
};
int main()
{struct node que[50010];int t;cin>>t;while(t--) {//归0memset(que, 0, sizeof(que)); //清空结构体数组memset(vis, 0, sizeof(vis)); //清空标记过的点int n;cin>>n;//读入方向for(int i = 0; i < n; ++i)cin>>dx[i]>>dy[i];//初始化队列int head = 0, tail = 0;que[tail].x = 100;que[tail].y = 100;tail++;vis[100][100] = 1; //标记//队列不为空while(head < tail) {//枚举n个方向for(int i = 0; i < n; ++i) {tx = que[head].x + dx[i];ty = que[head].y + dy[i]; //新的坐标//超出边界if(tx < 0 || ty < 0 || tx > 200 || ty > 200)continue;//未访问过if(vis[tx][ty] == 0) {vis[tx][ty] = 1;que[tail].x = tx;que[tail].y = ty;tail++;}}head++; //继续后续队列的扩展}if(vis[99][100] && vis[101][100]&& vis[100][99] && vis[100][101])cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

应该dfs在这题复杂度稍微低了点的原因，bfs得开scanf()才AC

所有cin改scanf()好了

AC  100%

#include<iostream>
#include<cstring> //memset()
#include<cstdio> //scanf()
using namespace std;
int vis[205][205]; //标记
int dx[110], dy[110]; //direction方向
int tx, ty; //临时变量
struct node
{int x, y; //横纵坐标
};
int main()
{struct node que[41000];int t;scanf("%d", &t);while(t--) {//归0memset(que, 0, sizeof(que)); //清空结构体数组memset(vis, 0, sizeof(vis)); //清空标记过的点int n;scanf("%d", &n);//读入方向for(int i = 0; i < n; ++i)scanf("%d%d", &dx[i], &dy[i]);//初始化队列int head = 0, tail = 0;que[tail].x = 100;que[tail].y = 100;tail++;vis[100][100] = 1; //标记//队列不为空while(head < tail) {//枚举n个方向for(int i = 0; i < n; ++i) {tx = que[head].x + dx[i];ty = que[head].y + dy[i]; //新的坐标//超出边界if(tx < 0 || ty < 0 || tx > 200 || ty > 200)continue;//未访问过if(vis[tx][ty] == 0) {vis[tx][ty] = 1;que[tail].x = tx;que[tail].y = ty;tail++;}}head++; //继续后续队列的扩展}if(vis[99][100] && vis[101][100]&& vis[100][99] && vis[100][101])cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

 emmm...有大佬跟我说，不开scanf()，bfs也能AC

说没必要用数组模拟队列，直接用stl的#include<queue>就好，更快一点

🌳深搜  AC

#include<iostream>
#include<cstring> //memset()
int vis[210][210], dx[110], dy[110];
int t, n, tx, ty;
void dfs(int x, int y)
{for(int i = 0; i < n; ++i) {tx = x + dx[i];ty = y + dy[i];if(tx < 0 || ty < 0 || tx > 200 || ty > 200)continue;if(vis[tx][ty] == 0) {vis[tx][ty] = 1;dfs(tx, ty);//不用取消标记了}}
}
using namespace std;
int main()
{cin>>t;while(t--) {memset(vis, 0, sizeof(vis));cin>>n;for(int i = 0; i < n; ++i)cin>>dx[i]>>dy[i];vis[100][100] = 1;dfs(100, 100);if(vis[99][100] && vis[101][100] && vis[100][99] && vis[100][101])cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return 0;
}

难以置信，居然只有37行，而BFS写了58行，大概少20行

由于第一遍写了2次BFS，DFS只写了13分钟

🌼十三，DFS

知识点

在写一篇DFS总结（包含所有题型方法和例题、链接、AC代码），抛开较难的二分图和树的遍历，还有8个题型，不过在写的博客很多，可能需要23年5月后才有时间写

科普博客

→ 《啊哈算法》第四章之深度优先搜索_千帐灯无此声的博客-CSDN博客

加深理解

→ DFS（搜索） - OI Wiki

→ DFS（图论） - OI Wiki

精益求精

在开始之前，我想先对BFS和DFS作个简单的区分

dfs可以用递归来写，也可以用栈来写；bfs可以用数组模拟队列，也可以直接stl的队列

dfs很难找到最优解，只用来找到某个解，内存消耗较小；bfs则适用于找最优解，但不适用于深层次的搜索

dfs如果需要回溯，就需要取消标记；而bfs不需要取消标记

接下来谈谈最近dfs刷题的思考：

第一点思考

关于，为什么有些dfs需要在标记，递归后进行取消标记，而另一些题目则不需要取消标记呢？

eg1: 给定起点，走5步，求所有可能到达的点

eg2: 给定起点，不限制步数，求能否到达终点

问题1限制了步数，所以经过某点的路径会影响结果，那么就需要多次经过同一个点（意味着需要回溯），所以需要取消标记

而问题2经过某点的路径不影响结果（不限制步数），所以不需要多次经过同一个点（不需要回溯），所以不需要取消标记

一次能把所有点走完，不需要取消标记（不需要回溯），走过的点就不会再走了

而如果部分路径需要多次访问，这时就需要回溯取消标记了，不然就没法访问了

第二点思考

这个return;有时可以去掉，具体情况具体分析，需要判断什么时候这里的return;会冗余，加上去会起到什么作用

如果这个return和这层函数的结尾之间没有其他东西，就可以不加

折腾了一个小时没个结论，所以以后都加上吧👌

-- -- End~

👊（一）3502. 不同路径数

3502. 不同路径数 - AcWing题库

标签：DFS，简单，笔试题

常规dfs加了点变化

因为这点变化，只会做模板题的我，第一次没AC（看了别人的代码才发现多写了个vis[]标记数组，本题是不需要标记数组的）

具体为什么后面解释

🌳Wrong Answer

#include<iostream>
#include<set>
using namespace std;
int n, m, k, a[10][10], vis[10][10];
int sum, tx, ty;
set<int>st; //元素不重复void dfs(int x, int y, int s, int sum) //横坐标,纵坐标,步数,当前值
{//方向数组int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//判断边界if(s == k) {st.insert(sum); //集合元素不重复return;}//枚举四个方向for(int i = 0; i < 4; ++i) {tx = x + next[i][0];ty = y + next[i][1];if(tx < 0 || ty < 0 || tx >= n || ty >= m)continue;if(vis[tx][ty] == 0) {vis[tx][ty] = 1; //标记dfs(tx, ty, s + 1, sum * 10 + a[tx][ty]);vis[tx][ty] = 0; //取消标记}}
}int main()
{cin>>n>>m>>k;//读入矩阵for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j)cin>>a[i][j];for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j)dfs(i, j, 0, a[i][j]); //建议4个参数, 不要3个cout<<st.size();return 0;
}

为什么要去掉标记数组(vis[][]或book[][])呢？

因为题目说的很清楚，走过的位置可以重复走（可以回头）

比如初始在a[2][3] == 3, k == 2，规定只能走2步，此时存在向下走一步，再走回来的可能

也就是经历了a[2][3] --> a[3][3] --> a[2][3]三个点，如果加上vis[][]数组，只能走一条不可回头的路

拿到题目第一时间，是观察题目，和常规模板题的情景有哪些区别

在此基础上，给模板加细节，才有机会做对

否则你永远只会做模板题，没前途的

🌳Accepted

注释掉中间4行就AC了

#include<iostream>
#include<set>
using namespace std;
int n, m, k, a[10][10]; //vis[10][10];
int sum, tx, ty;
set<int>st; //元素不重复void dfs(int x, int y, int s, int sum) //横坐标,纵坐标,步数,当前值
{//方向数组int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//判断边界if(s == k) {st.insert(sum); //集合元素不重复return;}//枚举四个方向for(int i = 0; i < 4; ++i) {tx = x + next[i][0];ty = y + next[i][1];if(tx < 0 || ty < 0 || tx >= n || ty >= m)continue;//if(vis[tx][ty] == 0) {//vis[tx][ty] = 1; //标记dfs(tx, ty, s + 1, sum * 10 + a[tx][ty]);//vis[tx][ty] = 0; //取消标记//}}
}int main()
{cin>>n>>m>>k;//读入矩阵for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j)cin>>a[i][j];for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j)dfs(i, j, 0, a[i][j]); //建议4个参数, 不要3个cout<<st.size();return 0;
}

 👂 理想世界 - 马良 - 单曲 - 网易云音乐

👊（二）P1036 [NOIP2002 普及组] 选数

P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：DFS，普及-，素数

虽然看起来简单，貌似是全排列，但是有点绕，你要判重，直接套DFS模板样例都过不了
甚至比不上直接多重for，，，

Wrong

#include<iostream>
using namespace std;
int n, k, ans;
int a[30], vis[30];
bool check(long long x) //判断素数
{if(x == 1) return false;if(x == 2 || x == 3) return true;for(int i = 2; i * i <= x; ++i) {if(x % i == 0)return false;}return true;
}
void dfs(int s, long long sum) //step步数, 总和sum
{//完成任务if(s == k) {if(check(sum)) {ans += 1;//cout<<sum<<endl;}return; //回溯}//遍历for(int i = 0; i < n; ++i) {if(vis[i] == 0) {vis[i] = 1; //标记dfs(s + 1, sum + a[i]); //递归vis[i] = 0; //取消标记}}
}
int main()
{cin>>n>>k;for(int i = 0; i < n; ++i)cin>>a[i];dfs(0, 0); //从第0个数字, 总和为0开始cout<<ans;return 0;
}

4 3
3 7 12 19
6

正常用dfs模板会出现，先选后面的数，再选前面数的情况，就会重复 

已知29是唯一答案，经过了6次29...

假如现在给定1~6，6个数，里面选4个，如何实现按 1 + 2 + 3 + 4, 1 + 2 + 3 + 5
1 + 2 + 3 + 6(第一轮)，1 + 2 + 4 + 5, 1 + 2 + 4 + 6(第二轮)......直到 4 + 5 + 6的顺序呢
也就是，如何判重呢（这里是不同数字组合的判重，而不是总和的判重）

我们在dfs函数中加个参数

dfs中参数startx作用是, 每次只能选它后面的数；而不能先选后面再选前面的（上个代码的错误）

AC  代码

#include<iostream>
using namespace std;
int n, k, ans;
int a[30];
bool check(long long x) //判断素数
{if(x == 1) return false;if(x == 2 || x == 3) return true;for(int i = 2; i * i <= x; ++i) {if(x % i == 0)return false;}return true;
}
void dfs(int s, long long sum, int startx) //step步数, 总和sum, start判重
{ //startx作用是, 每次只能选它后面的数,而不能先选后面再选前面的//完成任务if(s == k) {if(check(sum)) {ans += 1;}return; //回溯}//遍历for(int i = startx; i < n; ++i)dfs(s + 1, sum + a[i], i + 1); //递归
}
int main()
{cin>>n>>k;for(int i = 0; i < n; ++i)cin>>a[i];dfs(0, 0, 0); //从第0个数字, 总和为0开始, 判重cout<<ans;return 0;
}

👊（三）P9011 [USACO23JAN] Air Cownditioning II B

P9011 [USACO23JAN] Air Cownditioning II B - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：DFS，差分，USACO

多点做结合2个甚至3个算法的综合题，选这道题是为了复习差分，真的忘光了

👂 猫咪日记 - 饼饼/袁嘉怡Bella - 单曲 - 网易云音乐

复习 → 前缀和 & 差分 - OI Wiki (oi-wiki.org)

为了巩固差分，我重新做了一次这2题（易 --> 难）

→ P2367 语文成绩 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

→ 3729. 改变数组元素 - AcWing题库

哈哈，又发现个问题，现在习惯性敲完代码 + 过了样例后，再测一组更全面的，结果往往忘了删掉中间（为了测试）增加的cout，导致本来能AC的，WA了。。蓝桥杯要注意这个问题

思路

1，对读入的温度要求，进行 +=k的差分

2，将读入的空调数据按结构体中，四个变量的形式输入

3，一个结构体，一个check判断是否满足降温条件，两个差分函数insert

当然，后来想想，没必要写两个，只需要在dfs递归时，在cold[i].p前加个负号 '-' 即可

关于check()函数中，为什么全部<=0即可，因为只要能抵消到<= 0的程度，就满足降温需求

🌳DFS + 二分  AC  100%

说实话，这么小的数据量没必要二分，但学习一下也好，

当两个甚至多个算法组合在一起，就会暴露出很多问题

#include<iostream>
using namespace std;
int n, m, ans = 1e9, e[110], vis[20]; //最大100栏, 10空调struct node{int a, b, p, m; //[a, b], 降温, 价格
};
struct node cold[20]; //空调//判断满足降温条件
bool check()
{ //还得前缀和一次int sum = 0;for(int i = 1; i <= 100; ++i) { //100个栏sum += e[i];if(sum > 0) return false;}return true;
}//[l, r] -k, 读入空调的差分
void insert1(int l, int r, int k)
{e[l] -= k;e[r + 1] += k;
}
//[l, r] +k, 初始要求的差分
void insert2(int l, int r, int k)
{e[l] += k;e[r + 1] -= k;
}void dfs(int money)
{if(check()) {ans = min(ans, money);return; //回溯}//遍历所有空调for(int i = 0; i < m; ++i) {if(vis[i] == 0) {insert1(cold[i].a, cold[i].b, cold[i].p); //-= kvis[i] = 1; //标记dfs(money + cold[i].m); //递归vis[i] = 0; //取消标记//手动还原差分数组insert2(cold[i].a, cold[i].b, cold[i].p); //+= k}}
}int main()
{cin>>n>>m;int xx, yy, zz;//输入温度要求for(int i = 0; i < n; ++i) {cin>>xx>>yy>>zz;insert2(xx, yy, zz); //+= k}//输入空调数据for(int i = 0; i < m; ++i)cin>>cold[i].a>>cold[i].b>>cold[i].p>>cold[i].m;dfs(0);cout<<ans;return 0;
}

最最关键的是代码第48行，需要我们手动还原差分，

否则经过多次dfs后，样例输入后，会输出2而不是10，

因为过程中的

差分数组e被多次改变而得不到还原

🌳暴力DFS  AC  82%

第一次AC  82%，让我想想有没有什么优化的点

答案是没有

为什么呢，因为出题人觉得暴力的做法，只配得82%得分数，而不是你解出了82%的正解

#include<iostream>
using namespace std;
int n, m, ans = 1e9, e[110], vis[20]; //最大100栏, 10空调struct node{int a, b, p, m; //[a, b], 降温, 价格
};
struct node cold[20]; //空调//判断满足降温条件
bool check()
{for(int i = 1; i <= 100; ++i) //100个栏if(e[i] > 0)return false;return true;
}void dfs(int money)
{if(check()) {ans = min(ans, money);return; //回溯}//遍历所有空调for(int i = 0; i < m; ++i) {if(vis[i] == 0) {for(int j = cold[i].a; j <= cold[i].b; ++j)e[j] -= cold[i].p; //暴力, 小心i, j混淆vis[i] = 1; //标记这个空调使用过dfs(money + cold[i].m); //递归vis[i] = 0; //取消标记//这里同样是要恢复数组e, 只不过这次是直接恢复,//上个代码是恢复差分数组for(int j = cold[i].a; j <= cold[i].b; ++j)e[j] += cold[i].p;}}
}int main()
{cin>>n>>m;int xx, yy, zz;//输入温度要求for(int i = 0; i < n; ++i) { //n头牛cin>>xx>>yy>>zz;for(int j = xx; j <= yy; ++j)e[j] = zz;}//输入空调数据for(int i = 0; i < m; ++i)cin>>cold[i].a>>cold[i].b>>cold[i].p>>cold[i].m;dfs(0);cout<<ans;return 0;
}

👊（四）1116: 组合的输出

 P1116 - 组合的输出 - New Online Judge (ecustacm.cn)

标签：递归，DFS，基础题

思路

1，DFS模板

2，dfs(int step, int startx)中，startx参数，保证升序排列，也就是按字典序

3，利用数组a保存每次的排列，for循环中 a[step] = i； step表示到了第step个数字

4，坑：原文是，每个字符占3个位置，这里提供两种解决方案

挣扎了20分钟，才摸索到2种解决方法

//1
#include<cstdio>
printf("%3d", a[i]);
//2
#include<iomanip>
cout<<setw(3)<<a[i];

而只是用cout<<"  "这种做法，就算你全部换行和空格都和题目一样，最多只能AC 50%

AC代码

#include<iostream>
#include<cstdio> //printf()
using namespace std;
int n, r, a[30]; //数组a保存当前排列
void dfs(int step, int startx) //startx保证升序排列, 防止重复
{if(step == r) {for(int i = 0; i < r; ++i) {//step从0开始, 所以这里也要从0开始printf("%3d", a[i]);}cout<<endl;return; //回溯}//遍历for(int i = startx; i <= n; ++i) {a[step] = i;dfs(step + 1, i + 1); //注意startx只在遍历的初始出现1次}
}
int main()
{cin>>n>>r;dfs(0, 1);return 0;
}

👊（五）1117: 素数环

P1117 - 素数环 - New Online Judge (ecustacm.cn)

标签：基础题，DFS

有个坑，但也补充了知识盲点

第一次敲了20分钟，提交，时间超限，AC 0%，，，我想，不会吧，难道是没剪枝？

可看了下，没找到  if  break的地方，后来才发现，输出大量数据时，printf()比cout更快

当然你也可以关同步，因为需要兼容cin与stdin，cout与stdout，所以cin, cout较之scanf()，printf()更慢

具体可以看(11条消息) cin,cout与scanf，printf的速度到底相差多少_printf比cout快多少_BlingBling520的博客-CSDN博客

因为这个原因，又折腾了20分钟才AC

AC  代码

#include<iostream>
using namespace std;
int n, now = 1, a[20], vis[20]; //数组a保存答案
//判断素数
bool check(int x)
{if(x == 1) return false;if(x == 2 || x == 3) return true;for(int i = 2; i * i <= x; ++i)if(x % i == 0)return false;return true;
}
void dfs(int step)
{if(step == n + 1 && check(a[1] + a[n])) { //首尾相加也是素数for(int i = 1; i <= n; ++i)printf("%d ", a[i]);printf("\n");return; //回溯}//遍历for(int i = 2; i <= n; ++i) {if(vis[i] == 0 && check(a[step - 1] + i)) {//相邻相加是素数a[step] = i;vis[i] = 1; //标记dfs(step + 1); //递归vis[i] = 0; //取消标记}}
}
int main()
{a[1] = 1;while(cin>>n) {printf("Case %d:\n", now++);dfs(2); //1已经确定, 所以从第2步开始printf("\n");}return 0;
}

👊（六）1118: 自然数的拆分

P1118 - 自然数的拆分 - New Online Judge (ecustacm.cn)

标签：DFS，基础题

与之前做的题又有点区分

思路

如果题目说的是，保证拆分的数字按字典序且不重复，则需要在for循环中加个startx参数，然后for(i = startx...)即可

但本题存在重复的数字，我们只需要对a数组进行一个判断

i >= a[step - 1]可以处理这一情况

if(sum + i <= n) {if(step == 0) {a[step] = i;dfs(step + 1, sum + i);}else if(step > 0 && i >= a[step - 1]) {a[step] = i;dfs(step + 1, sum + i);}}

AC  代码

#include<iostream>
using namespace std;
int n, a[30];
//大量输出记得printf()
void dfs(int step, int sum)
{if(sum == n) {printf("%d=", n);for(int i = 0; i < step; ++i) {printf("%d", a[i]);if(i < step - 1)printf("+");}printf("\n");return; //回溯}//遍历for(int i = 1; i < n; ++i)if(sum + i <= n) {if(step == 0) {a[step] = i;dfs(step + 1, sum + i);}else if(step > 0 && i >= a[step - 1]) {a[step] = i;dfs(step + 1, sum + i);}}
}
int main()
{while(cin>>n) {dfs(0, 0);printf("\n");}return 0;
}

🌼十四，拓扑排序（未更新）

👂  不露声色 - Jam - 单曲 - 网易云音乐

🌼十五，Dijkstra

👂 这个世界不会好 - 子默 - 单曲 - 网易云音乐

Dij和Floyd的题放一块

Floyd科普博客👇

(13条消息) 最短路之Floyd-Warshall（10张图解）_千帐灯无此声的博客-CSDN博客

👆

→ 最短路 - OI Wiki (oi-wiki.org)

→ Floyd 算法 - 简书 (jianshu.com)

先来看看Floyd模板，其他部分和Dij几乎一模一样，除了比Dij少了book[]数组和dis[]数组

只有5行，其他都是初始化 + 读入数据 + 输出答案 的活

//通过k中转, i 到 j 距离更短, 就更新
for(int k = 1; k <= n; ++k)for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)if(e[i][j] > e[i][k] + e[k][j])e[i][j] = e[i][k] + e[k][j];

🌼十七，Floyd

👂 我才不看你脸色！ - 蛙腩/AEolus阿一 - 单曲 - 网易云音乐

Dij和Floyd的题放一块

注意Dij不能做有负权边的最短路，因为它的推导过程是基于贪心的且所有边权都是正数的

dijkstra科普博客👇

(13条消息) 最短路之Dijkstra（15张图解）_迪杰斯特拉算法求最短路径图解_码龄?天的博客-CSDN博客

👆

→ 最短路 - OI Wiki (oi-wiki.org)

→ (17条消息) dijkstra算法详解—简单易懂_unique_pursuit的博客-CSDN博客

先来默写一下dijkstra模板（结合输入输出）

第一行输入n个顶点，m条边

后面m行输入 t1 号顶点到 t2 号顶点的距离 t3

最后一行输出 1 号顶点到 1~n 号顶点的最短路径

代码

#include<cstdio>
int main()
{int e[10][10], dis[10], book[10], i, j, n, m;int t1, t2, t3, u, v, Min;int inf = 1e8; //infinity(n.)无穷//读入n个顶点, m条边scanf("%d%d", &n, &m);//初始化for(i = 1; i <= n; ++i)for(j = 1; j <= n; ++j) {if(i == j) e[i][j] = 0;else e[i][j] = inf;}//读入边for(i = 1; i <= m; ++i) {scanf("%d%d%d", &t1, &t2, &t3);e[t1][t2] = t3;}//初始化dis数组, 表示源点1号到其他点初始路程for(i = 1; i <= n; ++i)dis[i] = e[1][i];//初始化book数组for(i = 1; i <= n; ++i)book[i] = 0;//Dijkstra算法核心//源点不用确定, 所以是n - 1次遍历for(i = 1; i <= n - 1; ++i) {Min = inf;for(j = 2; j <= n; ++j) { //从顶点2开始//找确定值（未确定中找最小值）if(book[j] == 0 && dis[j] < Min) {Min = dis[j];u = j;}}book[u] = 1; //顶点u已确定//从刚被确定的顶点出边for(v = 2; v <= n; ++v) //从顶点2开始if(e[u][v] < inf && dis[u] + e[u][v] < dis[v])//两点连通且可更新dis[v] = dis[u] +e[u][v];}for(int i = 1; i <= n; ++i)printf("%d ", dis[i]);return 0;
}

输入输出

6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
0 1 8 4 13 17

👊（一）1488. 最短距离（未完待续）

1488. 最短距离 - AcWing题库

标签：单源最短路，Dij，笔试题，简单

 输入输出放到代码段里

//输入
7 7
1 2 5
1 4 3
2 3 2
2 5 1
3 6 7
5 6 8
6 7 6
3
7
5
4
7
1
2
3
4
5
6
7
//输出
3
1
3
0
0
6
0

注意关键字：

1，无向；2，M，K，Q最大都达10^5，必须用scanf() + printf()

虽说标签是单源最短路，但题目乍一看上去，不就是多源最短路吗？

常规的多源是，求任意两个点之间的最短路，

而本题应该算单源最短路的变式，求的是多个源点（商店）到其他村庄的最短路

由于有K个商店，也就是求K次单源最短路

如果直接朴素Dij，进行K次单源最短路的求解，复杂度最大就接近O(n^3)了，会TLE

方法

建个虚拟源点，不要觉得它很神秘，实际上就是，本来不是1~n个顶点（村庄）嘛

现在多设一个0号村庄，它到所有商店的距离都设置为0即可，就多了这一行代码

就将K次单源最短路转化为普遍意义上的单源最短路

坑

由于不喜欢背模板，我喜欢的是《啊哈算法》那种，先模拟一遍整个过程，每一行代码都按自己的理解写出清楚的注释，也就不需要背模板了

本题顶点数量达10^5，所以如果用二维数组存储图，e[100010][100010]即使声明为全局变量，也会报错 error: size of array e is too large（只能背邻接表模板了）

补充个知识点：二维数组e声明为全局变量，int的话最大约e[5050][5050]，再大就会报错

不会邻接表实现Dij或者vector存图+堆优化的小伙伴，蓝桥杯只能这样骗30%的分了

邻接表模板

//邻接表(头插法)
int h[N], e[M], w[M], ne[M], idx; 
void add(int a, int b, int c) 
{ //读入a到b的距离ce[idx] = b, w[idx]= c, ne[idx] = h[a], h[a] = idx++;
}

然而，Dij里也要对应修改，或者堆优化，然后由于我不知道邻接表的模拟过程是怎样的

所以最终还是放弃这题吧，等蓝桥杯结束了，或者暑假有时间再来学邻接表和堆优化

👇这个就是vector存图的Dij堆优化👇

Ubuntu Pastebin

👆是除了邻接表存图外的另一种方式👆（有时间再来学把）

👊（二）P2935 [USACO09JAN]Best Spot S

P2935 [USACO09JAN]Best Spot S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：枚举，最短路，USACO

 标签说的很对，就是最短路的枚举

注意关键字：1，双向(无向图多敲一行代码)；2，最佳牧场(所以别输出成最小的平均距离)

如果采用Floyd，直接每两个点之间的最短路即可，然后对平均值判断，O(n^3) = 1.25 * 10^8还好

如果采用Dij则需要分别对最喜欢的F个牧场Dij一次，也就是F次Dij，F * O(n^2)快一点点

都是暴力/朴素最短路能做的，毕竟只有500个点，二维数组也是能开的

🌳Dijstra  AC

额外的测试

//自己编的输入
5 2 6
3 5
1 5 4
1 4 6
2 4 8
2 5 11
3 4 10
4 5 12
//加上cout观察过程是否正确
20 1
29 2
20 3
20 4
20 5
//结果
1

样例以及额外的测试都正确，可以提交了

模板基础上加了点东西，有几个卡点

1，代码第17行一开始敲错了，，，

2，第27，28行一开始漏敲，思路被模板限制住了

3，第53行进行K次Dij，一开始没有写Dij函数，全部在主函数里操作，弄的很乱

虽然是一次AC，但还是费了一个半小时（敲代码半小时，debug一小时），如果比赛时Dij不熟练，数据量像这题一样那么小

500^3还是在1e8复杂度左右，不要犹豫，直接Floyd（5行核心代码，很好实现的） 

AC  代码

#include<iostream>
#include<cstring> //memset()
using namespace std;
int e[510][510], book[510], farm[510], dis[510];
int n, F, m, t1, t2, t3, u, inf = 1e9;
void Dijstra(int love) //love号牧场的单源最短路
{book[love] = 1; //love点到自己已经确定//初始化dis数组for(int i = 1; i <= n; ++i)dis[i] = e[love][i];//Dij核心for(int i = 1; i <= n - 1; ++i) { //n - 1次遍历//找确定点int Min = inf;for(int j = 1;  j <= n; ++j)if(book[j] == 0 && dis[j] < Min) { //注意这里是dis[j] < MinMin = dis[j];u = j;}book[u] = 1; //u号点已确定//从确定点出边for(int k = 1; k <= n; ++k)//通过u中转更近if(book[k] == 0 && dis[k] > dis[u] + e[u][k]) {dis[k] = dis[u] + e[u][k]; //更新e[k][love] = dis[k]; //二维数组也更新e[love][k] = dis[k]; //双向}}
}
int main()
{cin>>n>>F>>m; //n个牧场, F个喜欢, m条双向路//初始化数组efor(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j) {if(i == j) e[i][j] = 0; //自己到自己距离0else e[i][j] = inf; //无穷infinity}//读入喜欢的牧场for(int i = 0; i < F; ++i)cin>>farm[i];//读入边for(int i = 0; i < m; ++i) {cin>>t1>>t2>>t3;e[t1][t2] = t3; //t1到t2距离为t3e[t2][t1] = t3; //双向}//F次Dijfor(int i = 0; i < F; ++i) {memset(book, 0, sizeof(book)); //恢复标记数组Dijstra(farm[i]);}//找最佳牧场int ans, ans_sum = inf, sum;for(int i = 1; i <= n; ++i) {sum = 0;for(int j = 0; j < F; ++j)sum += e[farm[j]][i]; //心爱农场到i号农场的距离if(sum < ans_sum) {ans_sum = sum;ans = i;}}cout<<ans;return 0;
}

🌳Floyd  AC 

哈哈，Floyd直接在Dij代码基础上，删掉一半，再补充5行核心代码完活

耗时3分钟（26~30即5行核心代码，其他Dij粘贴过来）

#include<iostream>
#include<cstring> //memset()
using namespace std;
int e[510][510], farm[510];
int n, F, m, t1, t2, t3, u, inf = 1e9;
int main()
{cin>>n>>F>>m; //n个牧场, F个喜欢, m条双向路//初始化数组efor(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j) {if(i == j) e[i][j] = 0; //自己到自己距离0else e[i][j] = inf; //无穷infinity}//读入喜欢的牧场for(int i = 0; i < F; ++i)cin>>farm[i];//读入边for(int i = 0; i < m; ++i) {cin>>t1>>t2>>t3;e[t1][t2] = t3; //t1到t2距离为t3e[t2][t1] = t3; //双向}//Floyd核心//通过k中转, i 到 j 距离更短, 就更新for(int k = 1; k <= n; ++k)for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)if(e[i][j] > e[i][k] + e[k][j])e[i][j] = e[i][k] + e[k][j];//找最佳牧场int ans, ans_sum = inf, sum;for(int i = 1; i <= n; ++i) {sum = 0;for(int j = 0; j < F; ++j)sum += e[farm[j]][i]; //心爱农场到i号农场的距离if(sum < ans_sum) {ans_sum = sum;ans = i;}}cout<<ans;return 0;
}

👊（三）P1119 灾后重建

P1119 灾后重建 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：图论，枚举，最短路，普及+/提高

这道题，考了Floyd的原理：

从 i号 顶点到 j号 顶点，只经过前 k号 点的最短路程（一种动态规划思想 

很棒的练手题目

思路

1，写一个Floyd函数int Floyd(int x)，意思是通过k号顶点中转

2，将重建完成时间读入一维数组tim[]

3，初始化二维数组e[][]，并读入边

4，剩下q次询问就好

注意

1，顶点从0号开始，不是1号

2，两个点需要双向边，一个是Floyd更新数组e时，一个是主函数中读入边时

3，我们在q次询问前，增加一个变量now = 0，表示重建到了第now个村庄，应该注意的是，now要放q次询问的循环外，否则就像我一开始一样，每次询问都从第0个村庄开始重建，于是TLE了60%的样例

AC  代码

#include<cstdio> //scanf(), printf()
int e[210][210], tim[210];
int n, m, q, t1, t2, t3, inf = 1e9;
//经过第x号点中转
int Floyd(int x)
{for(int i = 0; i < n; ++i)for(int j = 0; j < n; ++j)if(e[i][j] > e[i][x] + e[x][j]) {e[i][j] = e[i][x] + e[x][j];e[j][i] = e[i][x] + e[x][j]; //双向Floyd也要更新}
}
int main()
{scanf("%d%d", &n, &m);//第i个村庄重建完成时间for(int i = 0; i < n; ++i)scanf("%d", &tim[i]);//初始化二维数组efor(int i = 0; i < n; ++i)for(int j = 0; j < n; ++j) {if(i == j) e[i][j] = 0;else e[i][j] = inf;}//读入边for(int i = 0; i < m; ++i) {scanf("%d%d%d", &t1, &t2, &t3);e[t1][t2] = t3; //t1到t2的距离t3e[t2][t1] = t3; //双向}scanf("%d", &q);//q次询问int now = 0; //这个得放外面, 否则每次都从第0个开始重新Floydwhile(q--) {scanf("%d%d%d", &t1, &t2, &t3);//关键: 第now个村庄建成时间小于给定时间while(tim[now] <= t3 && now < n) //now < n一开始漏了Floyd(now++); //否则你可以通过后续不存在的距离为0的道路中转//不可到达 || t1未建成 || t2未建成if(e[t1][t2] == inf || tim[t1] > t3 || tim[t2] > t3) {printf("-1\n");continue; //跳出本次循环}printf("%d\n", e[t1][t2]);}return 0;
}

🌼十六，SPFA（未更新）

👂 世间美好与你环环相扣 - 柏松 - 单曲 - 网易云音乐

🌼十八，最小生成树（未更新）

👂 声声慢 - 崔开潮 - 单曲 - 网易云音乐

🌼十九，最近公共祖先（未更新）

👂 渡渡年 - 要不要买菜 - 单曲 - 网易云音乐

🌼二十，二分图（未更新）

👂 風になる（幻化成风） - つじあやの - 单曲 - 网易云音乐

🍋总结 

大一参加蓝桥杯注定无法取得好成绩，因为数据结构是大二上才学，先不谈数据结构，单就算法来说，大一能掌握一半的基础算法都不错了，只是一半的基础算法，最多也就C++A组省二

1，对拍，找bug很棒的方法

2，s.find(), s.substr() 

#include<cstring> //s.substr(), s.find()string s1 = s.substr(j, i); //下标j开始, 截取i个字符
if(s.find(s1, j + 1) == string::npos)
//没有找到子串, 返回string::nposif(s.find(s1, j + 1) != string::npos)
//找到子串

3，map的迭代器

#include<iostream>
#include<map>
using namespace std;
map<int, int>m;
for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it) //迭代器printf("%d ", it->second);

4，蓝桥杯技巧

不论是比赛还是平时，OI赛制都要懂得自己设计样例来测试代码，不要只是过了样例就提交

也许有些简单的错误是样例测试不出来的

样例过了后，再想2~5组数据，都过了再提交，没过就好好检查下为什么信心满满的代码不行，总能揪出错误

5，O2优化

洛谷或者AcW里少数的题会卡O2，起到常数优化的效果

代码第一行加上：#pragma GCC optimize(2)

#pragma GCC optimize(2)

蓝桥杯是可以用的

6，数组超限

是个大坑，比如201 * 201的二维平面，你得开到40401以上，而不是40001以上，因为 201 * 201 = 40401，心算不好就拿🖊算，要么就多开个几千

7，测试后忘删cout

不论OI还是IOI，ACM赛制，写完代码过了样例后，利用cout再测多一组数据，并观察过程是否正确，都是好习惯

然而，你经常忘了删cout，导致AC  100%变成了AC  0%，要注意

8，关于scanf()和printf()

大量输入时，用scanf()，不用cin

大量输出时，用printf()，不用cout

9，关于stl

参加蓝桥杯，天梯赛等比赛，它们是支持C++11的，一定要学stl，不会stl是硬伤，现在所有的二分还是别的算法，我都是现场手写的，虽说对打基础 / 以后的面试题，有帮助

但是比赛谁给你那么多时间？所以我很多比赛有些会的题，就没时间看了

一是熟练度不够，二是没学过stl

目前stl接触过的只有sort()，#include<queue>和<stack>最基础的两三个操作，其他完全没见过

等23年蓝桥杯结束应该好好学学stl，外加对应题目的练习

30个题型+代码(冲刺2023蓝桥杯)(中)

2023.3.13~8.13持续更新

AcW需要付费的题，可以考虑上洛谷，New Oj找替代，或者花点钱

目录

🍎注意

🌼前言

🌼十，KMP（留坑）

🌼十一，Trie（留坑）

🌼十二，BFS

👊(一)1562. 微博转发

🌳AC  BFS暴力 + queue + stack(未完成)

🌳AC  Floyd-Warshall暴力

👊（二）机器人的运动范围

🌳BFS  AC  40%

🌳BFS  AC  75%

🌳BFS  AC  100%

🌳DFS  AC  100%

👊（三）188. 武士风度的牛

👊（四）P1451 求细胞数量

🌳暴力BFS

🌳暴力DFS

👊（五）1810: [NewOJ Week 4] 超级骑士

🌳广搜  AC

🌳深搜  AC

🌼十三，DFS

👊（一）3502. 不同路径数

🌳Wrong Answer

🌳Accepted

👊（二）P1036 [NOIP2002 普及组] 选数

👊（三）P9011 [USACO23JAN] Air Cownditioning II B

🌳DFS + 二分  AC  100%

🌳暴力DFS  AC  82%

👊（四）1116: 组合的输出

👊（五）1117: 素数环

👊（六）1118: 自然数的拆分

🌼十四，拓扑排序（未更新）

🌼十五，Dijkstra

🌼十七，Floyd

👊（一）1488. 最短距离（未完待续）

👊（二）P2935 [USACO09JAN]Best Spot S

🌳Dijstra  AC

🌳Floyd  AC 

👊（三）P1119 灾后重建

🌼十六，SPFA（未更新）

🌼十八，最小生成树（未更新）

🌼十九，最近公共祖先（未更新）

🌼二十，二分图（未更新）

🍋总结 

🍎注意

本篇博客写了4个题型就31063字了，所以，剩下的我决定再写第四个博客

每10个题型写一个博客，分为上中下三个博客，12万字收尾

后续再补充剩下两个博客地址

(上)(1条消息) 30个题型+代码(冲刺2023蓝桥杯)(上)_码龄?天的博客-CSDN博客

(下)(2条消息) 30个题型+代码(冲刺2023蓝桥杯)(下)_千帐灯无此声的博客-CSDN博客

🌼前言

前缀和√，差分√，二分√，双指针√，递归√，递推√，BFS√，DFS√，Dijkstra√, Floyd√，质数筛，最大公约数，背包dp，线性dp，区间dp，组合计数，快速幂，哈希√，并查集√，博弈论 

每个类型第一题来自AcWing蓝桥杯集训-每日一题

1，花5块钱

2，上洛谷找替代 / 原题 

题型有

前缀和，差分，二分，双指针，递推，递归，并查集，哈希，单调队列，
KMP，Trie，BFS，DFS，拓扑排序，Dijkstra，Floyd，最小生成树，
最近公共祖先，二分图，筛质数，最大公约数，快速幂，组合计数，博弈论，
背包DP，线性DP，区间DP，树型DP，树状数组，线段树，矩阵乘法 

如果你想冲省一，拿22年A组为例，你得拿60分，也就是2道填空题 + 4道编程题

5 + 5 + 10 + 10 + 15 + 15

省赛需要掌握的有：

前缀和，差分，二分，双指针，递归，递推，BFS，DFS，Dijkstra, Floyd，质数筛，最大公约数，背包dp，线性dp，区间dp，组合计数，快速幂，哈希，并查集，博弈论

围绕省赛需要掌握的类型，针对性地下手

先给大家看个时间复杂度（来源于AcWing）

🌼十，KMP（留坑）

👂 Secret Base (吉他版)（未闻花名(绝美指弹吉他)） - uBio高尾和树 - 单曲 - 网易云音乐 

→ KMP算法笔记 - AcWing

→ KMP 算法详解 - AcWing

→ 字符串匹配 - OI Wiki (oi-wiki.org)

→ 前缀函数与 KMP 算法 - OI Wiki (oi-wiki.org)

→ KMP算法详解-彻底清楚了(转载+部分原创) - sofu6 - 博客园 (cnblogs.com)

→ KMP算法详解_小轩爱学习的博客-CSDN博客

→ KMP 算法详解 - 知乎 (zhihu.com)

→ 数据结构KMP算法配图详解（超详细）_kmp算法图解_哈顿之光的博客-CSDN博客

🌼十一，Trie（留坑）

👂 想去海边 - 夏日入侵企画 - 单曲 - 网易云音乐

🌼十二，BFS

👂 逝年 - 夏小虎 - 单曲 - 网易云音乐

👇BFS科普博客

→ 《啊哈算法第四章之bfs》（17张图解）_码龄?天的博客-CSDN博客

先将科普博客敲一遍

就是将迷宫按二维数组输入，0表示空地，1表示障碍物，输出起点到终点的步数

由于是一步一步扩展的，这个步数就是最短路

⚠ 只有边权为1，才能用用BFS求最短路

//迷宫2维数组里, 1障碍, 0未走过的空地, -1走过的空地
#include<cstdio> //scanf(), printf()
int a[51][51];
struct note
{int x, y, s; //横坐标,纵坐标,步数
};
int main()
{struct note que[2501]; //声明队列为结构体int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组int n, m; //n行m列scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)scanf("%d", &a[i][j]);int startx, starty, p, q; //起点终点坐标scanf("%d%d%d%d", &startx, &starty, &p, &q);//队列初始化int head = 1, tail = 1;//往队列插入迷宫入口坐标que[tail].x = startx;que[tail].y = starty;que[tail].s = 0; //入口步数为0tail++;a[startx][starty] = -1; //标记走过int flag = 0; //标记是否到达终点//当队列不为空int tx, ty; //临时变量while(head < tail) {//枚举四个方向for(int i = 0; i < 4; ++i) {tx = que[head].x + next[i][0];ty = que[head].y + next[i][1];//判断越界if(tx < 1 || ty < 1 || tx > n || ty > m)continue;//判断不为障碍且未走过if(a[tx][ty] == 0) {//bfs每个点只入队一次a[tx][ty] = -1;//新的点入队que[tail].x = tx;que[tail].y = ty;que[tail].s = que[head].s + 1; //上一步再+1tail++; //放最后}//到达终点if(tx == p && ty == q) {flag = 1;break;}}if(flag) break;head++; //继续后续点的扩展}//tail指向队尾下一位, 要-1printf("%d", que[tail - 1].s);return 0;
}

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3
7

👇看动图 

→ 图文详解 DFS 算法 和 BFS 算法 - 墨天轮 (modb.pro)

→ 熬夜怒肝，图解算法！BFS和DFS的直观解释_Jack-Cui的博客-CSDN博客

👇bfs适用场景

→ 什么时候用DFS，什么时候用BFS? - 菜鸟龙* - 博客园 (cnblogs.com)

→ (1条消息) DFS和BFS应用场景（什么时候用）_bfs与dfs应用场景_binddddd的博客-CSDN博客

👊(一)1562. 微博转发

1562. 微博转发 - AcWing题库

标签：图论，BFS，中等，PAT甲级

思路

由样例可知，求最大转发量，就是求L层以内，关注这个用户的人数（不包括用户自己）

所以是有向图的多源最短路

嗯。。我不会邻接表，邻接矩阵和堆优化，所以只能暴力了，所幸这题数据量不大，暴力似乎也能过

🌳AC  BFS暴力 + queue + stack(未完成)

对每个点BFS一次

⚠ 只有边权为1，才能用用BFS求最短路

1，每个点要记录当前层数

2，同时用 st 数组判断是否访问过，防止重复入队

但是暴力bfs结合queue和stack，以减少代码量

bla...
//水一下，不会用Bfs做，先空着

🌳AC  Floyd-Warshall暴力

1，用一个二维数组存储图

2，Floyd，O(n^3)时间复杂度--暴力

3，最后要开O2优化

👇floyd科普博客（核心代码只有5行）

→ 最短路之Floyd-Warshall（10张图解）_码龄?天的博客-CSDN博客

再默写一遍floyd

#include<cstdio>
int e[10][10], k,i,j,n,m, t1,t2,t3, inf = 1e9;
int main()
{scanf("%d%d", &n, &m);//初始化地图for(i = 1; i <= n; ++i)for(j = 1; j <= n; ++j)if(i != j)e[i][j] = inf;//读入边for(i = 0; i < m; ++i) {scanf("%d%d%d", &t1, &t2, &t3);e[t1][t2] = t3;}//Floyd核心代码5行for(k = 1; k <= n; ++k)for(i = 1; i <= n; ++i)for(j = 1; j <= n; ++j)if(e[i][j] > e[i][k] + e[k][j])e[i][j] = e[i][k] + e[k][j];//打印i到j的最短路for(i = 1; i <= n; ++i) {for(j = 1; j <= n; ++j)printf("   %d", e[i][j]);printf("\n");}return 0;
}

注意AC代码有个小坑，因为输入的第i组数据，表示i所关注的几个人，所以

代码第34行是 e[j][i] <= L，而不是 e[i][j] <= L

样例过了，再编一组测试

8 2
3 3 4 7
3 4 8 1
1 6
1 5
2 6 4
0
0
2 3 4
8 1 2 3 4 5 6 7 8
1
0
3
4
4
5
2
1

说下AC之前的2次错误吧

1，Segmentation Fault，内存超限，e[10][10] --> e[1010][1010]

2，Time Limit Exceeded，时间超限，可我寻思别人也能Floyd过，我咋不行

因为第一行没加#pragma GCC optimize(2)

这个是什么呢，类似洛谷的O2优化，而且蓝桥杯是支持的

它的好处是常数优化，卡极限AC，当然也有坏处

据说PAT不开O2优化能过，但是AcW不开就time limit

AC  代码

#pragma GCC optimize(2)
#include<cstdio>
int e[1010][1010], k,i,j,n,q, t1, inf = 1e9;
int main() //询问q次
{int L;scanf("%d%d", &n, &L);//初始化图for(i = 1; i <= n; ++i)for(j = 1; j <= n; ++j)if(i != j)e[i][j] = inf; //infinity无穷//读入边for(i = 1; i <= n; ++i) { //读入n次关注的人scanf("%d", &j); //关注j个人while(j) {j--;scanf("%d", &t1);e[i][t1] = 1; //顶点i到顶点t1距离为1}}//Floyd核心代码for(k = 1; k <= n; ++k)for(i = 1; i <= n; ++i)for(j = 1; j <= n; ++j)if(e[i][j] > e[i][k] + e[k][j])e[i][j] = e[i][k] + e[k][j];//q次询问scanf("%d", &q);while(q) {q--;int ans = 0;scanf("%d", &i);for(int j = 1; j <= n; ++j)if(i != j && e[j][i] <= L) //注意是j指向ians += 1;printf("%d\n", ans);}return 0;
}

所以说，Floyd的O(n^3)做这种数据量的题，也是有点勉强的，但放在蓝桥杯，数据量不太大的情况，足以骗到80%的分 

👊（二）机器人的运动范围

24. 机器人的运动范围 - AcWing题库

标签：BFS，DFS，简单，剑指offer

我一开始想，谁这么傻，不是两层暴力就出来了吗

🌳BFS  AC  40%

class Solution {
public:int get_num(int x, int y){int s = 0;while(x) {s += x % 10;x /= 10;}while(y) {s += y % 10;y /= 10;}return s;}int movingCount(int threshold, int rows, int cols){int ans = 0;for(int i = 0; i < rows; ++i)for(int j = 0; j < cols; ++j) {int now = get_num(i, j);if(now <= threshold)ans += 1;}return ans;}
};

但我忽略了现实条件，有个真实不虚的机器人在移动，它是不可以飞的，而由于判断小于k的要求是，每一位相加判断（而不是两数相加），所以存在get_num(i, j) <= k但机器人无法到达的情况

所以还是得用BFS

🌳BFS  AC  75%

class Solution {
public:int getnum(int x, int y){int s = 0;while(x) {s += x % 10;x /= 10;}while(y) {s += y % 10;y /= 10;}return s;}struct node{int x, y, s; //横坐标,纵坐标,路程};int movingCount(int k, int rows, int cols){int book[51][51] = {0};struct node q[2510]; //队列扩展大于50*50即可//初始化队列int head = 0, tail = 0;q[tail].x = 0;q[tail].y = 0;q[tail].s = 1;tail++;book[0][0] = 1; //标记起点走过int tx, ty; //临时变量int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组//当队列不为空while(head < tail) {for(int i = 0; i < 4; ++i) {tx = q[head].x + next[i][0];ty = q[head].y + next[i][1];//判断边界if(tx < 0 || ty < 0 || tx >= rows || ty >= cols)continue;//未到达过//此处if是所有bfs区别的地方if(book[tx][ty] == 0 && getnum(tx, ty) <= k) {book[tx][ty] = 1;q[tail].x = tx;q[tail].y = ty;q[tail].s = q[tail - 1].s + 1; //路程+1tail++; //放最后}}head++; //继续其他点的扩展}return q[tail - 1].s; //tail指向队尾下一位, 要-1}
};

有个坑，如果行或列任一为0，说明方格不存在，只能输出0，最后需要分类讨论

🌳BFS  AC  100%

AcW代码

class Solution {
public:int getnum(int x, int y){int s = 0;while(x) {s += x % 10;x /= 10;}while(y) {s += y % 10;y /= 10;}return s;}struct node{int x, y, s; //横坐标,纵坐标,路程};int movingCount(int k, int rows, int cols){int book[51][51] = {0};struct node q[2510]; //队列扩展大于50*50即可//初始化队列int head = 0, tail = 0;q[tail].x = 0;q[tail].y = 0;q[tail].s = 1;tail++;book[0][0] = 1; //标记起点走过int tx, ty; //临时变量int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组//当队列不为空while(head < tail) {for(int i = 0; i < 4; ++i) {tx = q[head].x + next[i][0];ty = q[head].y + next[i][1];//判断边界if(tx < 0 || ty < 0 || tx >= rows || ty >= cols)continue;//未到达过//此处if是所有bfs区别的地方if(book[tx][ty] == 0 && getnum(tx, ty) <= k) {book[tx][ty] = 1;q[tail].x = tx;q[tail].y = ty;q[tail].s = q[tail - 1].s + 1; //路程+1tail++; //放最后}}head++; //继续其他点的扩展}if(rows == 0 || cols == 0)return 0;elsereturn q[tail - 1].s; //tail指向队尾下一位, 要-1}
};

本地编译器代码

#include<iostream>
using namespace std;
int book[51][51];
struct node
{int x, y, s; //横坐标,纵坐标,路程
};
int getnum(int x, int y)
{int s = 0;while(x) {s += x % 10;x /= 10;}while(y) {s += y % 10;y /= 10;}return s;
}
int main()
{struct node q[2510]; //队列扩展大于50*50即可int k, rows, cols;cin>>k>>rows>>cols;//初始化队列int head = 0, tail = 0;q[tail].x = 0;q[tail].y = 0;q[tail].s = 1;tail++;book[0][0] = 1; //标记起点走过int tx, ty; //临时变量int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组//当队列不为空while(head < tail) {for(int i = 0; i < 4; ++i) {tx = q[head].x + next[i][0];ty = q[head].y + next[i][1];//判断边界if(tx < 0 || ty < 0 || tx >= rows || ty >= cols)continue;//未到达过//此处if是所有bfs区别的地方if(book[tx][ty] == 0 && getnum(tx, ty) <= k) {book[tx][ty] = 1;q[tail].x = tx;q[tail].y = ty;q[tail].s = q[tail - 1].s + 1; //路程+1tail++; //放最后}}head++; //继续其他点的扩展}if(rows == 0 || cols == 0)cout<<0;elsecout<<q[tail - 1].s; //tail指向队尾下一位, 要-1return 0;
}

🌳DFS  AC  100%

貌似剑指offer还是可以声明全局变量，力扣不可以

尽管可以声明，给来的movingCount依旧是核心代码模式，所以

我给dfs函数整了5个参数

当然，据说可以

1，直接int dfs()，在函数里操作

2，通过取地址符传参

AcW代码

没有办法，只能给dfs整5个参数，取地址符不会用，dfs函数里直接操作也不会

class Solution {
public:
int book[51][51], vis[51][51], ans = 0;
int tx, ty;int getnum(int x, int y){int s = 0;while(x) {s += x % 10;x /= 10;}while(y) {s += y % 10;y /= 10;}return s;}void dfs(int x, int y, int k, int rows, int cols){int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//枚举4个方向for(int i = 0; i < 4; ++i) {//下一点坐标tx = x + next[i][0];ty = y + next[i][1];//超出范围if(tx < 0 || ty < 0 || tx >= rows || ty >= cols)continue;//没访问过且小于kif(book[tx][ty] == 0 && getnum(tx, ty) <= k) {book[tx][ty] = 1; //标记dfs(tx, ty, k, rows, cols); //递归book[tx][ty] = 0; //取消标记}}//切记, ans += 1的if判断放外面if(vis[x][y] == 0) {ans += 1;vis[x][y] = 1;}}int movingCount(int k, int rows, int cols){book[0][0] = 1;dfs(0, 0, k, rows, cols);if(rows == 0 || cols == 0)return 0;elsereturn ans;}
};

本地编译代码

#include<iostream>
using namespace std;
int book[51][51], vis[51][51], ans = 0;
int k, rows, cols, tx, ty;
int getnum(int x, int y)
{int s = 0;while(x) {s += x % 10;x /= 10;}while(y) {s += y % 10;y /= 10;}return s;
}
void dfs(int x, int y)
{int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//枚举4个方向for(int i = 0; i < 4; ++i) {//下一点坐标tx = x + next[i][0];ty = y + next[i][1];//超出范围if(tx < 0 || ty < 0 || tx >= rows || ty >= cols)continue;//没访问过且小于kif(book[tx][ty] == 0 && getnum(tx, ty) <= k) {book[tx][ty] = 1; //标记dfs(tx, ty); //递归book[tx][ty] = 0; //取消标记}}//切记, ans += 1的if判断放外面if(vis[x][y] == 0) {ans += 1;vis[x][y] = 1;}
}
int main()
{cin>>k>>rows>>cols;book[0][0] = 1;dfs(0, 0);if(rows == 0 || cols == 0)cout<<0;elsecout<<ans;return 0;
}

-- -- --梳理-- -- --

bfs核心是扩展，dfs核心是递归

相同点

1，方向数组next[4][2]        2,getnum()按题意写（当然有时不需要getnum）

区别

bfs构造完getnum()后，直接进入主函数，通过队列和开头的while(head < tail)得到答案

dfs构造完getnum()后，还要构造dfs()，这才进入主函数，然后调用函数得到答案 

bfs的主体是在主函数里通过队列实现的(也可放函数外)，dfs主体在主函数外通过递归实现 

其实很多迷宫题，都需要getnum()这个函数，当然实现会有点区别

👊（三）188. 武士风度的牛

188. 武士风度的牛 - AcWing题库

标签：搜索，BFS，简单

BFS模板，因为不熟悉，我写了50分钟才写出来，然后样例没对。。

找了20分钟，没找到哪里错了，后来别人说，方向数组错了

一开始写成

int next[8][2] = {{1,0},{-1,0},{2,0},{-2,0},{0,1},{0,-1},{0,2},{0,-2}};
...
...
int dd = abs(next[i][0]) - abs(next[i][1]);//超出范围或不符合马走势if(tx < 0 || ty < 0 || tx >= r || ty >= c || dd == 0)continue;

但是dd == 0，并不能保证按马的走，会出现很多(2, 0)，(-2, 0)，(0, 2)，(0, 1)这种玩意

明明之前用过类似的，比如

int next[4][2] = {{-1, 0}, //上{1, 0},  //下{0, -1}, //左{0, 1}}; //右

但这个是迷宫中，每次走一步，结果这次只是换了点东西就错了

思维定势太严重，，，还得多接触下不同的题，培养思考习惯，而不是套模板习惯

方向数组改成这个后

int next[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};

我又编了一组测试

6 5
.....
K....
.....
..*..
.....
.*.H.
3

然后提交，AC了

AC  代码

#include<iostream>
#include<cmath> //abs()
using namespace std;
char a[151][151];
int startx, starty, p, q, tx, ty, flag = 0; //p,q 终点坐标
struct node
{int x, y, s; //横坐标,纵坐标,步数
};
int main()
{//方向数组struct node que[22510];int next[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};int c, r; //c列r行cin>>c>>r;//读入地图//记得是从0开始, 后续都受这个影响for(int i = 0; i < r; ++i)for(int j = 0; j < c; ++j) {cin>>a[i][j];if(a[i][j] == 'K')startx = i, starty = j; //起点if(a[i][j] == 'H')p = i, q = j; //终点}//队列初始化int head = 0, tail = 0;que[tail].x = startx;que[tail].y = starty;que[tail].s = 0;tail++;a[startx][starty] = '*'; //标记走过//当队列不为空while(head < tail) {//枚举四个方向for(int i = 0; i < 8; ++i) {tx = que[head].x + next[i][0];ty = que[head].y + next[i][1];int dd = abs(next[i][0]) - abs(next[i][1]);//超出范围或不符合马走势if(tx < 0 || ty < 0 || tx >= r || ty >= c || dd == 0)continue;//不为障碍且没走过if(a[tx][ty] == '.') {//bfs每个点只入队一次a[tx][ty] = '*'; //标记走过que[tail].x = tx;que[tail].y = ty;que[tail].s = que[head].s + 1;tail++;}if(tx == p && ty == q) {flag = 1;break;}}if(flag) break;head++; //继续后续队列扩展}cout<<que[tail - 1].s; //tail指向队尾下一位, 要-1return 0;
}

👊（四）P1451 求细胞数量

P1451 求细胞数量 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：搜索，BFS，DFS，普及-

一开始看到分成几块，第一时间以为可以用并查集，想了大半小时没结果，因为一个元素分横纵坐标两个变量，可以考虑用结构体，但比BFS难实现多了

所以没有最好的算法，只有最合适的算法

🌳暴力BFS

基础思路：写个bfs函数，访问过的点标记好

主函数中两层for循环遍历每个点直到所有非0点都遍历过

最后输出细胞数

这里不用book数组，我们直接在存储地图的二维数组a上直接操作，访问过的点赋值为0即可

还要注意下输入问题，可以按我的，转整型再放进二维数组

也可以直接按char[][]输入，直接对字符判断

哪个熟练用哪个

额外的测试

5 7
1024540
0314350
1230123
1213010
1230230
2

AC  代码

#include<iostream>
using namespace std; //string s;
int a[110][110], ans = 0, n, m, tx, ty;
struct node
{int x, y; //横坐标, 纵坐标, 编号
};
struct node que[10010]; //100*100
void bfs(int x, int y)
{int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组//初始化队列int head = 0, tail = 0;que[tail].x = x;que[tail].y = y;tail++;a[x][y] = 0; //标记//队列不为空while(head < tail) {//枚举4个方向for(int i = 0; i < 4; ++i) {tx = que[head].x + next[i][0];ty = que[head].y + next[i][1];//超出范围或不为细胞if(tx < 0 || ty < 0 || tx >= n || ty > m || a[tx][ty] == 0)continue;a[tx][ty] = 0; //标记que[tail].x = tx;que[tail].y = ty;tail++;}head++; //继续后续点的扩展}
}
int main()
{cin>>n>>m;string s[n];//按字符串读入for(int i = 0; i < n; ++i)cin>>s[i];//2维数组建表for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j) {a[i][j] = s[i][j] - '0'; //字符转10进制整数}//对所有点BFSfor(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j) {if(a[i][j] != 0) {bfs(i, j);ans += 1;}}cout<<ans;return 0;
}

🌳暴力DFS

由于代码第15行，我不确定是否要按模板常规的取消标记（标记，递归，取消标记的套路）

所以，第一次保留了取消标记，输出错误

第二次，去掉了取消标记，输出正确，但是不放心，就又试了一次

额外的测试

4 5
11110
11101
11001
01010
3

居然对了，忘了dfs遇到死胡同，会自动递归回上一步，直到有通路的全部点访问完

AC  代码

#include<iostream>
using namespace std; //string s;
int a[110][110], ans = 0, n, m, tx, ty;
void dfs(int x, int y)
{a[x][y] = 0; //标记int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组for(int i = 0; i < 4; ++i) {tx = x + next[i][0];ty = y + next[i][1];if(tx < 0 || ty < 0 || tx >= n || ty >= m || a[tx][ty] == 0)continue;a[tx][ty] = 0; //标记dfs(tx, ty); //递归}
}
int main()
{cin>>n>>m;string s[n];//按字符串读入for(int i = 0; i < n; ++i)cin>>s[i];//2维数组建表for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j) {a[i][j] = s[i][j] - '0'; //字符转10进制整数}//对所有点BFSfor(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j) {if(a[i][j] != 0) {dfs(i, j);ans += 1;}}cout<<ans;return 0;
}

才39行，比bfs少了20行，虽然很多人说dfs难，但好实现

👊（五）1810: [NewOJ Week 4] 超级骑士

P1810 - [NewOJ Week 4] 超级骑士 - New Online Judge (ecustacm.cn)

👂 今晚约会吧（踩着落日余晖） - SORROW - 单曲 - 网易云音乐

标签：进阶题，深搜，广搜

 DFS，BFS都可以，都尝试下

思路

一开始也一头雾水，看了大佬的文字解释，自己再开干

1，如何判断一个骑士可以走遍整个空间？

只要这个骑士能从(x, y)走到(x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1)

则骑士可以走遍平面

2，由于每步坐标不超过100，可以从(100, 100)出发，暴力走(0 ~ 200, 0 ~ 200)的二维平面，最后检查(100, 100)四周是否被标记(走过)

思路来源NewOJ Week 4题解_[newoj week 4] 减一_傅志凌的博客-CSDN博客

里的E题

🌳广搜  AC

第一次提交

运行错误，一般是数组超限

struct node que[40010]; 
--> struct node que[41000];

不够严谨哈，算数也算错，一开始是想到201*201的，但是201 * 201 != 40001， 

200*201 = 200*200+1*200 = 40200，而201*201还得加上201，== 40401

你个菜鸡

修改后提交，AC 90%，时间超限

AC  90%

#include<iostream>
#include<cstring> //memset()
using namespace std;
int vis[205][205]; //标记
int dx[110], dy[110]; //direction方向
int tx, ty; //临时变量
struct node
{int x, y; //横纵坐标
};
int main()
{struct node que[50010];int t;cin>>t;while(t--) {//归0memset(que, 0, sizeof(que)); //清空结构体数组memset(vis, 0, sizeof(vis)); //清空标记过的点int n;cin>>n;//读入方向for(int i = 0; i < n; ++i)cin>>dx[i]>>dy[i];//初始化队列int head = 0, tail = 0;que[tail].x = 100;que[tail].y = 100;tail++;vis[100][100] = 1; //标记//队列不为空while(head < tail) {//枚举n个方向for(int i = 0; i < n; ++i) {tx = que[head].x + dx[i];ty = que[head].y + dy[i]; //新的坐标//超出边界if(tx < 0 || ty < 0 || tx > 200 || ty > 200)continue;//未访问过if(vis[tx][ty] == 0) {vis[tx][ty] = 1;que[tail].x = tx;que[tail].y = ty;tail++;}}head++; //继续后续队列的扩展}if(vis[99][100] && vis[101][100]&& vis[100][99] && vis[100][101])cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

应该dfs在这题复杂度稍微低了点的原因，bfs得开scanf()才AC

所有cin改scanf()好了

AC  100%

#include<iostream>
#include<cstring> //memset()
#include<cstdio> //scanf()
using namespace std;
int vis[205][205]; //标记
int dx[110], dy[110]; //direction方向
int tx, ty; //临时变量
struct node
{int x, y; //横纵坐标
};
int main()
{struct node que[41000];int t;scanf("%d", &t);while(t--) {//归0memset(que, 0, sizeof(que)); //清空结构体数组memset(vis, 0, sizeof(vis)); //清空标记过的点int n;scanf("%d", &n);//读入方向for(int i = 0; i < n; ++i)scanf("%d%d", &dx[i], &dy[i]);//初始化队列int head = 0, tail = 0;que[tail].x = 100;que[tail].y = 100;tail++;vis[100][100] = 1; //标记//队列不为空while(head < tail) {//枚举n个方向for(int i = 0; i < n; ++i) {tx = que[head].x + dx[i];ty = que[head].y + dy[i]; //新的坐标//超出边界if(tx < 0 || ty < 0 || tx > 200 || ty > 200)continue;//未访问过if(vis[tx][ty] == 0) {vis[tx][ty] = 1;que[tail].x = tx;que[tail].y = ty;tail++;}}head++; //继续后续队列的扩展}if(vis[99][100] && vis[101][100]&& vis[100][99] && vis[100][101])cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

 emmm...有大佬跟我说，不开scanf()，bfs也能AC

说没必要用数组模拟队列，直接用stl的#include<queue>就好，更快一点

🌳深搜  AC

#include<iostream>
#include<cstring> //memset()
int vis[210][210], dx[110], dy[110];
int t, n, tx, ty;
void dfs(int x, int y)
{for(int i = 0; i < n; ++i) {tx = x + dx[i];ty = y + dy[i];if(tx < 0 || ty < 0 || tx > 200 || ty > 200)continue;if(vis[tx][ty] == 0) {vis[tx][ty] = 1;dfs(tx, ty);//不用取消标记了}}
}
using namespace std;
int main()
{cin>>t;while(t--) {memset(vis, 0, sizeof(vis));cin>>n;for(int i = 0; i < n; ++i)cin>>dx[i]>>dy[i];vis[100][100] = 1;dfs(100, 100);if(vis[99][100] && vis[101][100] && vis[100][99] && vis[100][101])cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return 0;
}

难以置信，居然只有37行，而BFS写了58行，大概少20行

由于第一遍写了2次BFS，DFS只写了13分钟

🌼十三，DFS

知识点

在写一篇DFS总结（包含所有题型方法和例题、链接、AC代码），抛开较难的二分图和树的遍历，还有8个题型，不过在写的博客很多，可能需要23年5月后才有时间写

科普博客

→ 《啊哈算法》第四章之深度优先搜索_千帐灯无此声的博客-CSDN博客

加深理解

→ DFS（搜索） - OI Wiki

→ DFS（图论） - OI Wiki

精益求精

在开始之前，我想先对BFS和DFS作个简单的区分

dfs可以用递归来写，也可以用栈来写；bfs可以用数组模拟队列，也可以直接stl的队列

dfs很难找到最优解，只用来找到某个解，内存消耗较小；bfs则适用于找最优解，但不适用于深层次的搜索

dfs如果需要回溯，就需要取消标记；而bfs不需要取消标记

接下来谈谈最近dfs刷题的思考：

第一点思考

关于，为什么有些dfs需要在标记，递归后进行取消标记，而另一些题目则不需要取消标记呢？

eg1: 给定起点，走5步，求所有可能到达的点

eg2: 给定起点，不限制步数，求能否到达终点

问题1限制了步数，所以经过某点的路径会影响结果，那么就需要多次经过同一个点（意味着需要回溯），所以需要取消标记

而问题2经过某点的路径不影响结果（不限制步数），所以不需要多次经过同一个点（不需要回溯），所以不需要取消标记

一次能把所有点走完，不需要取消标记（不需要回溯），走过的点就不会再走了

而如果部分路径需要多次访问，这时就需要回溯取消标记了，不然就没法访问了

第二点思考

这个return;有时可以去掉，具体情况具体分析，需要判断什么时候这里的return;会冗余，加上去会起到什么作用

如果这个return和这层函数的结尾之间没有其他东西，就可以不加

折腾了一个小时没个结论，所以以后都加上吧👌

-- -- End~

👊（一）3502. 不同路径数

3502. 不同路径数 - AcWing题库

标签：DFS，简单，笔试题

常规dfs加了点变化

因为这点变化，只会做模板题的我，第一次没AC（看了别人的代码才发现多写了个vis[]标记数组，本题是不需要标记数组的）

具体为什么后面解释

🌳Wrong Answer

#include<iostream>
#include<set>
using namespace std;
int n, m, k, a[10][10], vis[10][10];
int sum, tx, ty;
set<int>st; //元素不重复void dfs(int x, int y, int s, int sum) //横坐标,纵坐标,步数,当前值
{//方向数组int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//判断边界if(s == k) {st.insert(sum); //集合元素不重复return;}//枚举四个方向for(int i = 0; i < 4; ++i) {tx = x + next[i][0];ty = y + next[i][1];if(tx < 0 || ty < 0 || tx >= n || ty >= m)continue;if(vis[tx][ty] == 0) {vis[tx][ty] = 1; //标记dfs(tx, ty, s + 1, sum * 10 + a[tx][ty]);vis[tx][ty] = 0; //取消标记}}
}int main()
{cin>>n>>m>>k;//读入矩阵for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j)cin>>a[i][j];for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j)dfs(i, j, 0, a[i][j]); //建议4个参数, 不要3个cout<<st.size();return 0;
}

为什么要去掉标记数组(vis[][]或book[][])呢？

因为题目说的很清楚，走过的位置可以重复走（可以回头）

比如初始在a[2][3] == 3, k == 2，规定只能走2步，此时存在向下走一步，再走回来的可能

也就是经历了a[2][3] --> a[3][3] --> a[2][3]三个点，如果加上vis[][]数组，只能走一条不可回头的路

拿到题目第一时间，是观察题目，和常规模板题的情景有哪些区别

在此基础上，给模板加细节，才有机会做对

否则你永远只会做模板题，没前途的

🌳Accepted

注释掉中间4行就AC了

#include<iostream>
#include<set>
using namespace std;
int n, m, k, a[10][10]; //vis[10][10];
int sum, tx, ty;
set<int>st; //元素不重复void dfs(int x, int y, int s, int sum) //横坐标,纵坐标,步数,当前值
{//方向数组int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//判断边界if(s == k) {st.insert(sum); //集合元素不重复return;}//枚举四个方向for(int i = 0; i < 4; ++i) {tx = x + next[i][0];ty = y + next[i][1];if(tx < 0 || ty < 0 || tx >= n || ty >= m)continue;//if(vis[tx][ty] == 0) {//vis[tx][ty] = 1; //标记dfs(tx, ty, s + 1, sum * 10 + a[tx][ty]);//vis[tx][ty] = 0; //取消标记//}}
}int main()
{cin>>n>>m>>k;//读入矩阵for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j)cin>>a[i][j];for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j)dfs(i, j, 0, a[i][j]); //建议4个参数, 不要3个cout<<st.size();return 0;
}

 👂 理想世界 - 马良 - 单曲 - 网易云音乐

👊（二）P1036 [NOIP2002 普及组] 选数

P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：DFS，普及-，素数

虽然看起来简单，貌似是全排列，但是有点绕，你要判重，直接套DFS模板样例都过不了
甚至比不上直接多重for，，，

Wrong

#include<iostream>
using namespace std;
int n, k, ans;
int a[30], vis[30];
bool check(long long x) //判断素数
{if(x == 1) return false;if(x == 2 || x == 3) return true;for(int i = 2; i * i <= x; ++i) {if(x % i == 0)return false;}return true;
}
void dfs(int s, long long sum) //step步数, 总和sum
{//完成任务if(s == k) {if(check(sum)) {ans += 1;//cout<<sum<<endl;}return; //回溯}//遍历for(int i = 0; i < n; ++i) {if(vis[i] == 0) {vis[i] = 1; //标记dfs(s + 1, sum + a[i]); //递归vis[i] = 0; //取消标记}}
}
int main()
{cin>>n>>k;for(int i = 0; i < n; ++i)cin>>a[i];dfs(0, 0); //从第0个数字, 总和为0开始cout<<ans;return 0;
}

4 3
3 7 12 19
6

正常用dfs模板会出现，先选后面的数，再选前面数的情况，就会重复 

已知29是唯一答案，经过了6次29...

假如现在给定1~6，6个数，里面选4个，如何实现按 1 + 2 + 3 + 4, 1 + 2 + 3 + 5
1 + 2 + 3 + 6(第一轮)，1 + 2 + 4 + 5, 1 + 2 + 4 + 6(第二轮)......直到 4 + 5 + 6的顺序呢
也就是，如何判重呢（这里是不同数字组合的判重，而不是总和的判重）

我们在dfs函数中加个参数

dfs中参数startx作用是, 每次只能选它后面的数；而不能先选后面再选前面的（上个代码的错误）

AC  代码

#include<iostream>
using namespace std;
int n, k, ans;
int a[30];
bool check(long long x) //判断素数
{if(x == 1) return false;if(x == 2 || x == 3) return true;for(int i = 2; i * i <= x; ++i) {if(x % i == 0)return false;}return true;
}
void dfs(int s, long long sum, int startx) //step步数, 总和sum, start判重
{ //startx作用是, 每次只能选它后面的数,而不能先选后面再选前面的//完成任务if(s == k) {if(check(sum)) {ans += 1;}return; //回溯}//遍历for(int i = startx; i < n; ++i)dfs(s + 1, sum + a[i], i + 1); //递归
}
int main()
{cin>>n>>k;for(int i = 0; i < n; ++i)cin>>a[i];dfs(0, 0, 0); //从第0个数字, 总和为0开始, 判重cout<<ans;return 0;
}

👊（三）P9011 [USACO23JAN] Air Cownditioning II B

P9011 [USACO23JAN] Air Cownditioning II B - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：DFS，差分，USACO

多点做结合2个甚至3个算法的综合题，选这道题是为了复习差分，真的忘光了

👂 猫咪日记 - 饼饼/袁嘉怡Bella - 单曲 - 网易云音乐

复习 → 前缀和 & 差分 - OI Wiki (oi-wiki.org)

为了巩固差分，我重新做了一次这2题（易 --> 难）

→ P2367 语文成绩 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

→ 3729. 改变数组元素 - AcWing题库

哈哈，又发现个问题，现在习惯性敲完代码 + 过了样例后，再测一组更全面的，结果往往忘了删掉中间（为了测试）增加的cout，导致本来能AC的，WA了。。蓝桥杯要注意这个问题

思路

1，对读入的温度要求，进行 +=k的差分

2，将读入的空调数据按结构体中，四个变量的形式输入

3，一个结构体，一个check判断是否满足降温条件，两个差分函数insert

当然，后来想想，没必要写两个，只需要在dfs递归时，在cold[i].p前加个负号 '-' 即可

关于check()函数中，为什么全部<=0即可，因为只要能抵消到<= 0的程度，就满足降温需求

🌳DFS + 二分  AC  100%

说实话，这么小的数据量没必要二分，但学习一下也好，

当两个甚至多个算法组合在一起，就会暴露出很多问题

#include<iostream>
using namespace std;
int n, m, ans = 1e9, e[110], vis[20]; //最大100栏, 10空调struct node{int a, b, p, m; //[a, b], 降温, 价格
};
struct node cold[20]; //空调//判断满足降温条件
bool check()
{ //还得前缀和一次int sum = 0;for(int i = 1; i <= 100; ++i) { //100个栏sum += e[i];if(sum > 0) return false;}return true;
}//[l, r] -k, 读入空调的差分
void insert1(int l, int r, int k)
{e[l] -= k;e[r + 1] += k;
}
//[l, r] +k, 初始要求的差分
void insert2(int l, int r, int k)
{e[l] += k;e[r + 1] -= k;
}void dfs(int money)
{if(check()) {ans = min(ans, money);return; //回溯}//遍历所有空调for(int i = 0; i < m; ++i) {if(vis[i] == 0) {insert1(cold[i].a, cold[i].b, cold[i].p); //-= kvis[i] = 1; //标记dfs(money + cold[i].m); //递归vis[i] = 0; //取消标记//手动还原差分数组insert2(cold[i].a, cold[i].b, cold[i].p); //+= k}}
}int main()
{cin>>n>>m;int xx, yy, zz;//输入温度要求for(int i = 0; i < n; ++i) {cin>>xx>>yy>>zz;insert2(xx, yy, zz); //+= k}//输入空调数据for(int i = 0; i < m; ++i)cin>>cold[i].a>>cold[i].b>>cold[i].p>>cold[i].m;dfs(0);cout<<ans;return 0;
}

最最关键的是代码第48行，需要我们手动还原差分，

否则经过多次dfs后，样例输入后，会输出2而不是10，

因为过程中的

差分数组e被多次改变而得不到还原

🌳暴力DFS  AC  82%

第一次AC  82%，让我想想有没有什么优化的点

答案是没有

为什么呢，因为出题人觉得暴力的做法，只配得82%得分数，而不是你解出了82%的正解

#include<iostream>
using namespace std;
int n, m, ans = 1e9, e[110], vis[20]; //最大100栏, 10空调struct node{int a, b, p, m; //[a, b], 降温, 价格
};
struct node cold[20]; //空调//判断满足降温条件
bool check()
{for(int i = 1; i <= 100; ++i) //100个栏if(e[i] > 0)return false;return true;
}void dfs(int money)
{if(check()) {ans = min(ans, money);return; //回溯}//遍历所有空调for(int i = 0; i < m; ++i) {if(vis[i] == 0) {for(int j = cold[i].a; j <= cold[i].b; ++j)e[j] -= cold[i].p; //暴力, 小心i, j混淆vis[i] = 1; //标记这个空调使用过dfs(money + cold[i].m); //递归vis[i] = 0; //取消标记//这里同样是要恢复数组e, 只不过这次是直接恢复,//上个代码是恢复差分数组for(int j = cold[i].a; j <= cold[i].b; ++j)e[j] += cold[i].p;}}
}int main()
{cin>>n>>m;int xx, yy, zz;//输入温度要求for(int i = 0; i < n; ++i) { //n头牛cin>>xx>>yy>>zz;for(int j = xx; j <= yy; ++j)e[j] = zz;}//输入空调数据for(int i = 0; i < m; ++i)cin>>cold[i].a>>cold[i].b>>cold[i].p>>cold[i].m;dfs(0);cout<<ans;return 0;
}

👊（四）1116: 组合的输出

 P1116 - 组合的输出 - New Online Judge (ecustacm.cn)

标签：递归，DFS，基础题

思路

1，DFS模板

2，dfs(int step, int startx)中，startx参数，保证升序排列，也就是按字典序

3，利用数组a保存每次的排列，for循环中 a[step] = i； step表示到了第step个数字

4，坑：原文是，每个字符占3个位置，这里提供两种解决方案

挣扎了20分钟，才摸索到2种解决方法

//1
#include<cstdio>
printf("%3d", a[i]);
//2
#include<iomanip>
cout<<setw(3)<<a[i];

而只是用cout<<"  "这种做法，就算你全部换行和空格都和题目一样，最多只能AC 50%

AC代码

#include<iostream>
#include<cstdio> //printf()
using namespace std;
int n, r, a[30]; //数组a保存当前排列
void dfs(int step, int startx) //startx保证升序排列, 防止重复
{if(step == r) {for(int i = 0; i < r; ++i) {//step从0开始, 所以这里也要从0开始printf("%3d", a[i]);}cout<<endl;return; //回溯}//遍历for(int i = startx; i <= n; ++i) {a[step] = i;dfs(step + 1, i + 1); //注意startx只在遍历的初始出现1次}
}
int main()
{cin>>n>>r;dfs(0, 1);return 0;
}

👊（五）1117: 素数环

P1117 - 素数环 - New Online Judge (ecustacm.cn)

标签：基础题，DFS

有个坑，但也补充了知识盲点

第一次敲了20分钟，提交，时间超限，AC 0%，，，我想，不会吧，难道是没剪枝？

可看了下，没找到  if  break的地方，后来才发现，输出大量数据时，printf()比cout更快

当然你也可以关同步，因为需要兼容cin与stdin，cout与stdout，所以cin, cout较之scanf()，printf()更慢

具体可以看(11条消息) cin,cout与scanf，printf的速度到底相差多少_printf比cout快多少_BlingBling520的博客-CSDN博客

因为这个原因，又折腾了20分钟才AC

AC  代码

#include<iostream>
using namespace std;
int n, now = 1, a[20], vis[20]; //数组a保存答案
//判断素数
bool check(int x)
{if(x == 1) return false;if(x == 2 || x == 3) return true;for(int i = 2; i * i <= x; ++i)if(x % i == 0)return false;return true;
}
void dfs(int step)
{if(step == n + 1 && check(a[1] + a[n])) { //首尾相加也是素数for(int i = 1; i <= n; ++i)printf("%d ", a[i]);printf("\n");return; //回溯}//遍历for(int i = 2; i <= n; ++i) {if(vis[i] == 0 && check(a[step - 1] + i)) {//相邻相加是素数a[step] = i;vis[i] = 1; //标记dfs(step + 1); //递归vis[i] = 0; //取消标记}}
}
int main()
{a[1] = 1;while(cin>>n) {printf("Case %d:\n", now++);dfs(2); //1已经确定, 所以从第2步开始printf("\n");}return 0;
}

👊（六）1118: 自然数的拆分

P1118 - 自然数的拆分 - New Online Judge (ecustacm.cn)

标签：DFS，基础题

与之前做的题又有点区分

思路

如果题目说的是，保证拆分的数字按字典序且不重复，则需要在for循环中加个startx参数，然后for(i = startx...)即可

但本题存在重复的数字，我们只需要对a数组进行一个判断

i >= a[step - 1]可以处理这一情况

if(sum + i <= n) {if(step == 0) {a[step] = i;dfs(step + 1, sum + i);}else if(step > 0 && i >= a[step - 1]) {a[step] = i;dfs(step + 1, sum + i);}}

AC  代码

#include<iostream>
using namespace std;
int n, a[30];
//大量输出记得printf()
void dfs(int step, int sum)
{if(sum == n) {printf("%d=", n);for(int i = 0; i < step; ++i) {printf("%d", a[i]);if(i < step - 1)printf("+");}printf("\n");return; //回溯}//遍历for(int i = 1; i < n; ++i)if(sum + i <= n) {if(step == 0) {a[step] = i;dfs(step + 1, sum + i);}else if(step > 0 && i >= a[step - 1]) {a[step] = i;dfs(step + 1, sum + i);}}
}
int main()
{while(cin>>n) {dfs(0, 0);printf("\n");}return 0;
}

🌼十四，拓扑排序（未更新）

👂  不露声色 - Jam - 单曲 - 网易云音乐

🌼十五，Dijkstra

👂 这个世界不会好 - 子默 - 单曲 - 网易云音乐

Dij和Floyd的题放一块

Floyd科普博客👇

(13条消息) 最短路之Floyd-Warshall（10张图解）_千帐灯无此声的博客-CSDN博客

👆

→ 最短路 - OI Wiki (oi-wiki.org)

→ Floyd 算法 - 简书 (jianshu.com)

先来看看Floyd模板，其他部分和Dij几乎一模一样，除了比Dij少了book[]数组和dis[]数组

只有5行，其他都是初始化 + 读入数据 + 输出答案 的活

//通过k中转, i 到 j 距离更短, 就更新
for(int k = 1; k <= n; ++k)for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)if(e[i][j] > e[i][k] + e[k][j])e[i][j] = e[i][k] + e[k][j];

🌼十七，Floyd

👂 我才不看你脸色！ - 蛙腩/AEolus阿一 - 单曲 - 网易云音乐

Dij和Floyd的题放一块

注意Dij不能做有负权边的最短路，因为它的推导过程是基于贪心的且所有边权都是正数的

dijkstra科普博客👇

(13条消息) 最短路之Dijkstra（15张图解）_迪杰斯特拉算法求最短路径图解_码龄?天的博客-CSDN博客

👆

→ 最短路 - OI Wiki (oi-wiki.org)

→ (17条消息) dijkstra算法详解—简单易懂_unique_pursuit的博客-CSDN博客

先来默写一下dijkstra模板（结合输入输出）

第一行输入n个顶点，m条边

后面m行输入 t1 号顶点到 t2 号顶点的距离 t3

最后一行输出 1 号顶点到 1~n 号顶点的最短路径

代码

#include<cstdio>
int main()
{int e[10][10], dis[10], book[10], i, j, n, m;int t1, t2, t3, u, v, Min;int inf = 1e8; //infinity(n.)无穷//读入n个顶点, m条边scanf("%d%d", &n, &m);//初始化for(i = 1; i <= n; ++i)for(j = 1; j <= n; ++j) {if(i == j) e[i][j] = 0;else e[i][j] = inf;}//读入边for(i = 1; i <= m; ++i) {scanf("%d%d%d", &t1, &t2, &t3);e[t1][t2] = t3;}//初始化dis数组, 表示源点1号到其他点初始路程for(i = 1; i <= n; ++i)dis[i] = e[1][i];//初始化book数组for(i = 1; i <= n; ++i)book[i] = 0;//Dijkstra算法核心//源点不用确定, 所以是n - 1次遍历for(i = 1; i <= n - 1; ++i) {Min = inf;for(j = 2; j <= n; ++j) { //从顶点2开始//找确定值（未确定中找最小值）if(book[j] == 0 && dis[j] < Min) {Min = dis[j];u = j;}}book[u] = 1; //顶点u已确定//从刚被确定的顶点出边for(v = 2; v <= n; ++v) //从顶点2开始if(e[u][v] < inf && dis[u] + e[u][v] < dis[v])//两点连通且可更新dis[v] = dis[u] +e[u][v];}for(int i = 1; i <= n; ++i)printf("%d ", dis[i]);return 0;
}

输入输出

6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
0 1 8 4 13 17

👊（一）1488. 最短距离（未完待续）

1488. 最短距离 - AcWing题库

标签：单源最短路，Dij，笔试题，简单

 输入输出放到代码段里

//输入
7 7
1 2 5
1 4 3
2 3 2
2 5 1
3 6 7
5 6 8
6 7 6
3
7
5
4
7
1
2
3
4
5
6
7
//输出
3
1
3
0
0
6
0

注意关键字：

1，无向；2，M，K，Q最大都达10^5，必须用scanf() + printf()

虽说标签是单源最短路，但题目乍一看上去，不就是多源最短路吗？

常规的多源是，求任意两个点之间的最短路，

而本题应该算单源最短路的变式，求的是多个源点（商店）到其他村庄的最短路

由于有K个商店，也就是求K次单源最短路

如果直接朴素Dij，进行K次单源最短路的求解，复杂度最大就接近O(n^3)了，会TLE

方法

建个虚拟源点，不要觉得它很神秘，实际上就是，本来不是1~n个顶点（村庄）嘛

现在多设一个0号村庄，它到所有商店的距离都设置为0即可，就多了这一行代码

就将K次单源最短路转化为普遍意义上的单源最短路

坑

由于不喜欢背模板，我喜欢的是《啊哈算法》那种，先模拟一遍整个过程，每一行代码都按自己的理解写出清楚的注释，也就不需要背模板了

本题顶点数量达10^5，所以如果用二维数组存储图，e[100010][100010]即使声明为全局变量，也会报错 error: size of array e is too large（只能背邻接表模板了）

补充个知识点：二维数组e声明为全局变量，int的话最大约e[5050][5050]，再大就会报错

不会邻接表实现Dij或者vector存图+堆优化的小伙伴，蓝桥杯只能这样骗30%的分了

邻接表模板

//邻接表(头插法)
int h[N], e[M], w[M], ne[M], idx; 
void add(int a, int b, int c) 
{ //读入a到b的距离ce[idx] = b, w[idx]= c, ne[idx] = h[a], h[a] = idx++;
}

然而，Dij里也要对应修改，或者堆优化，然后由于我不知道邻接表的模拟过程是怎样的

所以最终还是放弃这题吧，等蓝桥杯结束了，或者暑假有时间再来学邻接表和堆优化

👇这个就是vector存图的Dij堆优化👇

Ubuntu Pastebin

👆是除了邻接表存图外的另一种方式👆（有时间再来学把）

👊（二）P2935 [USACO09JAN]Best Spot S

P2935 [USACO09JAN]Best Spot S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：枚举，最短路，USACO

 标签说的很对，就是最短路的枚举

注意关键字：1，双向(无向图多敲一行代码)；2，最佳牧场(所以别输出成最小的平均距离)

如果采用Floyd，直接每两个点之间的最短路即可，然后对平均值判断，O(n^3) = 1.25 * 10^8还好

如果采用Dij则需要分别对最喜欢的F个牧场Dij一次，也就是F次Dij，F * O(n^2)快一点点

都是暴力/朴素最短路能做的，毕竟只有500个点，二维数组也是能开的

🌳Dijstra  AC

额外的测试

//自己编的输入
5 2 6
3 5
1 5 4
1 4 6
2 4 8
2 5 11
3 4 10
4 5 12
//加上cout观察过程是否正确
20 1
29 2
20 3
20 4
20 5
//结果
1

样例以及额外的测试都正确，可以提交了

模板基础上加了点东西，有几个卡点

1，代码第17行一开始敲错了，，，

2，第27，28行一开始漏敲，思路被模板限制住了

3，第53行进行K次Dij，一开始没有写Dij函数，全部在主函数里操作，弄的很乱

虽然是一次AC，但还是费了一个半小时（敲代码半小时，debug一小时），如果比赛时Dij不熟练，数据量像这题一样那么小

500^3还是在1e8复杂度左右，不要犹豫，直接Floyd（5行核心代码，很好实现的） 

AC  代码

#include<iostream>
#include<cstring> //memset()
using namespace std;
int e[510][510], book[510], farm[510], dis[510];
int n, F, m, t1, t2, t3, u, inf = 1e9;
void Dijstra(int love) //love号牧场的单源最短路
{book[love] = 1; //love点到自己已经确定//初始化dis数组for(int i = 1; i <= n; ++i)dis[i] = e[love][i];//Dij核心for(int i = 1; i <= n - 1; ++i) { //n - 1次遍历//找确定点int Min = inf;for(int j = 1;  j <= n; ++j)if(book[j] == 0 && dis[j] < Min) { //注意这里是dis[j] < MinMin = dis[j];u = j;}book[u] = 1; //u号点已确定//从确定点出边for(int k = 1; k <= n; ++k)//通过u中转更近if(book[k] == 0 && dis[k] > dis[u] + e[u][k]) {dis[k] = dis[u] + e[u][k]; //更新e[k][love] = dis[k]; //二维数组也更新e[love][k] = dis[k]; //双向}}
}
int main()
{cin>>n>>F>>m; //n个牧场, F个喜欢, m条双向路//初始化数组efor(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j) {if(i == j) e[i][j] = 0; //自己到自己距离0else e[i][j] = inf; //无穷infinity}//读入喜欢的牧场for(int i = 0; i < F; ++i)cin>>farm[i];//读入边for(int i = 0; i < m; ++i) {cin>>t1>>t2>>t3;e[t1][t2] = t3; //t1到t2距离为t3e[t2][t1] = t3; //双向}//F次Dijfor(int i = 0; i < F; ++i) {memset(book, 0, sizeof(book)); //恢复标记数组Dijstra(farm[i]);}//找最佳牧场int ans, ans_sum = inf, sum;for(int i = 1; i <= n; ++i) {sum = 0;for(int j = 0; j < F; ++j)sum += e[farm[j]][i]; //心爱农场到i号农场的距离if(sum < ans_sum) {ans_sum = sum;ans = i;}}cout<<ans;return 0;
}

🌳Floyd  AC 

哈哈，Floyd直接在Dij代码基础上，删掉一半，再补充5行核心代码完活

耗时3分钟（26~30即5行核心代码，其他Dij粘贴过来）

#include<iostream>
#include<cstring> //memset()
using namespace std;
int e[510][510], farm[510];
int n, F, m, t1, t2, t3, u, inf = 1e9;
int main()
{cin>>n>>F>>m; //n个牧场, F个喜欢, m条双向路//初始化数组efor(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j) {if(i == j) e[i][j] = 0; //自己到自己距离0else e[i][j] = inf; //无穷infinity}//读入喜欢的牧场for(int i = 0; i < F; ++i)cin>>farm[i];//读入边for(int i = 0; i < m; ++i) {cin>>t1>>t2>>t3;e[t1][t2] = t3; //t1到t2距离为t3e[t2][t1] = t3; //双向}//Floyd核心//通过k中转, i 到 j 距离更短, 就更新for(int k = 1; k <= n; ++k)for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)if(e[i][j] > e[i][k] + e[k][j])e[i][j] = e[i][k] + e[k][j];//找最佳牧场int ans, ans_sum = inf, sum;for(int i = 1; i <= n; ++i) {sum = 0;for(int j = 0; j < F; ++j)sum += e[farm[j]][i]; //心爱农场到i号农场的距离if(sum < ans_sum) {ans_sum = sum;ans = i;}}cout<<ans;return 0;
}

👊（三）P1119 灾后重建

P1119 灾后重建 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：图论，枚举，最短路，普及+/提高

这道题，考了Floyd的原理：

从 i号 顶点到 j号 顶点，只经过前 k号 点的最短路程（一种动态规划思想 

很棒的练手题目

思路

1，写一个Floyd函数int Floyd(int x)，意思是通过k号顶点中转

2，将重建完成时间读入一维数组tim[]

3，初始化二维数组e[][]，并读入边

4，剩下q次询问就好

注意

1，顶点从0号开始，不是1号

2，两个点需要双向边，一个是Floyd更新数组e时，一个是主函数中读入边时

3，我们在q次询问前，增加一个变量now = 0，表示重建到了第now个村庄，应该注意的是，now要放q次询问的循环外，否则就像我一开始一样，每次询问都从第0个村庄开始重建，于是TLE了60%的样例

AC  代码

#include<cstdio> //scanf(), printf()
int e[210][210], tim[210];
int n, m, q, t1, t2, t3, inf = 1e9;
//经过第x号点中转
int Floyd(int x)
{for(int i = 0; i < n; ++i)for(int j = 0; j < n; ++j)if(e[i][j] > e[i][x] + e[x][j]) {e[i][j] = e[i][x] + e[x][j];e[j][i] = e[i][x] + e[x][j]; //双向Floyd也要更新}
}
int main()
{scanf("%d%d", &n, &m);//第i个村庄重建完成时间for(int i = 0; i < n; ++i)scanf("%d", &tim[i]);//初始化二维数组efor(int i = 0; i < n; ++i)for(int j = 0; j < n; ++j) {if(i == j) e[i][j] = 0;else e[i][j] = inf;}//读入边for(int i = 0; i < m; ++i) {scanf("%d%d%d", &t1, &t2, &t3);e[t1][t2] = t3; //t1到t2的距离t3e[t2][t1] = t3; //双向}scanf("%d", &q);//q次询问int now = 0; //这个得放外面, 否则每次都从第0个开始重新Floydwhile(q--) {scanf("%d%d%d", &t1, &t2, &t3);//关键: 第now个村庄建成时间小于给定时间while(tim[now] <= t3 && now < n) //now < n一开始漏了Floyd(now++); //否则你可以通过后续不存在的距离为0的道路中转//不可到达 || t1未建成 || t2未建成if(e[t1][t2] == inf || tim[t1] > t3 || tim[t2] > t3) {printf("-1\n");continue; //跳出本次循环}printf("%d\n", e[t1][t2]);}return 0;
}

🌼十六，SPFA（未更新）

👂 世间美好与你环环相扣 - 柏松 - 单曲 - 网易云音乐

🌼十八，最小生成树（未更新）

👂 声声慢 - 崔开潮 - 单曲 - 网易云音乐

🌼十九，最近公共祖先（未更新）

👂 渡渡年 - 要不要买菜 - 单曲 - 网易云音乐

🌼二十，二分图（未更新）

👂 風になる（幻化成风） - つじあやの - 单曲 - 网易云音乐

🍋总结 

大一参加蓝桥杯注定无法取得好成绩，因为数据结构是大二上才学，先不谈数据结构，单就算法来说，大一能掌握一半的基础算法都不错了，只是一半的基础算法，最多也就C++A组省二

1，对拍，找bug很棒的方法

2，s.find(), s.substr() 

#include<cstring> //s.substr(), s.find()string s1 = s.substr(j, i); //下标j开始, 截取i个字符
if(s.find(s1, j + 1) == string::npos)
//没有找到子串, 返回string::nposif(s.find(s1, j + 1) != string::npos)
//找到子串

3，map的迭代器

#include<iostream>
#include<map>
using namespace std;
map<int, int>m;
for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it) //迭代器printf("%d ", it->second);

4，蓝桥杯技巧

不论是比赛还是平时，OI赛制都要懂得自己设计样例来测试代码，不要只是过了样例就提交

也许有些简单的错误是样例测试不出来的

样例过了后，再想2~5组数据，都过了再提交，没过就好好检查下为什么信心满满的代码不行，总能揪出错误

5，O2优化

洛谷或者AcW里少数的题会卡O2，起到常数优化的效果

代码第一行加上：#pragma GCC optimize(2)

#pragma GCC optimize(2)

蓝桥杯是可以用的

6，数组超限

是个大坑，比如201 * 201的二维平面，你得开到40401以上，而不是40001以上，因为 201 * 201 = 40401，心算不好就拿🖊算，要么就多开个几千

7，测试后忘删cout

不论OI还是IOI，ACM赛制，写完代码过了样例后，利用cout再测多一组数据，并观察过程是否正确，都是好习惯

然而，你经常忘了删cout，导致AC  100%变成了AC  0%，要注意

8，关于scanf()和printf()

大量输入时，用scanf()，不用cin

大量输出时，用printf()，不用cout

9，关于stl

参加蓝桥杯，天梯赛等比赛，它们是支持C++11的，一定要学stl，不会stl是硬伤，现在所有的二分还是别的算法，我都是现场手写的，虽说对打基础 / 以后的面试题，有帮助

但是比赛谁给你那么多时间？所以我很多比赛有些会的题，就没时间看了

一是熟练度不够，二是没学过stl

目前stl接触过的只有sort()，#include<queue>和<stack>最基础的两三个操作，其他完全没见过

等23年蓝桥杯结束应该好好学学stl，外加对应题目的练习