算法高阶

本部分算法难度较高，建议读者充分掌握算法基础之后再来学习。个人感觉对于蓝桥杯有点多，但是对于leetcode刚刚好(¬‿¬)

目前以视频的方法为主，等蓝桥杯考完之后按照labuladong或者是考研的方法写代码。

站主要备考考研了，可能要等考研之后才有充足的时间回头来修改和完善博客

我的仓库使用指南

我的仓库链接格式如下：https://github.com/lloyd-kai/cpp-lanqiaocup/tree/main/1_20 其中1_20表示的是日期(一般是2025)，里面的文件就包含对应题目的解答(均通过对应题目的测试)或者是算法实现，其中文件名lanqiao表示 是蓝桥杯官网上的题目，_ 后面的数字是蓝桥杯的题目编号，可以找到对应的蓝桥杯的题目，比如题目链接是https://www.lanqiao.cn/problems/498/learning/?page=1&first_category_id=1&problem_id=498 problems斜杠后面的数字498 就是对应的题目编号，你就在我指定链接下面的文件夹下按照lanqiao_题目编号.cpp 这样的格式找对应文件，就可以看到对应题目的解答代码。

001_demo.png

数据结构

基础数据结构

RMQ问题

【概念】：RMQ(Range Minimum/Maximum Query)问题是指对于数组，每次给一个区间[l,r],要求返回区间内的最大值或最小值（的下标）也就是说，RMQ就是求区间最值的问题。对于RMQ问题，容易想到一种O(n)的方法，就是用i直接遍历区间，找出不断比较a[i]与max的大小关系，然后不断更新max,最后得出的就是最大值。但是如果要进行多次的查询，这个算法将会变得非常慢。于是，我们可以利用倍增和动态规划的思想，利用“ST表”这个数据结构来帮助解决。

ST表

ST表是一种可以“静态求区间最值”的数据结构，本质上是一种dp.假设我们要求区间最大值（最小值类似），设状态st[i][j]表示从开始，大小为2^ j的长度的区间的最大值，即区间[i,i+2^j-1]的最大值。状态转移方程为st[i][j]=max(st[i][j−1],st[i+(1<<(j−1))][j−1]);st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);注意状态转移的方向和保证区间合法。

区间查询：为了查询区间[[l,r]的最大值，它可以分解为两个小区间的最大值，例如要求[2,7]的最大值，可以分解为[2,2+2 ^ 2-1],[7-2 ^ 2+1,7]的最大值，也就是max(st[2][2],st[7−4][2])max(st[2][2],st[7-4][2]),拓展一下，[l,r]区间，需要找出一个k,使得2^ k<=r-1+1,k<=log2(r-l+1),可以分解为max(st[l][k],st[r−2k+1][k])max(st[l][k],st[r-2^k+1][k])

1
2
3
4
5
int getMax(int l,int r)
{
    int k = log(r-l+1)/log(2);
    return max(st[l][k],st[r-(l<<k)+1][k]);
}

【例题】

直接按照st表模板套就行

并查集

【概念】：并查集是一种图形数据结构，用于存储图中结点的连通关系。每个结点有一个父亲，可以理解为“一只伸出去的手”，会指向另外一个点，初始时指向自己。个点的根节点是该点的父亲的父亲的…的父亲，直到某个点的父亲是自己（根）当两个点的根相同时，我们就说他们是属于同一类，或者说是连通的。比如：3、6的根都是3，所以他们是连通的，2、4是连通的，而2、6不连通，因为他们的根不同。

【实现】：找根函数

1
2
3
4
5
6
7
8
9
10
11
int root(int x)
{
    //如果根是自己就返回
    if(pre[x] == x)
    {
        return x;
    }
    //根不是自己就返回父节点的根
    //pre数组是存储父节点的数组
    return root(pre[x]);
}

合并操作：在并查集中，所有的操作都在根上，假如我要使得x和y两个点合并，只需要将root(x)指向root(y),或使得root(y)指向root(x)。即

1
pre[root(x)] = root(y);

路径压缩：找根函数的复杂度最坏情况下会达到O(n),如果查询次数较多的话效率将会非常低下。我们可以在找根的过程中，将父亲直接指向根，从而实现路径压缩，这样可以使得找根的总体时间,复杂度接近O(1)。如下图，执行一次root(7)之后，沿途的点都会直接指向根3。

1
2
3
4
int root(int x)
{
    return pre[x] = (pre[x] == x?x:root(pre[x]));
}

【例题】

直接用并查集就行了

本部分算法实现与例题解决实现代码链接：点击此处

带权并查集

【例子引入】：某个镇上的几个居民家族怀着重建家谱的愿望，以便能够追溯自己的家族历史。由于时间的流逝，这些家族只能依靠现存的资料来确定镇上曾经存在过的家族关系。根据现有的资料，我们能够获知镇上居民之间的父子关系，从而描绘出一个家族谱系。基于上述情况，我们需要进行一系列的查询，以确定每个现存居民属于哪个家族，并且找出最早祖先的名字，并且查询是第几代人。这个过程将帮助我们重新构建这些家族的历史，从而理清各个家族之间的关系。此时就是带权并查集了，特殊的每个边权值为1。简而言之，就是带权值的并查集。

【实现】：带权并查集和普通的并查集不一样，需要维护某一个节点到其根节点的路径长度(权值和)，首先我们需要定义一个dis数组：dis[],fa[],由于我们还需要维护路径长度，所以需要改写两个操作函数：1. 因为路径压缩会改变点与点的连接关系，路径压缩后，点的父节点变为了根节点，所以需要更新Dis数组 2.集合的代表元（根节点）是没有父结点的，所以Dis数组中也没有值。但是合并集合后其中一个根节点变为了另一个集合根节点的子节点，所以需要赋值。

Find函数：
递推找到该节点的祖先节点，在回归过程中实现路径压缩。路径压缩可以理解成将该节点直接连到祖先节点上，当它儿子节点，同时权值dis也更新成与祖先节点的关系。路径上的每一个节点先更新该节点的父亲节点father(=fa[x])与祖先节点的关系（递归），然后该节点和祖先节点的关系就可以表示为dis[x]+dis[father];示例代码如下

1
2
3
4
5
6
7
8
9
10
11
12
int find(int x)
{
    //如果节点的父节点是他本身
    if(f[x] == x)
    {
        return x;
    }
    //否则递归找到其父节点
    int fa = find(f[x]);
    dis[x] += dis[f[x]];
    return f[x] = fa;
}

merge函数：合并两个没有联系的独立集合。两个集合本来没有联系，每个集合内部的点存在联系，通过联系两个不同集合中独立的两个点使得两个集合建立关系。合并两个集合，实质就是建立两个集合中祖先节点之间的关系。合并后集合内部的点之间的关系通过各自和祖先节点之间的关系得到。示例代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
//思路：先通过find实现路径压缩，将x和y节点直接连在各自祖先节点上，得出和祖先节点的关系dis[x],dis[y],合并祖先节点fx,fy,并通过向量得到fx和fy关系。
void merge(int x,int y,int c)
{
    int fx = find(x);
    int fy = find(y);
    //如果两个节点的父节点相同
    if(fx == fy)
    {
        return;
    }
    f[fx] = fy;
    dis[fx]+=c+dis[y]-dis[x];
}

dist函数：判断两个节点是否存在关系，以及什么关系的函数。先find找各自祖先，如果重合，那么就是有关系，如果不重合，则无关，
返回-1.重合的情况下，二者已通过find路径压缩得到与共同祖先的关系，分别是dis[x],dis[y}。那么x和y之间的关系通过向量的关系可以得到dis[x]-dis[y]

可撤销并查集

后续补上，目前性价比较低。

堆

【概念】：在语法基础课中其实有讲过优先队列，其实优先队列就是一个堆，它可以维护一个集合的最大值（或最小值）。

在做算法题的时候强调过会使用优先级队列就行了，如果想要深入理解数据结构，还需要手动实现堆这种数据结构。

【例题】

优先级队列的经典应用，做题基本上达到这种程度就可以了，接下来就要讲解堆的实现。

堆是一种二叉树，对于每个结点满足：儿子的权值都比自己的权值小。这个性质不断向上传递直到根，就可以保证：根的权值是整棵树中最大的。例如左图是一个大根堆(或者叫大顶堆)，而右图却不是。

手写堆比较繁琐(学过数据结构的同学应该深有体会)，实际做题中几乎不用，但是对于我们理解堆这种数据结构尤为重要，手写堆需要实现以下几个函数：

  1. pushup()将某个点向上更新，一般是将最后一个点向上更新

  2. pushdown()将某个点向下更新，一般将根向下更新

  3. push()插入一个点到堆内

  4. pop()将根结点删除

我们采用数组的方式来存储数据，利用二叉树的性质：2x表示x的左儿子编号，2x+1表示x的右儿子编号。用sz表示结点数量，a[x]表示结点x的权值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//pushup函数
void pushup(int x)
{
    while(x!=1) //只要不是根节点，就一直和父节点比较并更新
    {
        if(a[x]>a[x>>1])
        {
            swap(a[x],a[x>>1]);
            x>>=1;
        }
        else
        {
            break;//如果节点到了某个位置停下了，就跳出
        }
    }
}
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
//pushdown函数
void pushdown(int x)
{
    //如果没有子节点
    if((x<<1)>sz)
    {
        return;
    }
    //如果只有左子节点
    if((x<<1 | 1)>sz )
    {
        if(a[x<<1]>a[x])
        {
            swap(a[x],a[x<<1]);
            pushdown(x<<1);
        }
    }
    else
    {
        //左右子节点都有
        if(a[x] == max({a[x],a[x<<1],a[x<<1|1]}))
        {
            return;
        }
        
        if(a[x<<1]>a[x<<1|1])
        {
            swap(a[x],a[x<<1]);
            pushdown(x<<1);
        }
        else
        {
            swap(a[x],a[x<<1|1]);
            pushdown(x<<1|1);
        }
    }
}
1
2
3
4
5
6
//push函数
void push(int x)
{
    a[++sz] = x;
    pushup(sz);
}
1
2
3
4
5
6
//pop函数
void pop()
{
    a[1] = a[sz--];
    pushdown(1);
}

本部分算法实现与例题解决实现代码链接：点击此处

链表、栈、队列

用数组的方式实现

【概念】：这一部分很多都是数据结构上讲到的东西，读者完全可以翻书查看，这里就不讲解其概念了(其实用C语言实现更加底层，更能理解其数据结构)，读者完全可以只看数据结构中是如何实现的，这里主要讲一些例题，并且用相对底层的方法解答。

单调栈与单调队列

【概念】：单调栈是一个时刻保证内部元素具有单调性质的栈，是一种线性结构。其单调特性使得处理一些问题变得高效，例如求某个点左侧或右侧第一个比它大的点的位置。单调栈的核心思想是：在入栈时逐个删除所有“更差的点”，保持单调性。单调栈一般可分为单调递减栈、单调递增栈、单调不减栈、单调不增栈，需要根据题意来确定。同时，用数组实现的单调栈会比用STL实现的更灵活，可以在里面进行二分，LIS的O(logn)算法就需要用到单调栈+二分。

【概念】：单调队列和单调栈思想类似，是一种基于“双端队列”的数据结构。单调队列内元素具有单调性质，但是大多时候我们会将“下标”作为队列中的元素，而不是“元素值”。一般来说，单调队列的队头是“最优的元素”，后面的是候选元素，每次入队时会将“没有价值的元素”直接删除。

【例题】

用单调队列分别处理出固定长度区间的最大值和最小值，然后用遍历区间[k,n],计算有多少个区间的最值之差<=x,总区间个数为n-k+1,再结合逆元计算即可。

本部分算法实现与例题解决实现代码链接：点击此处

树

同前面的部分，不对数据结构中已经详细介绍的重复介绍，而主要讲解在解题上的应用。

DFS序

【概念】：DFS序是指对一棵树进行DFS时，每个节点被访问到的顺序。DFS序分成两部分：进入该节点的顺序和退出该节点的顺序。

【实现】：

对于DFS中当前节点

  1. 计数+
  2. 进入当前节点的顺序等于当前计数
  3. 向所有子节点继续搜索
  4. 推出当前节点的顺序等于当前计数

示例代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int t,int f)//t表示当前节点编号，f表示父节点编号
{
    in[t] = ++cnt;//in数组存放的是进入改节点的顺序，cnt用来计时
    for(int i = head[t];i;i = edge[i].next)
    {
        if(edge[i].n!=f)
        {
            dfs(edge[i].n,t);
        }
    }
    out[t] = cnt;//out表示退出该节点的顺序，也就是dfs递归完回退部分
}

