DFS与BFS

DFS与BFS都是用来搜索的常用方法，但是两者有不同点，DFS更适合层层深入的情况，但是DFS遇到分支很多的时候往往非常慢甚至会迷路，而BFS更适合找全局最优解，但是BFS面对层次很深的情况很慢很慢，因此在平常使用时就要判断使用DFS还是BFS。

DFS

分治

分治法适用的情况

分治法所能解决的问题一般具有以下几个特征：

  • 该问题的规模缩小到一定的程度就可以容易地解决

  • 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

  • 利用该问题分解出的子问题的解可以合并为该问题的解；

  • 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

分治法的基本步骤

分治法在每一层递归上都有三个步骤：

​ step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

​ step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

​ step3 合并：将各个子问题的解合并为原问题的解。

可使用分治法求解的一些经典问题

二分搜索

基本的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) { // 注意
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        if (nums[mid] < target)
            left = mid + 1; // 注意
        if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}

寻找左侧边界的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target)
            right = mid;
        if (nums[mid] < target)
            left = mid + 1;
        if (nums[mid] > target)
            right = mid; // 注意
    }
    return left;
}

寻找右侧边界的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target)
            left = mid + 1; // 注意
        if (nums[mid] < target)
            left = mid + 1;
        if (nums[mid] > target)
            right = mid;
    }
    return left - 1; // 注意

大整数乘法

Strassen矩阵乘法

棋盘覆盖

合并排序

快速排序

线性时间选择

最接近点对问题

循环赛日程表

汉诺塔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <stdlib.h>
using namespace std;
static int count = -1;
void move(char x,char y);  // 对move函数的声明 
void hanoi(int n,char one,char two,char three);  // 对hanoi函数的声明
int main()
{
	int m;
	cout<<"请输入一共有多少个板子需要移动";
    cin>>m;
    cout<<"以下是"<<m<<"个板子的移动方案:"<<endl;
    hanoi(m,'A','B','C');
    system("pause");
    return 0;
}
void hanoi(int n,char one,char two,char three)  // 定义hanoi函数 
    // 将n个盘从one座借助two座,移到three座 
{	
	if(n==1) move(one,three);
    else {
    hanoi(n-1,one,three,two); //首先把n-1个从one移动到two
    move(one,three);  //然后把最后一个n从one移动到three
    hanoi(n-1,two,one,three);  //最后再把n-1个从two移动到three
 	}
}
void move(char x,char y)  // 定义move函数 
{
	count++;
    if( !(count%5) )  cout<<endl;
    cout<<x<<"移动至"<<y<<"  ";
}

并查集

基本信息

并查集是一种将拥有某种联系的一些节点归类的算法，其类似与人们的亲属关系，如果我们的祖先是同一个人，那么我们是同一类人，并查集也是这个意思，利用祖先的编号关系来区分或者合并两个节点。

详细知识

初始化

对于并查集，我们创建一个数组id[maxn]来表示每一个节点的祖先节点，那么问题来了，没有祖先的，或者自己就是祖先，怎么办呢。

对于这种情况，我们将其祖先设置为他自己，因此第一步，先令每个人都是一个单独的节点，也就是每个人都没有祖先。

1
2
3
4
int id[maxn];
inline void init(int n){
	for(int i = 1;i <= n;i++) id[i] = i;
}

查找祖先

初始化完成之后，那么对于两个点，怎么来找他们的祖先节点呢，这里使用find函数

1
2
3
4
inline int find(int p){
	if(p == id[p]) return p;//当他的祖先是他自己，那么他就是祖先，否则对齐祖先再次寻找
	return find(id[p]);
}

在这里我们可以小小优化一下，一点小小的操作可以让这个查询操作时间减很多，那就是让他的父亲节点直接储存他的祖先

1
2
3
4
inline int find(int p){
	if(p == id[p]) return p;
	return id[p] = find(id[p])//将其父亲节点储存为他的祖先，下一次查询就不用再查一次了，直接就能查到
}

合并

现在初始化完成了，查找祖先也有了，就只剩下有关系的节点合并了

