DFS

DFS介绍

DFS，即深度优先搜索，经常用于暴力以及图上遍历等。相比于bfs,dfs是纵向的搜索，是一次性找到底的。从根找到底，然后退回来换条路继续走到底，直到走完。

DFS可以理解为是递归+回溯。对于一棵DFS树，其搜索的方式是从根结点开始，沿着一条边一直走到底，层层递归，每次进入一个子节点就可以理解为一个新的以此子节点为根的DFS树，称之为递归。当访问到叶子结点时，又需要将叶子结点的信息返回并总结到该叶子节点的父亲节点，称之为回溯。

DFS大部分分为树上DFS与图上DFS，但其实两者是相通的，图上DFS可以将上下左右四个方向的遍历结果转化为该位置的四个儿子结点，此时还需要一个vis数组用来记录该儿子结点是否在别的分支出现过，尽管从一个点到另一个点会有多条路径，但如果不是要求最短路径的情况下，往往只需要记录一次即可。

题意

给定一张二维图，图上有两个连通块，求使得两个连通块相连的最短路径。

思路

由于无法区分两个连通块，所以通过dfs对两个连通块中的元素分别赋值0/1，然后对于两个连通块中的所有点分别求曼哈顿距离-1即可。（曼哈顿距离：水平距离+竖直距离）

前言

由于前缀和和差分一个加一个减，两个在写法上差距不大而且具有一定共同点，所以放在一块进行描述。

前缀和

前缀和介绍

前缀和顾名思义，就是一段数列前面某一段连续数列的和。

他经常用于预处理区间和的信息，通过预处理前缀和，我们可以快速的得到某段连续数列的和是多少。

当我们需要求取的区间和时，我们可以用来获取，经常会有人将减号后面写成，但是我们需要保留的和，需要减去的重复部分应该是之前的部分

题意

给定，求与范围内与互质的数的个数

思路

​ 这个就是欧拉函数的定义。

首先根据唯一分解定理可得：设，其中为质数，有

，其中后面连乘的部分与 无关，那么可以直接由来获取所有，直接分解质因数即可。对于，根据同余，可以通过快速幂得到。答案要求对大质数取余，除某个数等于乘该数的余数减二次方，即就是逆元。

题意

给定n位字符串，可以对连续的几位都进进行+1/-1的操作，求变成目标串最少的操作次数

思路

这里涉及到一个概念叫做相对距离，对于从起始串到目标串的变化可以转化为0000串到某个串的变化，每一位的相对距离保持不变即可。

这样我们就只需要预处理求出0000串到所有状态的最小操作次数即可，可以通过BFS来求出并记录。

题意

给定长度为n的数列，求出连续序列和为k的倍数的序列个数。

思路

首先，对于每一段前缀和都进行对k取余。

那么根据同余定理，,如果一段前缀和如果和前面的某段前缀和的值相同，那么前面的那个前缀所缺少的几个数（除最后一个元素）的和一定是k的倍数，对于每个余数所对应的前缀和数量，用一个map记录一下即可。

最后记得再加上，因为每次前缀和所得的那几个数并不包括尾部，所以当遍历到最后一个元素时，并无法得出包括最后一个元素的符合条件的连续序列数量，而是包括最后一个前面的那个元素的符合条件的连续序列数量。

题意

几间房间有各自的温度，每次操作可以对连续的几间房间+1/-1度，请问使每个房间都到达目标温度的最小操作次数

思路

​ 将目标温度减去起始温度后会得到一串数列a，目标就是求使这串数列全部为0的操作次数，由于需要实现区间加，比较容易联想到使用差分来进行操作。

​ 转化为差分数组后，每次操作就可以转化为对于某个位置+1/-1，在对某个位置-1/+1，或者不存在后者（就是位置为数列尾部+1）。

​ 这样就只需要比较到底是+1的次数多还是-1的次数多即可

题意

对一些墙壁进行作画，被作画的墙不会毁掉，只有和一面墙相邻的会被毁掉，每天可以画一面墙，每天画的墙必须和昨天画的相邻，然后会有一面墙被毁掉，每堵墙都有美观分，求使最终剩下的墙美观分能够到达的总和最高的值。

思路

首先只有和一面墙相邻的会被毁掉意思就是从两端开始毁掉，由于每天画一面墙，毁一面墙，那最终是能保留面墙，那么题目就是求长度为的连续序列和的最大值。

然后，我们就需要枚举每个起点，来比较以此为起点的连续序列和。其实循环下去每次减一个头元素，再加一个尾元素也可以。但是这边用前缀和来处理，每个连续序列和的计算公式为，需要注意的是，虽然是以为起点，但是号元素还是需要的，想要获取以为起点的连续序列和，需要减去前面的前缀和。

题意

m份订单，每份订单需要从s天到t天租借d个教室，每天都有r个教室可供租借，每个订单含顺序执行，不需要考虑每天是否需要更换租借教室，求从哪份订单开始会供不应求

思路

​ 显然由于订单的不断积累，每天租借的教室数量保证会持续上涨，满足了单调性，再看一下时间复杂度，1e6的话O(nlogn)能卡，很自然的可以想到二分答案的做法。

​ 二分的难点主要在check，但是二分可以O(n)的来处理，那么我们可以将当前需要check的前x个订单内容加起来，再去查看每天是否有超出可租借范围的。这样思路上没问题，但是前x个订单内容加起来如果直接暴力执行的话，每天都加上某个值显然时间复杂度过高，这种区间加有两种处理方法，一种是直接上数据结构，无脑套线段树，另一种就是通过差分把区间加改为单点加，这样时间复杂度就没有问题了。

二分查找

最早接触二分一般都是从二分查找开始，对于一串有序数列（假设单调递增），如果中间值小了就往右半边找，如果中间值大了就往左半边找。

代码如下(此处为找最后一个等于x的数，如果没有x则为大于x的第一个数)：代码为什么这么写后面会讲

1
2
3
4
5
6
7

int l=1,r=n;
while(l<=r){
	int mid=l+r>>1;
	if(mid<=x)l=mid+1；
	else r=mid-1;
}
cout<<r<<endl;

显然对于二分不可能只局限于二分查找，我们经常会遇到对于答案进行二分的情况，将if语句中的mid<=x换成check(mid),就是我们常见的二分模板，其实二分查找也可以通过修改check函数得到

什么情况可能会使用二分

1. 单调有序数列

2. 最大值的最小值/最小值的最大值

3. O(nlogn)的时间复杂度（logn的二分，O(n)的暴力扫一遍）