相关重要性质

  • 某些连续的入序对应树中的节点是一条链；
  • 某节点入序和出序之间对应的节点一定在其子树中。

【例题】

基本上是在原有dfs的基础上加上dfs序的模板就可以解决

本部分算法实现与例题解决实现代码链接：点击此处

LCA

【概念】：LCA(Least Common Ancestors),即最近公共祖先，是指在有根树中，找出某两个结点x和y最近的公共祖先。

【实现】：一种朴素的球阀就是枚举，不断向上找父亲直到两者的父亲相同，但是时间复杂度较高，而我们这里实现的方法是倍增法，

倍增法求LCA本质上是一个dp,类似于之前讲过的ST表。fa[i][j]表示i号节点，往上走2 ^ j所到的结点，当dep[i]-2^j>=1时fa[i][j]有效（假设根节点深度为1)这个fa数组同样用dfs可以求出来，示例代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//当前节点为x,父亲为p
void dfs(int x,int p)
{
    dep[x] = dep[p]+1;//更新dep
    fa[x][0] = p;
    for(int i = 1;i<=20;i++)//循环更新fa
    {
        fa[x][i] = fa[fa[x][i-1]][i-1];
    }
    //向下搜索
    for(const auto &y:g[x])
    {
        //如果y是父亲就跳过
        if(y == p)
        {
            continue;
        }
        dfs(y,x);
    }
}