1
2
3
4
5
6
7
8
9
inline void funion(int p, int q){
	int rootp = find(p);
	int rootq = find(q);
	if(rootp == rootq) return;	//如果两个人已经是一类人，那么就不用合并
	id[rootp] = rootq;			//如果不是同一类人，直接将他们的祖先合并即可
								//即让一个人的父亲变成另一个节点的祖先，那么两个点也就是一类了
    cnt--;						//这个操作是我习惯性加的，每合并一个节点，cnt--
    							//那么到最后cnt的数量也就是所有祖先的数量，就可以延申出去
}

模板题

P3367 【模板】并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
using namespace std;
const int maxn = 1e4 + 5;
int id[maxn];
inline void init(int n){
    for(int i = 1;i <= n;i++) id[i] = i;
}
inline int find(int p){
    if(p == id[p]) return p;
    return id[p] = find(id[p]);
}
inline void funion(int p, int q){
    int rootp = find(p);
    int rootq = find(q);
    if(rootp == rootq) return;
    id[rootp] = rootq;
}
int main(void)
{
    int n, m;
    cin>>n>>m;
	init(n);
    while(m--){
        int z,x,y;
        cin>>z>>x>>y;
        if(z == 1){
            funion(x, y);
        }else{
            if(find(x) == find(y)) cout<<"Y"<<endl;
            else cout<<"N"<<endl;
        }
    }
    return 0;
}

over!

排序

拓扑排序

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

百度百科定义：

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

转发一大佬的例子

拓扑排序示例

这五种都是可以选择的方案，都是拓扑排序，只是选择的策略不同。因此，拓扑排序可以存在多个。

生成拓扑排序的方法一般为：

1.从图中选择入度（以其为终点的边的数量）为0的顶点，输出

2.删除顶点，删除以其为起点的边

3.重复以上步骤，直到无顶点或当前所有顶点的入度都不为0（有环）

简易版算法

1
2
3
4
5
6
7
8
9
10
11
for(int i = 0;i < n;i++)
    for(int j = 0;j < n;j++){
        if(in[j] == 0){//寻找入度为0的点
            now = j;
            ans[cnt++] = j;//存点
            in[j]--;//当前点入度减一
            break;
        }
    for(int j = 0;j < n;j++) if(a[now][j] != 0) in[j]--;//与当前点为起点的边的终点入度减一
}
for(int i = 0;i < n;i++)cout<<ans[i]<<" ";

升级版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
queue<int>q;
vector<int>edge[n];
for(int i = 0;i < n;i++)
	if(in[i] == 0) q.push(i);//存入入度为0的点
vector<int>ans;
while(!q.empty()){
    int p = q.front();//寻找一个入度为0的点
    q.pop();//入度为0的点出去
    ans.push_bach(p);
    for(int i = 0;i < edge[p].size();i++){//遍历所有边
        int y = edge[p][i];
        in[y]--;//终点入度减一
        if(in[y] == 0)q.push(y);//入度为0存入
    }
}
if(ans.size() == n) for(int i = 0;i < n;i++) cout<<ans[i]<<" ";
else cout<<"WA!";

lca

基本信息

lca 是在树上面寻找两节点的最近共同祖先。

lca1

例如对于上面例子，13 与 12 的最近共同祖先是3。

那么怎么找呢，如果一个一个找，12 -> 9 -> 6 -> 3，13 -> 10 -> 7 -> 3，这明显不行，直接T飞，那么有没有方法可以一次找很多个呢。直接次方找不香么，算法复杂度直接降维打击O(lgN)，这就是lca算法。

详细知识

dfs初始化

那么怎么做到呢，因为要跳着找，因此第一步，需要找到每个节点的深度depth。这里用的是链式前向星存图。

1
2
3
4
5
6
7
int depth[maxn];
void dfs(int now, int fath){
	depth[now] = depth[fath]+1;
    for(int i = head[now];i;i = edge[i].next){
        if(edge[i].to != fa) dfs(edge[i].to, now).//跳过父亲节点，不然就回去了
    }
}

然后在这里面可以找到每个节点的父亲节点，我们只用储存其中的部分父亲节点，因此开一个fa[maxn][21] 来储存当前节点的21个父亲，分别代表的是第2^1，2^2，2^3，2^4，…，2^21个父亲节点。

此处我们先对数据进行一个优化，建立一个lg[maxn]数组，来储存每个数字的lg值。要加一是因为lg 1 = 0，但是很明显，1也是他的父亲。