倍增LCA中还用到了贪心的思想，在具体进行查询LCA(x,y)时，同样是假设x深度更深，然后从大到小枚举j,当fa[x][j]的深度不超过y的深度时，x才能往上跳。也就是说要让x往上跳，但是不能超过y,又要尽可能接近y.跳完之后必然有dep[x]=dep[y],此时如果x=y直接返回，否则再按照同样的方法同时往上跳，保持x!=y,最后一定会停留在LCA(x,y)的下方，返回fa[x][0]即可。

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
int lca(int x,int y)
{
    //如果x深度比y小，就交换x,y，使得x深度更深
    if(dep[x]<dep[y])
    {
        swap(x,y);
    }
    //贪心的思想，i从大到小
    //x向上跳的过程中,保持dep[x]>=dep[y]，深度不能超过y
    for(int i = 20;i>=0;i--)
    {
        if(dep[fa[x][i]]>=dep[y])
        {
            x = fa[x][i];
        }
    }
    if(y == x)
    {
        return x;
    }
    //跳跃过程中，保持x!=y
    for(int i = 20;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

【例题】

本部分算法实现与例题解决实现代码链接：点击此处

树的直径与重心

【概念】：树的直径是树上最长的一条链，当然这条链不唯一，所以一棵树可能有多条直径。直径由两个顶点u,V决定，若有一条直径u,v,则满足以下性质：1. u,v的度数均为1 2. 在以任意一个点为根的树上，u,v中必然存在一个点作为最深的叶子结点。深度就是点距离根节点的距离

【实现】

树的直径有两种求法，第一种方法是“跑两遍fs”，第二种方法是树形dp。我们先讲解第一种方法“跑两遍dfs”。
由于直径端点u,v必然存在一个是深度最深的点，那么我们可以在以任意节点为根的树上跑一次dfs求所有点的深度，选取深度最大的点（可能有多个，任取一个）作为u,然后以u为根再跑一次dfs,此时深度最大的点(可能有多个，任取一个)就是v.于是就可以得到两个端点u,v,从而确定树的直径，其长度就是路径上点的个数，也就等于以u为根的树中的dep[v]。

【例题】

首先，如果k<=C,那么肯定不能进行移动，因为每移动一次，都会付出C的代价，但是最多使得最深的点深度+1，换来k的收益，这是不划算的。当k>C时，随意画一棵树，可以将树划分为三部分。我们认为根的深度为0.换句话说，最优的位置一定是不经过直径的最深的叶子(图中的8或15)，或者v.他们两个的盈利分别是：dep[u]* k+maxdep * (k-c); dpeU[v] * k-dep[v] * c，其中dep[x]表示的是以1为根的树中x的深度，depU[x]表示的以U为根的数中x的深度。

树的重心

【概念】：树的重心是指对于某个点，将其删除后，可以使得剩余联通块的大小的点。也就等价于以某个点为根的树，将根删除后，剩余
的若干棵子树的大小最小。我们先学习重心的若干性质，然后学习其求法（很简单）我们用mss[x]表示x点的所有子树大小的最大值。注意，此时我们认为除去x及其子树剩余的部分也是x的子树。

相关性质

  • 性质一：重心的若干棵子树的大小一定<=n(n为总节点个数),除了重心以外的所有其他点，都必然存在一棵节点个数>n的子树。
  • 性质二：一棵树至多两个重心，如果存在两个重心，则必然相邻，将连接两个重心的边删除后，一定划分为两棵大小相等的树。
  • 性质三：树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。反过来，距离和最小的点一定是重心。
  • 性质四：把两棵树通过一条边相连得到一棵新的树，则新的重心在较大的一棵树一侧的连接点与原重心之间的简单路径上。如果两棵树大小一样，则重心就是两个连接点。

【实现】：非常简单，跑一遍dfs，如果mss[x]<=n/2,则x是重心，反之不是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(int x,int fa)
{
    sz[x] = 1,mss[x] = 0;
    for(const auto &y:g[x])
    {
        if(y == fa)
        {
            continue;
        }
        dfs(y,x);
        sz[x]+=sz[y];
        mss[x] = max(mss[x],sz[y]);
    }
    mss[x] = max(mss[x],n-sz[x]);
    if(mss[x]<=n/2)
    {
        v.push_back(x);
    }
}

本部分算法实现与例题解决实现代码链接：点击此处

树链剖分

【概念】：树链剖分（树剖）用于将树分割成若干条链的形式，以维护树上路径的信息。

重链剖分：重链剖分优先使用重儿子延续当前链，轻儿子则另开新链。重儿子指某节点的所有儿子中，子树大小最大的儿子，其他儿子均为轻儿子。

示例的数据结构如下

1
2
3
4
5
6
7
8
9
10
11
12
13
int ord;//DFS序计数
int rnk[MAXN];//rnk[i]代表入序为i的节点编号

struct NODE
{
    int fa;//当前节点的父节点
    int in;//当前节点的DFS入序
    int out;//当前节点的DFS出序
    int son;//当前节点的重儿子编号
    int top;//当前节点所需链的首节点编号
    int deep;//当前节点在树中的深度
    int size;//当前节点的子树大小
};

【实现】：一般是通过两次dfs实现的，第一次预处理出每个节点的基本信息：深度、子树大小、父节点、重儿子,第二次利用前边预处理出的信息对树进行剖分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//第一次的dfs
void dfs1(int t,int fa) 
{
	node[t].size = 1;
	node[t].fa = fa;
	node[t].deep = node[fa].deep+1;
	for(itn i = head[t];i;i = edge[i].next) 
	{
		if(edge[i].n!=fa)
		{
			dfs1(edge[i].n,t);
			node[t].size() += node[edge[i].n].size();
			if(node[edge[i].n].size> node[node[t].son].size)
			{
				node[t].son = edge[i].n;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//第二次dfs
void dfs2(int t,int fa,int top)
{
    node[t].top = top;
    node[t].in = ++ord;
    rnk[ord] = t;
    if(node[t].son)
    {
        dfs2(node[t].son,t,top);
    }
    for(int i = head[t];i;i = edge[i].next)
    {
        if(edge[i].n != fa && edge[i].n != node[t].son)
        {
            dfs2(edge[i].n,t,edge[i].n);
        }
    }
    node[t].out = ord;
}

相关的性质:每一条链子的dfs序都是连续的

相关的操作

查询两节点的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
int lca(int x,int y)
{
    while(node[x].top!=node[y].top)
    {
        if(node[node[x].top].deep<node[node[y].top].deep)
        {
            swap(x,y);
        }
        x = node[node[x].top].fa;
    }
    return node[x].deep>node[y].deep?y:x;
}

修改两个节点之间的路径信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void update(int x,int y,ll k)
{
    while(node[x].top!=node[y].top)
    {
        if(node[node[x].top].deep<node[node[y].top].deep)
        {
            swap(x,y);
        }
        update_v(1,1,ord,node[node[x].top].in,node[x].in,k);
        x = node[node[x].top].fa;
    }
    if(node[x].deep<node[y].deep)
    {
        swap(x,y);
    }
    update_v(1,1,ord,node[y].in,node[x].in,k);
}

树上差分

【例题引入】：树上差分有什么作用？举个例子，如果题目要求对树上的一段路径进行操作，并询问某个点或某条边被经过的次数，树上差分就可以派上用场了。这就是树上差分的基本操作。树上差分，就是利用差分的性质，对路径上的重要节点进行修改而不是暴力全改），作为其差分数组的值，最后在求值时，利用dfs遍历求出差分数组的前缀和，就可以达到降低复杂度的目的。需要注意的是树上差分需要求LCA，

【例题】：

  • 现在有一棵树，给定条路径，每条路径给定两个端点，两个端点之间的路径所覆盖的点进行染色，问每一个点被染色了多少次。

本问题的实现代码在文件名为TreeDiff.cpp文件中

本部分算法实现与例题解决实现代码链接：点击此处

主席树

【概念】：主席树，全称可持久化权值线段树。所谓可持久化，就是对于每次操作，都保留其历史版本(有点像是git(❁´◡`❁))

【实现】：以下主要讲解其数据结构

  1. 建树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct NODE
{
    //v表示该节点的值,ls与rs表示该节点的左右子节点编号
    int v,ls,rs;
}

struct SEGTREE
{
    //cnt记录节点的数量
    int cnt = 0;
    //root[i]表示第i个版本的根节点
    int root[MAXN<<5];
    NODE node[MAXN<<5];
}
  1. 更新：一、如果当前节点未创建，则创建该节点，复制原节点信息。二、如果左儿子需要更新，则将原来的右儿子作为当前节点的右儿子；如果右儿子需要更新，则将原来的左儿子作为当前节点的左儿子；三、最终进入下一层递归，未创建的儿子节点将在下一层创建
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
//_t表示原节点编号 t表示当前新节点编号 l,r表示当前节点的区间 pos表示待更新的位置，k为更新的目标值
void SETGTREE::update(int _t,int &t,int l.int r.int pos,int k)
{
    if(!t)
    {
        t = cnt++;
        node[t].v = node[_t].v;
    }
    if(l == r)
    {
        node[t].v+=k;
        return;
    }
    int mid = (l+r)>>1;
    if(pos<=mid)
    {
        node[t].rs = node[_t].rs;
        update(node[_t].ls,node[t].ls,l,mid,pos,k);
    }
    else
    {
        node[t].ls = node[_t].ls;
        update(node[_t].rs,node[t].rs,mid+1,r,pos,k);
    }
    node[t].v = node[node[t].ls].v+node[node[t].rs].v;
}
  1. 查询：如果当前节点未创建，则返回0；如果已经找到目标区间，返回该区间的值；如果未找到目标区间，则进入下一层递归。
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
//t为当前节点的编号,_l,_r表示当前节点的区间,l,r表示待查询的区间。
int SEGTREE::getV(int t,int _l,int _r,int l,int r)
{
    if(!t)
    {
        return 0;
    }
    if(l == _l && r == _r)
    {
        return node[t].v;
    }
    int mid = (_l+_r)>>1;
    if(r<=mid)
    {
        return getV(node[t].ls,_l,mid,l,r);
    }
    else if(l>mid)
    {
        return getV(node[t].rs,mid+1,_r,l,r);
    }
    else
    {
        return getV(node[t].ls,_l,mid,l,mid)+getV(node[t].rs,mid+1,_r,mid+1,r);
    }
}

【例题】

本部分算法实现与例题解决实现代码链接：点击此处

伸展树

考的比较少，后续补上，就是平衡二叉查找树的pro max版本，相关操作也基本上是平衡二叉树的。

树状数组

【概念】：树状数组是一种可以 “动态求区间和”的树形数据结构，但并没有真正地构造出边来，所以是“树状”的。基础的树状数组可以实现对区间和的单点修改和区间查询

在学习树状数组之前，我们需要了解lowbit操作，这是一种位运算操作，用于计算出数字的二进制表达史的最低位的1以及后面所有的0。

其实现方法如下

1
2
3
4
int lowbit(int x)
{
    return x & -x;//利用计算机存储整数的特性，因为在计算机中整数都是使用补码存储，原理不需要掌握，只需要会用就行。
}

接下来讲解树状数组的数据结构。其中t[i]存储a数组中一段区间的和，我们定义是让t[i]存储以i结尾，且区间大小为lowbit(i)的区间的和

其公式为ti=∑j=i−lowbit(i)+1iait_i = \sum_{j=i-lowbit(i)+1}^{i}a_i 习惯上叫[i-lowbit(i)+1,i]为i的管辖区间。

怎么进行单点修改？举个例子，假如我要修改a[3]，让他加上x，应该修改t[3],t[4]和t[8]共3个节点，因为这三个节点的管辖区间内都包含3这个节点。但是我们如何从3开始，去找到3,4,8呢？只需要进行+lowbit操作即可（二进制性质）。3 + lowbit(3) = 4

怎么进行区间查询？第一步我们将其拆为两个区间的差，举个例子我们要查询区间[3,7]的和，就要拆分为sum[1,7]-sum[1,2](前缀和的写法) 现在问题变为如何查询[1,k]的和？假如我们要求sum[1,7]，可以知道结果为t[7]+t[6]+t[4]，这是怎么得到的呢？通过-lowbit即可：7 - lowbit(7) = 6,6-lowbit(6) = 4;

【实现】根据以上的分析可以写出以下的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//给a[k]增加x
void update(int k,int x)
{
    for(int i = k;i<=n;i+=lowbit(i))
    {
        t[i]+=x;
    }
}

//返回区间[1,k]的和
int getprefix(int k)
{
    int res = 0;
    for(int i = k;i>0;i-=lowbit(i))
    {
        res+=t[i];
    }
    return res;
}

【例题】：

这一题就是要用树状数组实现

本部分算法实现与例题解决实现代码链接：点击此处

树状数组的二分

【例题引入】：给出三种操作，分别是：在容器中插入一个数；在容器中删除一个数；求出容器中大于a的第k大元素。

树状数组的特点就是对点更新，成段求和，而且常数非常小。原始的树状数组只有两种操作，在某点插入一个数和求1到i的所有数的和。这道题目一共有三种操作，但是实质上其实只有两种：插入和询问。插入操作和删除操作可以视为一种，只不过一个是将标记+1，另一个是-1,而插入的数对应于树状数组的下标，这样就可以在log(n)的时间内完成插入和删除。求大于a的k大元素，可以通过二分枚举答案来完成，枚举的是当前答案在树状数组中的位置，设为m，然后对v[a+1] v[m]求和就是小于等于m的数的个数，这一步可以用树状数组的求和操作来完成，然后根据和k的比较来调整m的位置

实现的代码如下

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 110000;
int tree[MAXN];
int q;

int lowbit(int x)
{
    return x & -x;
}

void add(int pos,int x)
{
    while(pos<MAXN)
    {
        tree[pos]+=x;
        pos+=lowbit(pos);
    }
}

int query(int pos)
{
    int ans = 0;
    while(pos)
    {
        ans+=tree[pos];
        pos-=lowbit(pos);
    }
    return ans;
}

int find(int a,int k) 
{
    int l = a+1,r = MAXN-1;
    int ans = 1;
    while(l<=r)
    {
        int mid = (l+r)>>1;
        if(query(mid)-query(a) == k)
        {
            ans = mid;
        }
        if(query(mid)-query(a)>=k)
        {
            r = mid-1;
        } 
        else
        {
            l = mid+1;
        }
    }
    return ans;
}

int main()
{
    scanf("%d",&q);
    for(int i = 1;i<=q;i++)
    {
        int x,y,z;
        scanf("%d",&x);
        if(x == 0)
        {
            scanf("%d",&y);
            add(y,1);
        }
        else if(x == 1)
        {
            scanf("%d",&y);
            if(query(y)-query(y-1) == 0)
            {
                continue;
            }
            add(y,-1);
        }
        else
        {
            scanf("%d%d",&y,&z);
            printf("%d\n",find(y,z)) ;
        }
    }
    return 0;
}

线段树

【概念】：相关的概念介绍和图形示例可以看这篇博客线段树 从入门到进阶（超清晰，简单易懂）_进阶线段树-CSDN博客 简单来说线段树是一种方便进行区间查询和单点修改的树，前面讲过的树状数组也是类似的实现。

标记永久化

在线段树的区间修改中，一般的处理方法是在待修改区间上使用懒惰标记(LazyFlag)，当访问到该节点时，再将懒惰标记下传。标记永久化是将懒惰标记永远标记在对应区间，在访问到该节点时，不下传标记，而是直接将标记累加，最终计算出该标记对结果的影响。

【实现】

  1. 建树：和前面主席树基本一样,一般的线段树也是这样建立的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void build(int t,int l,int r,int *v)
{
    _l[t] = l;
    -r[t] = r;
    if(l == r)
    {
        _v[t] = v[l];
        return ;
    }
    int mid = (l+r)>>1;
    build(t<<1,l,mid,v);
    build(t<<1|1,mid+1,r,v);
    _v[t] = _v[t<<1]+_v[t<<1|1];
}
  1. 在更新时，对上层区间进行修改，在待修改区间更新标记
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void update(int t,int l,int r,int k)
{
    _v[t]+=k*(r-l+1);
    if(_l[t] == l && _r[t] == r)
    {
        _laz[t]+=k;
        return ;
    }
    int mid = (_l[t]+_r[t])>>1;
    if(r<=mid)
    {
        update(t<<1,l,r,k);
    }
    else if(l>mid)
    {
        update(t<<1|1,l,r,k);
    }
    else
    {
        update(t<<1,l,mid,k);
        update(t<<1|1,mid+1,r,k)
    }
}
  1. 区间查询:在查询时，逐层累加上层区间标记，在带查询区间计算值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int getv(int t,int l,int r,int sum)
{
    if(_l[t] == l&& _r[t] == r)
    {
        return _v[t]+sum*(_r[t]-_l[t]+1);
    }
    int mid = (_l[t]+_r[t])>>1;
    if(r<=mid)
    {
        return getv(t<<1,l,r,sum+_laz[t]);
    }
    else if(l>mid)
    {
        return getv(t<<1|1,l,r,sum+_laz[t]);
    }
    else
    {
        return getv(t<<1,l,mid,sum+_laz[t])+getv(t<<1|1,mid+1,r,sum+_laz[t]);
    }
}

动态开点

【概念】：传统线段树中维护长度为n的区间，需要4n大小的数组。为了节省空间，我们可以不一次性建好树，而是在最初只建立一个根结点代表整个区间。当我们需要访问某个子区间时，才建立代表这个区间的子结点。这就是动态开点。也就是说，动态开点线段树的核心就是：节点只有在被需要的时候才会被创建。

【实现】

  1. 建树

动态开点不需要像普通线段树一样建树，只需要初始化根节点。并且由于动态开点，节点的子节点再是2p和2p+1，而是使用变量ls,rs存储子节点编号。

1
2
3
4
5
//l,r为该节点维护的区间 ls,rs表示该节点的左右子节点编号 n表示该节点的值
struct Tree
{
    int l,r,n,ls,rs;//
}
  1. 修改节点

在更新时，判断当前节点是否存在，如果不存在则开点。以单点修改为例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//其中t为当前节点编号 l,r为当前区间，pos为要修改的位置,n为目标值
void update(int &t,int l,int r,int pos,int n)
{
    if(!t)
    {
        t == ++cnt;
        tree[t].l = l;
        tree[t].r = r;
    }
    if(l == r)
    {
        tree[t].n = n;
        return;
    }
    int mid = (l+r)>>1;
    if(pos<=mid)
    {
        update(tree[t].ls,l,mid,pos,n);
    }
    else
    {
        update(tree[t].rs,mid+1,r,pos,n);
    }
}
  1. 查询

在查询时，判断当前节点是否存在，如果不存在则返回0。以区间查询为例。

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
//其中t为当前节点编号,l,r为当前区间
int getnum(int t,int l,int r)
{
    if(!t)
    {
        return 0;
    }
    if(tree[t].l == l && tree[t].r == r)
    {
        return tree[t].n;
    }
    int mid = (tree[t].l+tree[t].r)>>1;
    if(r<=mid)
    {
        return getnum(tree[t].ls,l,r);
    }
    else if(l > mid)
    {
        return getnum(tree[t].rs,l,r);
    }
    else
    {
        return getnum(tree[t].ls,l,mid)+getnum(tree[t],mid+1,r);
    }
}

【例题】

  • 给定一个长度为N的非负整数序列A，对于前奇数项求中位数 其中输入格式为第一行一个正整数N.第二行N个正整数A1…N。请输出[(N+1)/2]行，第i行为A1...A2i−1A_1...A_{2i-1}的中位数

代码示例如下

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 1e5+7;
const int INF = 1e9+7;

int n;

struct Tree
{
    int l, r, v, num, ls, rs; 
};

int root, cnt;
Tree tre[MAXN << 4];

void update(int &t, int l, int r, int k)
{
    if (!t)
    {
        t = ++cnt;
        tre[t].l = l;
        tre[t].r = r;
        tre[t].num = 0; // 初始化 num
    }
    if (l == r)
    {
        tre[t].v = k;
        tre[t].num++;
        return;
    }
    int mid = (l + r) >> 1;
    if (k <= mid)
    {
        if (!tre[t].ls) tre[t].ls = ++cnt;
        update(tre[t].ls, l, mid, k);
    }
    else
    {
        if (!tre[t].rs) tre[t].rs = ++cnt;
        update(tre[t].rs, mid + 1, r, k);
    }
    tre[t].num = (tre[t].ls ? tre[tre[t].ls].num : 0) + (tre[t].rs ? tre[tre[t].rs].num : 0);
}

// 找中位数函数 
// t表示当前节点 k剩余排名 
int _rank(int t, int k)
{
    if (tre[t].l == tre[t].r)
    {
        return tre[t].v;
    }
    if (tre[tre[t].ls].num >= k)
    {
        return _rank(tre[t].ls, k);
    }
    else
    {
        return _rank(tre[t].rs, k - tre[tre[t].ls].num);
    }
}

int main()
{
    // 初始化
    int x, y;
    cin >> n >> x;
    update(root, 0, INF, x);
    cout << x << endl;

    for (int i = 3; i <= n; i += 2)
    {
        cin >> x >> y;
        update(root, 0, INF, x);
        update(root, 0, INF, y);
        cout << _rank(root, i / 2 + 1) << endl;
    }
    return 0;
}

本部分算法实现与例题解决实现代码链接：点击此处

线段树维护哈希

【例题引入】：给定长度为从的仅由小写英文字母构成的字符串 S= S1,S2,…，Sn，定义它的子串 S[l, r] = Sl, Sl+1, . …, Sr.
有以下两种操作：

  1. ad ch：将字符串中第ad个元素sad赋值为字符ch，给定的ch仅可能是小写英文字母。

  2. l1 r1 12 r2:请你判断字符串 S[l1,r1] 是否等于 S[l2,r2]。

共进行q次操作，对于第二种操作，若两个子串相等则输出YES，否则输出 NO。

如果想要快速匹配对应的字符串是否想等，应该考虑的是用哈希值而不是kmp算法，而要维护区间信息的话最好使用线段树

但是怎么合并两个相邻区间的哈希值呢？比如对于哈希值来说 hA=hB×baselenC+hCh_A = h_B \times base^{len_{C}}+h_C 长度 lenA=lenB+lenClen_A = len_B+len_C可以总结成hA=∑i=1lenASbg+i−1×baselenA−i(modM)h_A = \sum_{i=1}^{len_{A}}S_{bg+i-1}\times base^{len_{A-i}} \pmod M

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll base = 233, mod = 998244353;
const int MAXN = 2000005;
ll bs[MAXN] = {1};
string a;
int n, q;

struct asdf {
    int len;
    ll h;
    asdf operator + (const asdf &c) const {
        return {len + c.len, (h * bs[c.len] + c.h) % mod};
    }
    bool operator == (const asdf &c) const {
        return len == c.len && h == c.h;
    }
};

asdf s[MAXN * 4];

asdf build(int l, int r, int rt) {
    if (l == r) {
        return s[rt] = {1, a[l] - 'a'};
    }
    int mid = (l + r) / 2;
    return s[rt] = build(l, mid, rt * 2) + build(mid + 1, r, rt * 2 + 1);
}

asdf modify(int l, int r, int rt, int ad, char ch) {
    if (l == r) {
        return s[rt] = {1, ch - 'a'};
    }
    int mid = (l + r) / 2;
    if (ad <= mid) {
        return s[rt] = modify(l, mid, rt * 2, ad, ch) + s[rt * 2 + 1];
    } else {
        return s[rt] = s[rt * 2] + modify(mid + 1, r, rt * 2 + 1, ad, ch);
    }
}

asdf query(int l, int r, int rt, int x, int y) {
    if (x <= l && r <= y) {
        return s[rt];
    }
    int mid = (l + r) / 2;
    if (y <= mid) {
        return query(l, mid, rt * 2, x, y);
    }
    if (x > mid) {
        return query(mid + 1, r, rt * 2 + 1, x, y);
    }
    return query(l, mid, rt * 2, x, y) + query(mid + 1, r, rt * 2 + 1, x, y);
}

int main() {
    cin >> n >> a;
    for (int i = 1; i <= n; i++) {
        bs[i] = bs[i - 1] * base % mod;
    }
    a = "!" + a;
    build(1, n, 1);
    for (cin >> q; q--;) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            int ad;
            char ch;
            cin >> ad >> ch;
            modify(1, n, 1, ad, ch);
        } else {
            int l1, r1, l2, r2;
            cin >> l1 >> r1 >> l2 >> r2;
            asdf x = query(1, n, 1, l1, r1);
            asdf y = query(1, n, 1, l2, r2);
            if (x == y) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }
    return 0;
}

分块

【概念】：分块是一种思想，把一个整体划分为若干个小块，对整块整体处理，零散块单独处理。块状数组把一个长度为n的数组划分为a块，每块长度为n/a,对于一次区间操作，对区间内部的整块进行整体的操作，对区间边缘的零散块单独暴力处理，所以分块被称为“优雅的暴力”。

【例题引入】：给出一个长为n的数列，以及n个操作，操作涉及区间加法、单点查值。n<=1e5

实现思路如下

  1. .将一个长度为n的序列分为T块，每一块的长度为n/T。
  2. 分情况处理操作，假设处理的区间为[l,r]
    1. 如果[l,r]这个区间在一个整块里面，就暴力处理
    2. 如果[l,r]跨越了一个整块，那么就整体处理整块，暴力处理零散。s

示例实现代码如下

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
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 110000;
int n, a[MAXN];
int blo, bl[MAXN], v[MAXN], add[MAXN];

void add1(int l, int r, int c) {
    for (int i = l; i <= min(bl[l] * blo, r); i++) {
        v[i] += c;
    }
    if (bl[l] != bl[r]) {
        for (int i = bl[l] + 1; i <= bl[r] - 1; i++) {
            add[i] += c;
        }
    }
    for (int i = (bl[r] - 1) * blo + 1; i <= r; i++) {
        v[i] += c;
    }
}

int main() {
    scanf("%d", &n);
    blo = sqrt(n); // 当成块的大小
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        v[i] = a[i];
    }
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / blo + 1;
    }
    for (int i = 1; i <= n; i++) {
        int op;
        scanf("%d", &op);
        if (op == 0) {
            int l, r, c;
            scanf("%d%d%d", &l, &r, &c);
            add1(l, r, c);
        } else {
            int x;
            scanf("%d", &x);
            printf("%d\n", v[x] + add[bl[x]]);
        }
    }
    return 0;
}

本部分算法实现与例题解决实现代码链接：点击此处

莫队算法

【例题引入】：考虑这样一个问题，有一个含有n个元素的序列，有m次询问，每次询问给出一个区间，要求输出该区间在满足某种性质下的答案。允许离线处理。n个元素，m次询问，每次询问给定一个区间[,r]，要求你输出这个区间内出现的数的种类个数。n,m<=10^5

注意：这个问题的答案满足这样一个性质，已知区间[,r]的答案，可以以0(1)的时间复杂度推出相邻区间的答案。元素个数和询问个数同阶。

莫队算法是怎么解决这类问题的呢，首先，把序列分成若干块。然后，我们注意这类问题有一个很好的性质，我们没有用到，题目注意里说明了相邻区间的答案可以O(1)互推，这启发我们可以将所有询问离线下来，通过合适的处理顺序优化复杂度，而莫队也是这么做的，具体做法是：以区间的左端点所在的块为第一关键字，右端点为第二关键字排序，考虑我们这么做可以得到什么，不难发现，我们可以将所有询问按左端点所在的块分成若干组，然后对于同一组内的，暴力转移

【实现】

示例代码如下

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
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1100000;
int n, m, a[MAXN], cnt[MAXN], ans[MAXN], bel[MAXN], l = 1, r;

struct Node {
    int l, r, id;
} q[MAXN];

bool cmp(Node a, Node b) {
    if (bel[a.l] != bel[b.l]) {
        return bel[a.l] < bel[b.l];
    } else {
        return a.r < b.r;
    }
}

int res;
void add(int x) {
    cnt[a[x]]++;
    if (cnt[a[x]] == 1) {
        ++res;
    }
}

void del(int x) {
    --cnt[a[x]];
    if (cnt[a[x]] == 0) {
        --res;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int blockSize = sqrt(n);
    for (int i = 1; i <= ceil((double)n / blockSize); i++) {
        for (int j = (i - 1) * blockSize + 1; j <= min(n, i * blockSize); j++) {
            bel[j] = i;
        }
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        while (l < q[i].l) {
            del(l++);
        }
        while (l > q[i].l) {
            add(--l);
        }
        while (r < q[i].r) {
            add(++r);
        }
        while (r > q[i].r) {
            del(r--);
        }
        ans[q[i].id] = res;
    }
    for (int i = 1; i <= m; i++) {
        printf("%d ", ans[i]);
    }
    printf("\n");
    return 0;
}

本部分算法实现与例题解决实现代码链接：点击此处

图论

图的基本知识

PS:基本上数据结构里面都有，这里不再赘述。主要讲解图的遍历

DFS

DFS是深度优先搜索，在之前讲搜索的时候就已经接触过DFS了(请参考之前蓝桥杯系列的博客)，现在把DFS融入到具体的图中，而不是隐含的图中。回忆一下DFS的核心思想：“一条路走到黑，走过的路不再走”。一般都是通过递归实现的

1
2
3
4
5
6
7
8
9
10
11
12
13
bitset<N> vis;//vis[i] = ture 说明i点已经走过
void dfs(int x)
{
    vis[x] = true;//打上标记
    for(const auto &y:g[x])
    {
        if(vis[y])
        {
            continue;
            dfs(y);
        }
    }
}

BFS

BFS是宽度优先搜索，其核心思想是： 一层一往外走，每个点只走一次.通常用于求边权想等情况下的最短距离

一般通过队列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bitset<N>vis;//vis[i] = true说明i点已经走过
queue<int>q;//q表示待扩展的点队列
while(q.size()) //只要队列不为空
{
    int x = q.front();
    q.pop();
    if(vis[x])
    {
        continue;
    }
    vis[x] = true;
    for(const auto &y:g[x])
    {
        q.push(y);
    }
}

【例题】

本部分算法实现与例题解决实现代码链接：点击此处

最小生成树

【概念】：最小生成树是指，对于一个连通图，剔除其中一部分边，而保留一部分边，使得剩下的部分构成一棵树，并且这棵树的所有边的权值之和最小。最小生成树所处理的图的边权一般是不相等的，否则意义不大。数据结构中实现的方法就是kruskal算法和prim算法。

最小生成树(MST)的性质如下

  1. MST的边权和是所有生成树中最小的
  2. MST的最大边权是所有生成树中最小的

【实现】

  1. kruskal算法

其核心思想是贪心,1.将所有边按照边权排序。2.从小到大遍历所有边(u,v)，如果(u,v)已经连通就跳过，否则就选中(u,v)，将它俩相连。在第二步中的连通性判断需要用到我们之前学过的并查集。示例代码如下

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
#include <bits/stdc++.h> 
using namespace std;
const int N = 1e5+9;

struct Edge
{
    int x, y, c;
    bool operator < (const Edge &u) const
    {
        return c < u.c; 
    } 
};

int pre[N];
int root(int x)
{
    return pre[x] = (pre[x] == x ? x : root(pre[x]));
}

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<Edge> es;
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        es.push_back({x, y, c}); 
    }
    
    sort(es.begin(), es.end());
    for(int i = 1; i <= n; i++)
    {
        pre[i] = i;  
    }
    int ans = 0;
    for(const auto& e : es)  
    {
        int x = e.x;
        int y = e.y;
        int c = e.c;
        if(root(x) == root(y))
        {
            continue;
        }
        ans = max(ans, c);
        pre[root(x)] = root(y);
    }
    cout << ans << "\n";
}

int main()
{
    solve();
    return 0;
}
  1. Prim算法

Prim算法采用集合的思想，维护一个mst集合，里面存储已经在最小生成树中的点。

  1. 从起点(一般为1号点)出发，每次找出不在mst中且d[最小的点x,d[x]就是选中的那条边的边权。
  2. 将点x加入到mst中，并更新其所有出点y，更新d[y]=min(d[y],w);其中w为x->y的距离
  3. 如果d[y]变小了，就加入到优先队列中作为可能的拓展点。这个mst集合我们用bool数组或bitset来实现即可。
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
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h> 
using namespace std;
const int N = 1e5 + 9;
typedef long long ll; // 添加 long long 的别名

struct Edge
{
    ll x, c;
    bool operator < (const Edge &u) const
    {
        return c == u.c ? x > u.x : c > u.c; // 按 c 从大到小排序，若 c 相同则按 x 从大到小排序
    }
};

vector<Edge> g[N]; // 邻接表存储图
ll d[N]; // 存储每个节点的最小边权
int n, m;

int prim()
{
    priority_queue<Edge> pq;
    bitset<N> vis; 

    fill(d, d + N, LLONG_MAX); // 初始化 d 数组为最大值
    d[1] = 0;
    pq.push({1, d[1]});

    ll res = 0;
    while (!pq.empty())
    {
        int x = pq.top().x;
        pq.pop();
        if (vis[x]) 
        {
            continue;
        }
        vis[x] = true;

        res = max(res, d[x]); // 更新最大边权

        for (const auto &e : g[x]) 
        {
            int y = e.x;
            ll w = e.c;
            if (vis[y])
            {
                continue;
            }
            if (w < d[y])
            {
                d[y] = w;
                pq.push({y, d[y]});
            }
        }
    }
    return res;
}

int main()
{
    cin >> n >> m; // 输入节点数和边数
    for (int i = 1; i <= m; i++)
    {
        ll x, y, w;
        cin >> x >> y >> w;
        g[x].push_back({y, w}); // 无向图，双向加边
        g[y].push_back({x, w});
    }
    cout << prim() << endl; // 输出最大边权
    return 0;
}

【例题】

最小生成树的典型例题，用模板套用即可。我的解法是用kruskal

本部分算法实现与例题解决实现代码链接：点击此处

拓扑排序

【概念】：拓扑排序是一种针对“有向无环图”的算法，用于解决一些有“依赖关系”的问题。拓扑排序保证了当处理到某个点时，其所有的入点都已经处理过了。比如6的节点被2与4节点指向，而通过拓扑排序可以实现在处理6节点之前点2与4都被处理过了。

拓扑排序不一定是“唯一”的，只要满足拓扑关系即可，当然在算法中要保证同样的输入要得到同样的输出。

【实现】：拓扑排序一般借助queue(队列)，使用类似BFS实现，先处理出每个点的入度，这个在读入边的时候处理。图一般用邻接表建立。在枚举边x->y的时候，可以进行状态转移，于是可以和动态规划结合起来。这样的DP也叫做DAG-DP（有向无环图上的动态规划）。状态转移一般只发生在枚举所有边的时候

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
void topo()
{
	queue<int> q;
	//将所有入度为0的点加入到队列中
	for(itn i = 1;i<=n;i++) 
	{
		if(!ind[i])
		{
			q.push(i);
		}
	}
	while(q.size())
	{
		//取出队头的点x,此时它的入度一定为0
		int x = q.front();
		q.pop();
		for(const auto &y:g[x]) 
		{
			//处理边x->y
			ind[y]  --;//处理完成后y的入度--
			if(!ind[y]) 
			{
				q.push(y);//如果y入度为0，说明y的所有入点已经处理完成直接入队 
			}
		}
	}
}

int main()
{
	int m;
	cin>>m;
	while(m--)
	{
		//新增一条u->v的边
		int u,v;
		cin>>u>>v;
		ind[v] ++;//V的入度+1; 
	}
	return 0;
}

【例题】

设状态dp[i]表示i点距离某一个起点的最远距离，状态转移的方向就是拓扑的顺序。假如存在一条边x->y，则有dp[y]=max(dp[y], dp[x] + 1);初始化时dp[i] = 0;

本部分算法实现与例题解决实现代码链接：点击此处

最短路径问题

PS：这个也是数据结构中的知识点，最令学子闻风丧胆的就是Floyd算法和Dijkstra算法

Floyd算法

【概念】：Floyd算法是一种求解 “多源最短路” 问题的算法。在Floyd算法中，图一般用邻接矩阵存储，边权可正可负（但不允许负环），利用动态规划的思想，逐步求解出任意两点之间的最短距离。我们需要准备的东西很少，只要一个d数组：int d[N][N][N]，初始为无穷。d[k][i][j]表示路径（除去起点和终点）中编号最大的点编号<=k的情况下，点到点j的最短距离。但是实际上k这一维度是可以优化掉的，所以直接用int d[N][N];d[i][j]表示考虑到当前情况下，点到点j的最短距离。整体代码非常简单，初学时只需要学会怎么写，怎么用就行，无需过度理解其含义。

核心部分如下

1
2
3
4
5
6
7
8
9
10
11
//注意k作为中转点，必须放在最外层
for(int k = 1;k<=n;k++)
{
    for(int i = 1;i<=n;i++)
    {
        for(itn j = 1;j<=n;j++)
        {
            d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
        }
    }
}

可以看到算法的复杂度较高，所以一般在数据量小的情况下才使用Floyd算法。

【例题】

这个就是Floyd算法题的经典形式

本部分算法实现与例题解决实现代码链接：点击此处

Dijkstra算法

【概念】：Dijkstra算法是一种高效的处理非负边权的“单源最短路”问题的算法，例如求出所有点距离源点1的距离。可以说Dijkstra是最重要的图论算法之一。Dijkstra算法利用了贪心和动态规划的思想，也有多个版本：朴素版、堆优化版，这里直接讲解Dijkstra算法的堆优化版本(priority_queue优先队列实现，最常用，最高效)。

【实现】

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
60
61
62
63
64
65
#include <bits/stdc++.h> 
using namespace std;
const int N = 1e7 + 9;

int d[N]; // d[i] 表示点 i 距离源点的最短距离
bitset<N> vis; // 表示某个点是否走过，按照迪杰斯特拉的贪心思想，第一次走到的时候得到的距离一定是最短距离，所以一个点不能走第二次
vector<pair<int, int>> g[N]; // 邻接表存储图，g[x] 存储从 x 出发的边，pair<y, dw> 表示 x->y 的边权为 dw

struct Node
{
    int x, w; // x 表示点编号，w 表示源点到 x 的最短距离
    bool operator < (const Node &u) const
    {
        return w == u.w ? x < u.x : w > u.w; // 修正：按照 w 升序，在优先级队列中 w 最小的作为堆顶
    }
};

priority_queue<Node> pq;

// 迪杰斯特拉算法的堆优化
void Dijkstra(int st)
{
    fill(d, d + N, INT_MAX); // 初始化 d 数组为最大值
    d[st] = 0; // 源点到源点的距离为 0
    pq.push({st, d[st]}); // 将源点加入优先队列
    while (!pq.empty()) // 只要队列不为空
    {
        auto [x, w] = pq.top();
        pq.pop(); // 取出队头元素
        if (vis[x])
        {
            continue; // 如果走过直接跳过
        }
        vis[x] = true;
        for (const auto &[y, dw] : g[x]) // 遍历从 x 出发的边，x->y 边权为 dw
        {
            if (d[x] + dw < d[y]) // 如果通过 x 到 y 的距离更短
            {
                d[y] = d[x] + dw; // 更新 y 的最短距离
                pq.push({y, d[y]}); // 将 y 加入优先队列
            }
        }
    }
}

int main()
{
    int n, m, st;
    cin >> n >> m >> st; // 输入节点数、边数和源点
    for (int i = 1; i <= m; i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        g[x].push_back({y, w}); // 添加有向边 x->y，边权为 w
    }
    Dijkstra(st); // 调用 Dijkstra 算法
    for (int i = 1; i <= n; i++)
    {
        if (d[i] == INT_MAX)
            cout << "INF "; // 如果不可达，输出 INF
        else
            cout << d[i] << " "; // 输出源点到每个点的最短距离
    }
    return 0;
}

【例题】

本部分算法实现与例题解决实现代码链接：点击此处

BellmanFord算法

【概念】：它可以计算负权图的单源最短路，且可以判断负环，但是时间复杂度较高，是O(nm)。

【实现】：松驰 用这条边去更新源点至到出点的最短路径。用每条边去做松弛操作，进行n-1轮松弛，因为在n个点的图中一条路径最由n-1条边组成，如果n-1轮松弛之后还能松弛，就说明存在负权环，否则就可以得到单源最短路。

代码示例如下

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;

ll h[N];//h[N]表示点0到x的最短距离

bool Bellman_Ford()
{
    //初始化h[]为无穷
    for(int i = 1;i<=n;i++)
    {
        h[i] = inf;
    }
    //h[0] = 0;可以忽略
    
    //一共n个点，所以松弛n-1次，i用于计数
    for(int i = 1;i<n;i++)
    {
        //枚举所有的边,尝试用这条边去松弛点x
        for(const auto &[x,y,w]:es)
        {
            if(h[x] == inf)
            {
                continue;
            }
            //如果可以通过这条边可以松弛
            if(h[x]+w<h[y])
            {
                h[y] = h[x]+w;
            }
        }
    }
    
    //判断是否存在负权环
    for(const auto &[x,y,z]:es)
    {
        if(h[x] == inf)
        {
            continue;
        }
        //如果还有边可以松弛，那么说明存在负环返回false
        if(h[x] + w<h[y])
        {
            return false;
        }
    }
    
    //不存在负环
    return true;
}

Johnson算法

【例题引入】：题目背景是求解稀疏图的全源最短路，点的个数n≤103n \leq 10^3，边数m≤2×103m \leq 2 \times 10^3，典型的稀疏图。

【实现】：

  1. 设置超级源点，用BellmanFord求单源最短路得到“势能”
  2. 在势能帮助下重新设置每条边的权重
  3. 跑n次Dijkstra算法计算出所有点的单源最短路，即得到了全源最短路

re-weight，顾名思义就是重新调整每条边的权重，对于一个图，我们先建立一个"SuperSourceNode”（超级源点），我们用0号节点表示，并且将其与所有点连接起来，边权为0。接下来用Bellman-Ford算法计算出超级源点的单源最短路，这个是很简单的。

好，假如不存在负环，现在我们就得到了一个h[]数组对吧，接下来我们令每条边的权重w(u,v)=w(u,v)+h[u]一h[v]。这样一定可以使得所有边权都为正权，假如w(u,v)<0，那么必然有h[u]+w(u,v)≥h[v]，于是有w(u,v)+h[u]-h[v]≥0。

在此基础上去对每一个点跑Dijkstra算法，即可求得对于每一个点的单源最短路径，而求出来的这个距离d(u,v)实际上是进行了偏移之后的，要还原为真实的距离还要令f(u,v)=d(u,v)-h[u]+h[v]。

注意我们第一次的数组h1，为什么不直接用d来表示呢？因为在物理中的含义是“势能”，我们将一个物理意义挪用到信息学中，可以形象的解释h数组的意义。

我们可以发现，如果存在一条路径：u->x1->x2->…->xk->v，那么就有：

d(u,v)=[w(u,x1)+h[u]−h[x1]]+[w(x1,x2)+h[x1]−h[x2]]+...+[w(xk,v)+h[xk]−h[v]]d(u,v) = [w(u,x_1)+h[u]-h[x_1]]+[w(x_1,x_2)+h[x_1]-h[x_2]]+...+[w(x_k,v)+h[x_k]-h[v]]

稍微做个变换可以得到：

d(u,v)=[w(u,x1)+w(x1,x2)]+...+[w(xk,v)]+[h[u]−h[x1]−h[x2]+...+h[xk]−h[v]]d(u,v) = [w(u,x_1)+w(x_1,x_2)]+...+[w(x_k,v)]+[h[u]-h[x_1]-h[x_2]+...+h[x_k]-h[v]]

d(u,v)=[w(u,x1)+w(x1,x2)]+...+[w(xk,v)]+h[u]−h[v]d(u,v) = [w(u,x_1)+w(x_1,x_2)]+...+[w(x_k,v)]+h[u]-h[v]

d(u,v)=f(u,v)+h[u]−h[v]d(u,v) = f(u,v) + h[u] - h[v]

其中f(u,v)为u,v的真实距离。所以真实距离是我们计算出的d(u,v)-h[u]+h[v]。注意这个真实距离可能是负数，并且如果你要判断两点不存在路径的话，应该判断d和f，就像在dijkstra中一样。

本部分算法实现与例题解决实现代码链接：点击此处

计算几何

点和线之间的关系

【概念】：点在二维平面坐标系下表示为(x,y)，所以一般来说，依据题目条件的不同，我们需要一个pair或者结构体来存储点。具体的类型依据题目而定，一般是int/longlong/double（不建议）

【例题】：常见的出题形式基本上和出数学题类似，只不过要求你用计算机语言实现，所以是否能够理解其中的数学关系至关重要。

判断一个点在直线的哪一边：因为B在直线上，所以对于xb,ybx_b,y_b而言，满足yb=k×xb+by_b = k \times x_b+b 假设A在直线的上方，所以如果过A做
一条竖直向下的直线l2，则一定会存在一个交点D，满足yd=k×xd+by_d = k \times x_d +b 又因为A与D的x坐标相等，A的y坐标更大，所以对于A而言，满足ya>k×xa+by_a>k \times x_a +b

点到线的垂足：

方法一: 假设需要求的点坐标是E(xe,ye)E(x_e,y_e),直线方程Ax+By+C=0Ax+By+C=0,可以直接假设垂足的位置F(xf,yf)F(x_f,y_f), 考虑到原直线ll的斜率是一A/BA/B,则直线EF的斜率是其倒数，也就是B/A。根据已知的条件(过一点和斜率),可以确定直线EF的表达式为Ay−Bx−Aye+Bxe=0Ay-Bx-Ay_{e}+Bx_{e}=0。通过联立两个直线可以获得交点坐标F(xf,yf)F(x_f,y_f)

xf=−ABye−AC+B2xeA2+B2x_f=\frac{-ABy_e-AC+B^2x_e}{A^2+B^2} yf=A2ye−ABxe−BCA2+B2y_f=\frac{A^2y_e-ABx_e-BC}{A^2+B^2}

即为垂足坐标。只需计算E(xe,yex_e,y_e)和F(xf,yfx_f,y_f)的距离即可获得距离。最终得到距离计算公式dis=(Axe+Bye+C)2A2+B2dis = \sqrt{\frac{(Ax_e + By_e + C)^2}{A^2 + B^2}}

方法二: 设直线 L 的方程为 Ax + By + C = 0，点 P 的坐标为 (x₀, y₀)，则点 P 到直线 L 的距离就是：
∣Ax0+By0+C∣A2+B2\frac{|Ax_0+By_0+C|}{\sqrt{A^2+B^2}} 。同理可知，当P (x₀,y₀)，直线的解析式为y=kx+b时，则点P到直线L的距离为：∣kx0−y0+b∣1+k2\frac{|kx_0-y_0+b|}{\sqrt{1+k^2}}

可以先计算出直线斜率 k，再套用第二个公式即可。在计算几何中，斜率是非常重要的，但是当直线 BC 是为竖直时，斜率为无穷，此时斜率法处理，需要用到向量。

方法三： 设点A(x1, y1)，点B(x2, y2)，点C(x3, y3)，求点A到直线BC的距离。我们可以知道，向量AB=(x2-x1, y2-y1)，向量AC=(x3-x1, y3-y1)。
向量叉乘(这是线性代数的知识)可以得到两个向量构成的平行四边形的面积，通过这个关系得到点到直线的距离。 d=∣AB⃗×AC⃗∣∣BC⃗∣d = \frac{|{\vec{AB}} \times {\vec{AC}}|}{|\vec{BC}|}

通俗地讲，这个公式可以转化为(于是就没有考虑斜率)： d=∣(x2−x1)×(y3−y1)−(x3−x1)×(y2−y1)∣(x3−x2)2+(y3−y2)2d = \frac{|(x_2 - x_1) \times (y_3 - y_1) - (x_3 - x_1) \times (y_2 - y_1)|}{\sqrt{(x_3 - x_2)^2 + (y_3 - y_2)^2}}

【例题】：

其实这一题可以直接用向量法秒掉的( •̀ ω •́ )✧

同理可以用数学关系解答，如果读者会使用向量法的话可以更加轻松解决。

也是同理

这一题用向量法求解会很方便，而且可以不用考虑线段斜率为无穷大的情况(当然特殊处理也不是不行)。本题目的实现代码链接如下 点击此处

本部分算法实现与例题解决实现代码链接：点击此处

点和点之间的关系

【概念】：平面上两点距离一般可分为欧几里得距离和曼哈顿距离。现在在二维平面上有两个点(x1,y1),(x2,y2).欧几里得距离：即常见的两点直线连线距离，通过勾股定理计算。d=sqrt(x1-x2)2+(y1-y2)2).曼哈顿距离：两点的x差值的绝对值与y的差值的绝对值之和 即∣x1−x2∣+∣y1−y2∣|x_1-x_2|+|y_1-y_2|，这个距离通常用在整数点上，因为这个距离对于整数点来说计算结果总是整数，而欧几里得距离会产生浮点。当然，在某些时候为了避免浮点误差(比如在C++中让eps = 1e-9,虽然趋近于0，但是不是真正的零)，如果可以不进行开方的情况，我们会使用欧几里得距离的平方来处理。

【实现】：

  1. 求两点的曼哈顿距离，一般用于整数点
1
2
3
4
5
6
int dist(int x1,int y1,int x2,int y2)
{
    int dx = abs(x1-x2);
    int dy = abs(y1-y2);//处理出差值方便编写代码，
    return dx+dy;
}
  1. 求两点欧几里得距离
1
2
3
4
5
6
double dist(double x1,double y1,double x2,double y2)
{
    double dx = x1-x2;
    double dy = y1-y2;
    return sqrt(dx*dx+dy*dy);
}

圆

主要就是求圆的周长和面积，其代码实现很简单。需要注意的在C++中，计算π\pi有一种准确的方法，就是double pi = acos(-1).在Python中可以导入math直接用pi。

圆之间的关系

  1. 两圆相交：dist<r1+r2
  2. 两圆相切：dist = r1+r2.注意如果变量类型是浮点数好的话要设置一定的偏差量eps,以免浮点误差带来的影响。
  3. 两圆相离：dist>r1+r2

三角形

一般三角形的面积——海伦公式

【概念】：已知一个三角形的三条边分别为a,b,c,设p=(a+b+c)/2,三角形面积为s,则有：s=p(p−a)(p−b)(p−c)s = \sqrt{p(p-a)(p-b)(p-c)}

【例题】

注意在使用海伦公式的时候建议使用long double变量名，否则精度不够。

本部分算法实现与例题解决实现代码链接：点击此处

参考

  1. 力扣刷题攻略 读者可以在这里参考刷题。
  2. 蓝桥云课C++班，作者谢子杨