1
2
3
4
int lg[maxn];
for(int i = 1;i <= n;i++){
	lg[i] = lg[i-1] + (1 << lg[i-1] == i);
}

然后来计算fa数组

1
2
3
4
5
6
7
int fa[maxn][21];
void dfs(int now, int fath){
    fa[now][0] = fath;
	for(int i = 1;i < lg[depth[now]];i++){//偏移过1了这里就不用偏移了
		fa[now][i] = fa[fa[now][i-1]][i-1];//因为每一段的长度是乘2的，因此应该跳二倍层，你的爷爷是你爸爸的爸爸嘛。
	}
}

这样就有了完整的dfs代码来初始化数据。

1
2
3
4
5
6
7
8
9
10
11
int fa[maxn][21], depth[maxn];
void dfs(int now, int fath){
    fa[now][0] = fath;
	depth[now] = depth[fath] + 1;
	for(int i = 1;i < lg[depth[now]];i++){
		fa[now][i] = fa[fa[now][i-1]][i-1];
	}
	for(int i = head[now];i;i = edge[i].next){
		if(edge[i].to != fath) dfs(edge[i].to, now);
	}
}

lca主查询

先上代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lca(int x, int y){
	if(depth[x] < depth[y]) swap(x, y);//令x的深度大于y的深度
    while(depth[x] > depth[y]){//使x先跳到与y同一深度
        x = fa[x][lg[depth[x] - depth[y]] - 1];//计算lg是加一了，这里就要减回去
    }
    if(x == y){//如果此时x与y相等，那么已经到达共同祖先，否则需要再向上跳。
        return x;
    }
    for(int k = lg[depth[x] - 1];k>=0;k--){//先跳大步，再跳小步
        if(fa[x][k] != fa[y][k]){//到达最近的共同祖先时，两个人的祖先肯定不相同，
            x = fa[x][k];        //那么就跳过去，最后得到的就是最近的公共祖先的儿子节点
            y = fa[y][k];
        }
    }
    return fa[x][0];
}

此处重点讲两处

1
2
3
while(depth[x] > depth[y]){
	x = fa[x][lg[depth[x] - depth[y]] - 1];
}

这里联系2进制来理解较好。2进制yyds。

对于两个节点A，B，深度分别为19，2，如果要让其跳到同一深度，很明显需要让A跳到2去。那么怎么跳呢。

我们来展开19(10011) 2(10)，两者相减，(10001)，就意味着A要跳这么远才能跳到2去。让我们来观察一下fa数组，fa数组分别储存的是每个次方的节点，因此fa[19][4]其实储存的就是(10000)号父亲节点，跳过去，这样就只剩下一个(1)没有跳了，再跳一下，就相同了。

从这里可以发现，其实lg数组储存的是每个数字二进制第一个1出现的位置。

1
2
3
4
5
6
for(int k = lg[depth[x] - 1];k >= 0;k++){
	if(fa[x][k] != fa[y][k]){
		x = fa[x][k];
		y = fa[y][k];
	}
}

这里是先跳大步然后跳小步，一定要保证不相同，这样就能一直跳，跳到最近公共祖先的下一个节点，不然虽然能跳到公共祖先，但是你不能保证这个节点是最近的。

这里主要说明一下在k次内是肯定可以找到的。lg找的是深度的第一个1的位置，但是如果每个k都跳的话是肯定会大于等于原本的深度的。因为如果每个k都跳，那么就跳了(111…11)步，这是肯定大于等于原来的深度，也就是肯定能找到。

至此，lca完毕。

模板题代码

P3379 【模板】最近公共祖先（LCA）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 5e5 + 5;
struct edge{
    int to;
    int next;
}edge[maxn << 1];
int head[maxn], cnt;
void add(int x, int y){
    edge[++cnt].to = y;
    edge[cnt].next = head[x];
    head[x] = cnt;
}
int depth[maxn], fa[maxn][21], lg[maxn];
void dfs(int now, int fath){
    fa[now][0] = fath;
    depth[now] = depth[fath] + 1;
    for(int i = 1;i < lg[depth[now]];i++){
        fa[now][i] = fa[fa[now][i-1]][i-1];
    }   
    for(int i = head[now];i;i = edge[i].next){
        if(edge[i].to != fath) dfs(edge[i].to, now);
    }
}
int lca(int x, int y){
    if(depth[x] < depth[y]) swap(x, y);//令x > y
    while(depth[x] > depth[y]){
        x = fa[x][lg[depth[x] - depth[y]] - 1];
    }
    if(x == y) return x;
    for(int k = lg[depth[x] - 1];k >= 0;k--){
        if(fa[x][k] != fa[y][k]){
            x = fa[x][k];
            y = fa[y][k];
        }
    }
    return fa[x][0];
}
int main(void){
    int n, m, s;
    scanf("%d %d %d",&n, &m, &s);
    for(int i = 1;i < n;i++){
        int x, y;
        scanf("%d %d",&x, &y);
        add(x, y);
        add(y, x);
    }
    for(int i = 1;i <= n;i++){
        lg[i] = lg[i-1] + (1 << lg[i-1] == i);
    }
    dfs(s,0);
    for(int i = 1;i <= m;i++){
        int x, y;
        scanf("%d %d",&x, &y);
        printf("%d\n",lca(x, y));
    }
    return 0;
}

st表

基本信息

st表是用来解决区间最大最小值的问题的，此问题如果利用常规思路，算法复杂度是O(N ^ 2)，而使用st表的话，可以在O(NlgN)预处理，O(1)查询，快的不是一点半点。他和lca其实是一个思路，对于每个数字，储存其后面2^n范围内的最大值，然后直接查询即可。

详细知识

预处理

我们建立一个MAX[maxn][21]数组来储存以当前数组为起点的，连续2^n的范围内的最大值，其中MAX[maxn][0]即为2 ^ 0 = 1范围内的最大值，即数字本身。

然后使用动态规划来将MAX数组处理。

1
2
3
4
5
6
7
8
int MAX[maxn][21];
inline void init(int n){
	for(int j = 1;j <= 21;j++){
		for(int i = 1;i + (1 << j) - 1 < n;i++){
			MAX[i][j] = max(MAX[i][j-1], MAX[i + (1 << (j-1))][j-1]);
		}
	}
}

这个动态规划可以用下面这个图来解释

st1

整段的最大值是左右两段其中之一的最大值。

查询

查询和上面的思路一样，因为我们已经找出来了以每个数字为起点，长度为2^n的序列的最大值，因此我们只需要将整个区间分成两个区间的并集即可，为了保证两个小区间一定包含了全部区间，两个小区间需要尽量大，最好是都是2^n长。

1
2
3
4
5
6
7
8
int lg[maxn];//预先计算lg，如果觉得麻烦可以直接用log2()函数
int query(int l, int r){
	int m = lg[l - r + 1] - 1;//使用与lca同样的方法将全部的lg算出来，减小常数，注意有偏移要减回来
	return max(MAX[l][m], MAX[r - (1 << m) + 1][m]);
}
for(int i = 1;i < n;i++){
    lg[i] = lg[i-1] + (1 << lg[i - 1] == i);//偏移了1，
}

区间长度为2 ^ m长，这是[L,r]内最长的次方数，也是最长的2^n长度。

st2

模板题代码

P3865 【模板】ST 表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int f[maxn][21];
int lg[maxn];
inline void init(int n){
    for(int i = 1;i <= n;i++){
        lg[i] = lg[i-1] + (1 << lg[i-1] == i);
    }
    for(int j = 1;j <= 21;j++){
        for(int i = 1;i + (1 << j) - 1 <= n;i++){
            f[i][j] = max(f[i][j-1], f[i + (1 << (j - 1))][j-1]);
        }
    }
}
inline int query(int l, int r){
    int mid = lg[r - l + 1] - 1;
    return max(f[l][mid], f[r - (1 << mid) + 1][mid]);
}
signed main(void){
    int n, m;
    scanf("%d %d",&n, &m);
    for(int i = 1;i <= n;i++)scanf("%d",&f[i][0]);
    init(n);
    for(int i = 1;i <= m;i++){
        int l, r;
        scanf("%d %d",&l, &r);
        printf("%d\n",query(l,r));
    }
    return 0;
}

over！

矩阵快速幂