CSP-S 复赛指南(2025 年版)
daiyulong2024 · · 算法·理论
此文章为 daiyulong 独家原创,耗时比较长。部分借助 AI。文章有点长(10 万字左右,21 万字符),请保持耐心。点击下载 PDF 版。可能更好的阅读体验。
:::align{center}
第一章\ \ \ \ 数据结构
第一节\ \ \ \ 线性结构
:::
1.1 【5】双端栈
1.1.1 什么是双端栈?
在理解双端栈之前,我们先回顾一下普通的栈。一个普通的栈,所有元素的插入(入栈,push)和删除(出栈,pop)都只能在同一端——也就是“栈顶”进行。
那么,一个很自然的想法是:如果我们允许栈的两端都可以进行入栈和出栈操作,会怎么样呢?这种两端都具备栈顶功能的数据结构,就是双端栈(Double-Ended Stack)。
想象一个很长的薯片筒,我们不仅可以从上面的开口放入或取出薯片,也可以打开下面的盖子,从底部放入或取出薯片。这个薯片筒就是一个典型的双端栈模型。
然而,在标准的计算机科学数据结构中,“双端栈”这个术语并不常用。其功能被一个更通用、更强大的数据结构——双端队列(Deque)——所完全覆盖。因此,通常我们将双端栈理解为双端队列的一个概念性前身。在接下来的内容中,我们将直接学习功能更全面的双端队列。
1.2 【5】双端队列
1.2.1 什么是双端队列?
双端队列(Double-Ended Queue,简称 Deque) 是一种允许在队列的头部和尾部都能进行插入和删除操作的线性数据结构。它就像一个“全能选手”,集成了栈和队列的特点。
- 如果只使用它的一端进行插入和删除,它就表现得像一个栈。
- 如果在一端进行插入,在另一端进行删除,它就表现得像一个队列。
我们可以将双端队列想象成一个两头都开放的“队伍”。新来的人可以选择排在队伍的最前面,也可以选择排在队伍的最后面;同时,队伍最前面的人可以离开,队伍最后面的人也可以“反悔”直接离开。
1.2.2 双端队列的核心操作
一个标准的双端队列通常支持以下几种核心操作:
push_back: 在队列的尾部插入一个元素。pop_back: 删除队列尾部的元素。push_front: 在队列的头部插入一个元素。pop_front: 删除队列头部的元素。front: 获取队列头部的元素。back: 获取队列尾部的元素。empty: 检查队列是否为空。size: 获取队列中元素的数量。
1.2.3 双端队列的实现
在竞赛中,我们几乎总是使用 C++ 标准模板库(STL)中提供的 std::deque 容器,因为它性能高效且使用方便。但为了深入理解其工作原理,了解如何用数组模拟双端队列是非常有帮助的。
1.2.3.1 数组模拟实现(循环数组)
我们可以使用一个数组来模拟双端队列,并设置两个指针:head 指向队头,tail 指向队尾的下一个位置。
为了避免数组存满后无法再插入元素,我们通常使用循环数组。也就是说,当指针移动到数组的末尾时,它会自动“绕回”到数组的开头。这可以通过取模运算 % 来实现。
- 初始化:
head和tail都指向数组中间的某个位置,以保证两边都有扩展的空间。 push_back: 元素存入tail指向的位置,然后tail向后移动一位(tail = (tail + 1) % N,其中N 是数组大小)。push_front:head向前移动一位(head = (head - 1 + N) % N),然后元素存入head指向的位置。pop_back:tail向前移动一位。pop_front:head向后移动一位。
判断队列为空的条件是 head == tail。判断队列为满的条件是 (tail + 1) % N == head。
这种手写方式虽然能加深理解,但在实际比赛中,除非有特殊要求,否则不推荐,因为容易出错且效率不如 STL。
1.2.4 C++ STL deque 代码模板
使用 STL 中的 deque 非常简单。首先需要包含头文件 <deque>。
#include <iostream>
#include <deque> // 包含 deque 的头文件
using namespace std;
int main() {
// 1. 创建一个 deque
deque<int> dq;
// 2. 在队尾插入元素
dq.push_back(10); // dq: [10]
dq.push_back(20); // dq: [10, 20]
// 3. 在队头插入元素
dq.push_front(5); // dq: [5, 10, 20]
dq.push_front(1); // dq: [1, 5, 10, 20]
// 4. 查看队头和队尾元素
cout << "队头元素是: " << dq.front() << endl; // 输出 1
cout << "队尾元素是: " << dq.back() << endl; // 输出 20
// 5. 获取队列大小
cout << "队列大小是: " << dq.size() << endl; // 输出 4
// 6. 从队头删除元素
dq.pop_front(); // dq: [5, 10, 20]
cout << "pop_front 后队头元素是: " << dq.front() << endl; // 输出 5
// 7. 从队尾删除元素
dq.pop_back(); // dq: [5, 10]
cout << "pop_back 后队尾元素是: " << dq.back() << endl; // 输出 10
// 8. 判断队列是否为空
while (!dq.empty()) {
cout << "当前队头: " << dq.front() << ", 准备出队..." << endl;
dq.pop_front();
}
if (dq.empty()) {
cout << "队列现在为空。" << endl;
}
return 0;
}
双端队列本身的应用场景非常广泛,例如在广度优先搜索(BFS)的某些变体中,以及作为实现其他高级数据结构(如我们即将学习的单调队列)的基础。
1.3 【5】单调队列
1.3.1 什么是单调队列?
单调队列并不是一个 STL 中直接存在的数据结构,而是一种基于双端队列(deque)实现的算法思想和数据结构。
顾名思义,单调队列内部的元素是单调的,即单调递增或单调递减。这个特性使得它非常适合解决一类经典问题:滑动窗口内的最值问题。
例如,给定一个数组和一个固定大小的窗口,当窗口在数组上从左到右滑动时,如何快速求出每个窗口内的最大值或最小值?
1.3.2 单调队列的核心思想
我们以“滑动窗口最大值”为例来剖析单调队列的精髓。
假设有一个窗口,我们需要找到其中的最大值。如果使用暴力法,每次窗口滑动时都遍历一遍窗口内的所有元素,时间复杂度会是
单调队列能将这个过程优化到
这个列表(用双端队列实现)有两个核心规则:
- 规则一(维护单调性):当一个新元素准备从队尾入队时,它会从队尾开始,将所有比它小的元素都“踢”出队列。然后,它自己再入队。这保证了队列中的元素从队头到队尾是单调递减的。
- 规则二(维护窗口范围):队头元素永远是当前窗口内的最大值。当队头元素的位置已经滑出当前窗口的左边界时,就需要将它从队头弹出(
pop_front)。
为什么这个方法是正确的?
思考一下规则一:假设队列中已经有元素 a 和 b(a 在 b 前面),它们都比新来的元素 c 小。由于 c 进入窗口的时间比 a 和 b 都晚,而 c 的值又比它们大。这意味着,在未来的任何包含 c 的窗口中,a 和 b 都不可能成为最大值了(因为有 c "压着"它们)。所以,a 和 b 就成了“没有潜力”的元素,可以被安全地从队列中移除。
这个过程保证了队列里的元素不仅值是单调递减的,它们在原数组中的下标也是单调递增的。队头的元素,就是这个单调队列中最大且最“老”的元素。
1.3.3 算法伪代码(滑动窗口最大值)
假设有一个数组 A 和窗口大小 k。我们用 dq 来存储元素的下标。
// 伪代码:滑动窗口最大值
// 数组 A 的下标从 1 到 n
// 窗口大小为 k
// dq 是一个双端队列,存储的是数组 A 的下标
function slidingWindowMax(A, n, k):
创建一个空的双端队列 dq
创建一个空的结果数组 ans
// 遍历数组 A 的每一个元素
for i from 1 to n:
// 规则一:维护单调性
// 当队列不为空,且队尾下标对应的元素 <= 当前元素 A[i]
while dq is not empty and A[dq.back()] <= A[i]:
dq.pop_back() // 弹出队尾,因为它已经没有机会成为最大值了
// 将当前元素的下标加入队尾
dq.push_back(i)
// 规则二:维护窗口范围
// 如果队头元素的下标已经超出了窗口的左边界
// 当前窗口的范围是 [i - k + 1, i]
if dq.front() <= i - k:
dq.pop_front() // 弹出队头
// 当窗口形成后(即遍历过的元素个数 >= k),开始记录答案
if i >= k:
// 此时队头元素就是当前窗口的最大值
ans.push_back(A[dq.front()])
return ans
注意:单调队列中存储的是元素的下标而不是元素的值。这是因为我们需要根据下标来判断元素是否已经滑出窗口。
1.3.4 算法流程演示
我们用一个具体的例子来走一遍流程。
数组 A = [1, 3, -1, -3, 5, 3, 6, 7],窗口大小 k = 3。
i = 1,A[1] = 1。队列为空,1的下标入队。dq = [1]。i = 2,A[2] = 3。A[2] > A[1],1出队,2入队。dq = [2]。i = 3,A[3] = -1。A[3] < A[2],3直接入队。dq = [2, 3]。- 此时窗口
[1, 3]形成,窗口范围是[1, 3]。队头下标是2 ,在窗口内。最大值为A[2] = 3。输出 3。
- 此时窗口
i = 4,A[4] = -3。A[4] < A[3],4直接入队。dq = [2, 3, 4]。- 窗口
[2, 4]形成。队头下标是2 ,在窗口[2, 4]内。最大值为A[2] = 3。输出 3。
- 窗口
i = 5,A[5] = 5。A[5]比A[4],A[3],A[2]都大,所以4, 3, 2依次出队。5入队。dq = [5]。- 窗口
[3, 5]形成。队头下标是5 ,在窗口[3, 5]内。最大值为A[5] = 5。输出 5。
- 窗口
i = 6,A[6] = 3。A[6] < A[5],6直接入队。dq = [5, 6]。- 窗口
[4, 6]形成。队头下标是5 ,在窗口[4, 6]内。最大值为A[5] = 5。输出 5。
- 窗口
i = 7,A[7] = 6。A[7] > A[6],6出队。A[7] > A[5],5出队。7入队。dq = [7]。- 窗口
[5, 7]形成。队头下标是7 ,在窗口[5, 7]内。最大值为A[7] = 6。输出 6。
- 窗口
i = 8,A[8] = 7。A[8] > A[7],7出队。8入队。dq = [8]。- 窗口
[6, 8]形成。队头下标是8 ,在窗口[6, 8]内。最大值为A[8] = 7。输出 7。
- 窗口
最终输出的最大值序列为:3, 3, 5, 5, 6, 7。
1.3.5 洛谷例题与题解
题目链接: P1886 滑动窗口 /【模板】单调队列
题目描述:
给定一个长度为
输入格式:
第一行包含两个整数
输出格式: 两行。 第一行输出,每个窗口的最小值。 第二行输出,每个窗口的最大值。
题解思路: 这道题是单调队列的模板题。我们需要分别求出滑动窗口的最小值和最大值。
- 求最小值:需要维护一个队头到队尾单调递增的队列。当新元素入队时,把队尾所有比它大的元素都踢出去。
- 求最大值:需要维护一个队头到队尾单调递减的队列。当新元素入队时,把队尾所有比它小的元素都踢出去。(这正是我们上面详细分析的过程)
我们可以写两个函数,或者在一个循环里用两个单调队列分别处理。下面给出的代码是在一个主循环中用两个队列分别完成任务。
1.3.6 C++ 代码实现
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
const int MAXN = 1000005;
int n, k;
int a[MAXN];
deque<int> min_dq, max_dq; // min_dq 存最小值的候选项,max_dq 存最大值的候选项
int main() {
// 读入数据
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
// --- 求滑动窗口最小值 ---
for (int i = 1; i <= n; ++i) {
// 维护单调递增性:新来的元素 a[i] 从队尾把比它大的都赶走
while (!min_dq.empty() && a[min_dq.back()] >= a[i]) {
min_dq.pop_back();
}
min_dq.push_back(i); // 将当前元素下标入队
// 维护窗口范围:检查队头是否已经滑出窗口
if (min_dq.front() <= i - k) {
min_dq.pop_front();
}
// 当窗口形成后(i >= k),输出结果
if (i >= k) {
cout << a[min_dq.front()] << " ";
}
}
cout << endl;
// --- 求滑动窗口最大值 ---
for (int i = 1; i <= n; ++i) {
// 维护单调递减性:新来的元素 a[i] 从队尾把比它小的都赶走
while (!max_dq.empty() && a[max_dq.back()] <= a[i]) {
max_dq.pop_back();
}
max_dq.push_back(i); // 将当前元素下标入队
// 维护窗口范围:检查队头是否已经滑出窗口
if (max_dq.front() <= i - k) {
max_dq.pop_front();
}
// 当窗口形成后(i >= k),输出结果
if (i >= k) {
cout << a[max_dq.front()] << " ";
}
}
cout << endl;
return 0;
}
代码解释:
- 代码中,我们开了两个
deque:min_dq和max_dq,都用来存储数组下标。 - 为了逻辑清晰,我们用了两个独立的循环来分别计算最小值和最大值序列。在实际比赛中,也可以将两个过程合并到一个循环中以提高一点点效率,但逻辑会稍微复杂一些。
- 求最小值部分:
while (!min_dq.empty() && a[min_dq.back()] >= a[i])这句是核心。它保证了min_dq中的元素对应的值是单调递增的。因为如果一个又老(下标小)又大的元素存在,它一定不会是未来任何窗口的最小值,所以可以被淘汰。 - 求最大值部分:
while (!max_dq.empty() && a[max_dq.back()] <= a[i])这句是核心。它保证了max_dq中的元素对应的值是单调递减的。原理同上。 if (dq.front() <= i - k)这句是用来判断队头下标是否过期的。i是当前窗口的右边界,那么左边界就是i - k + 1。如果队头的下标小于等于i - k,说明它已经在窗口之外了,必须出队。if (i >= k)这个判断确保我们只在窗口完全形成之后才开始输出结果。
通过单调队列,我们成功地将每个元素入队一次、出队一次,使得解决滑动窗口最值问题的总时间复杂度从
1.4 【6】优先队列
1.4.1 什么是优先队列?
在学习优先队列之前,我们先回顾一下队列(Queue)这种数据结构。队列是一种“先进先出”(First In First Out, FIFO)的线性表。这就像在食堂排队打饭,先到窗口的人先打到饭,后到的人后打饭。所有元素在队列中的地位都是平等的,唯一的区别就是它们进入队列的顺序。
然而,在现实世界的很多场景中,元素的“地位”并非平等。例如,在医院的急诊室,医生会优先处理病情更危重的病人,而不是严格按照病人挂号的先后顺序。一位心脏病突发的病人,即使比一位只是有点轻微擦伤的病人晚到,也应该被优先救治。
为了在计算机程序中模拟这种“按优先级处理”的场景,一种新的数据结构应运而生,它就是 优先队列(Priority Queue)。
顾名思义,优先队列中的每一个元素都有一个“优先级”。在进行出队操作时,它不再遵循“先进先出”的原则,而是将当前队列中优先级最高(或最低)的元素率先弹出。
我们可以将优先队列与栈(Stack)和普通队列(Queue)进行一个简单的对比:
| 数据结构 | 出队原则 | 生活中的例子 |
|---|---|---|
| 栈 (Stack) | 后进先出 (LIFO) | 叠放的盘子,最后放上去的盘子最先被取用。 |
| 队列 (Queue) | 先进先出 (FIFO) | 排队买票,排在最前面的人最先买到票。 |
| 优先队列 (Priority Queue) | 优先级最高者先出 | 医院急诊室,病情最危重的病人最先被救治。 |
因此,优先队列是一种特殊的队列,它允许我们在任何时候插入一个元素,但只能访问并移除当前优先级最高的元素。
1.1.5 优先队列的实现:二叉堆
优先队列是一个抽象的数据结构概念,它可以通过多种方式实现,例如使用有序数组、链表等。但这些实现在插入或删除操作上效率不高。在信息学竞赛中,实现优先队列最常用、最高效的数据结构是 堆(Heap),特别是 二叉堆(Binary Heap)。
1. 什么是二叉堆?
二叉堆本质上是一棵完全二叉树,并且它需要满足堆属性。
-
完全二叉树:一棵深度为
k 的二叉树,如果它的第1 层到第k-1 层都是满的,并且第k 层的节点都连续地集中在左边,那么它就是一棵完全二叉树。如下图所示,它非常“丰满”且“紧凑”。● / \ ● ● / \ / ● ● ● -
堆属性:堆属性规定了树中父节点和子节点之间的关系。它分为两种:
- 大根堆(Max-Heap):任意一个节点的值都 大于或等于 它的所有子节点的值。因此,根节点一定是整个堆中最大的元素。
- 小根堆(Min-Heap):任意一个节点的值都 小于或等于 它的所有子节点的值。因此,根节点一定是整个堆中最小的元素。
下面的左图是一个大根堆,右图是一个小根堆。
大根堆 小根堆 100 10 / \ / \ 70 60 20 15 / \ / / \ / 20 30 50 40 50 30在信息学竞赛中,当我们提到“优先队列”,通常默认指的是用“大根堆”实现的、取出最大元素的队列。如果需要取出最小元素,则使用“小根堆”。
2. 二叉堆的存储
二叉堆最巧妙的地方在于,尽管它是一棵树,但我们不需要使用复杂的指针来存储它。由于它是完全二叉树,我们可以非常方便地用一个一维数组来表示。
我们将树的节点从上到下、从左到右依次编号,从
节点1 (arr[1])
/ \
节点2(arr[2]) 节点3(arr[3])
/ \ / \
arr[4] arr[5] arr[6] arr[7]
在这种存储方式下,节点之间存在着优美的数学关系:
- 对于数组中下标为
i 的节点,它的父节点的下标是\lfloor i/2 \rfloor 。 - 对于数组中下标为
i 的节点,它的左子节点的下标是2 \times i 。 - 对于数组中下标为
i 的节点,它的右子节点的下标是2 \times i + 1 。
通过这些简单的计算,我们就可以在数组中模拟出树的父子关系,极大地节省了空间和编码复杂度。
1.4.3 堆的核心操作
以大根堆为例,堆的核心操作主要有两个:向上调整(Up-Heapify)和向下调整(Down-Heapify)。这两个操作是维持堆属性的关键。
1. 插入元素 (Push)
当向堆中插入一个新元素时,为了保持完全二叉树的结构,我们首先将这个新元素放在数组的末尾,也就是树的最底层、最右边的位置。
但是,这样做很可能会破坏大根堆的属性(新元素可能比它的父节点大)。因此,我们需要进行向上调整操作。
- 向上调整 (Up-Heapify):将新插入的节点(当前节点)和它的父节点进行比较。如果当前节点的值大于父节点,就交换它们的位置。然后继续将当前节点与新的父节点比较,如此循环,直到当前节点不再大于其父节点,或者它已经到达了堆顶(根节点)的位置。这个过程就像一个“气泡”不断上浮。
伪代码:Up(index)
while (index > 1 and heap[index] > heap[index / 2])
swap(heap[index], heap[index / 2])
index = index / 2
2. 删除堆顶元素 (Pop)
优先队列的 pop 操作总是删除优先级最高的元素,也就是堆顶元素。但是,如果我们直接删除根节点 heap[1],整棵树的结构就遭到了破坏。
正确的做法是:
- 记录下堆顶元素
heap[1]的值,这是我们要返回的结果。 - 将数组的最后一个元素(树的最底层最右边的叶子节点)移动到堆顶的位置。
- 此时,新的堆顶元素很可能小于它的子节点,破坏了大根堆的属性。因此,我们需要进行向下调整。
- 向下调整 (Down-Heapify):将新的堆顶(当前节点)与它的左右子节点中值较大的那个进行比较。如果当前节点的值小于那个较大的子节点,就交换它们的位置。然后继续将当前节点与新的子节点比较,如此循环,直到当前节点的两个子节点都比它小,或者它已经成为了叶子节点。这个过程就像一块“石头”不断下沉。
伪代码:Down(index, size)
while (2 * index <= size) // 只要存在子节点
child_index = 2 * index // 左子节点
// 如果右子节点存在,且比左子节点大,则目标是右子节点
if (child_index + 1 <= size and heap[child_index + 1] > heap[child_index])
child_index = child_index + 1
// 如果当前节点比它的两个孩子都大,则调整结束
if (heap[index] >= heap[child_index])
break
swap(heap[index], heap[child_index])
index = child_index // 继续向下调整
所有这些操作的时间复杂度都与树的高度成正比。一个包含
1.4.4 C++ STL 中的 priority_queue
在实际的编程竞赛中,我们通常不需要手动编写一个堆。C++ 的标准模板库(STL)中已经为我们提供了一个非常方便的容器:std::priority_queue。
要使用它,需要包含头文件 <queue>。
1. 基本用法
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
// 默认是大根堆
priority_queue<int> max_heap;
max_heap.push(30);
max_heap.push(100);
max_heap.push(20);
cout << "大根堆的堆顶元素是: " << max_heap.top() << endl; // 输出 100
max_heap.pop(); // 弹出 100
cout << "弹出后,堆顶元素是: " << max_heap.top() << endl; // 输出 30
return 0;
}
2. 如何定义小根堆
priority_queue 默认是大根堆。如果我们想使用小根堆(用于取出最小值),需要提供额外的模板参数。其完整定义是:
priority_queue<Type, Container, Compare>
Type: 存储的元素类型。Container: 实现底层堆的容器,通常是vector<Type>。Compare: 比较函数对象,用于决定优先级。less<Type>表示大根堆(默认),greater<Type>表示小根堆。
定义一个小根堆的语法如下:
// 定义一个存储 int 类型的小根堆
priority_queue<int, vector<int>, greater<int>> min_heap;
min_heap.push(30);
min_heap.push(100);
min_heap.push(20);
cout << "小根堆的堆顶元素是: " << min_heap.top() << endl; // 输出 20
3. 常用成员函数
| 函数 | 功能描述 | 时间复杂度 |
|---|---|---|
push(x) |
将元素 x 插入队列 |
|
pop() |
弹出队首元素(优先级最高的元素) | |
top() |
返回队首元素的引用 | |
empty() |
判断队列是否为空 | |
size() |
返回队列中元素的个数 |
1.4.5 洛谷例题:P3378 【模板】堆
这道题目是优先队列(堆)的模板题,完美地契合了我们刚刚学习的内容。
题目描述
给定一个序列,你需要支持以下三种操作:
- 插入一个数
x 。- 输出当前序列中最小的数。
- 删除当前序列中最小的数。
分析
题目要求我们维护一个数据集合,并能快速地插入、查询最小值、删除最小值。这正是小根堆的典型应用场景。我们直接使用 C++ STL 中的 priority_queue 就可以轻松解决。
C++ 代码模板
#include <iostream>
#include <queue>
#include <vector>
// 使用 using namespace std 是为了让初学者更容易理解代码
// 在大型项目中,推荐使用 std:: 前缀
using namespace std;
int main() {
// 关闭同步流,加速输入输出
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
// 定义一个小根堆,因为题目要求我们处理最小值
priority_queue<int, vector<int>, greater<int>> min_heap;
for (int i = 1; i <= n; ++i) {
int op;
cin >> op;
if (op == 1) {
int x;
cin >> x;
min_heap.push(x);
} else if (op == 2) {
// top() 操作返回的是最小的元素
cout << min_heap.top() << "\n";
} else { // op == 3
// pop() 操作会删除最小的元素
min_heap.pop();
}
}
return 0;
}
解题思路
- 读取操作总数
N 。 - 创建一个
int类型的小根堆min_heap,因为我们需要对最小值进行操作。 - 循环
N 次,每次读取一个操作指令op。 - 如果
op是1 ,就再读取一个整数x ,并调用min_heap.push(x)将其插入堆中。 - 如果
op是2 ,就调用min_heap.top()获取堆顶(即最小值)并输出。 - 如果
op是3 ,就调用min_heap.pop()删除堆顶元素。
通过这个模板题,我们可以看到 priority_queue 的强大和便捷。它将复杂的堆操作封装起来,让我们能更专注于解决问题本身的逻辑。
1.5 【6】ST表 (Sparse Table)
1.5.1 什么是 ST 表?
ST 表(Sparse Table,稀疏表)是一种用于高效解决 静态区间查询 问题的数据结构。最经典的应用是 区间最值查询(Range Maximum/Minimum Query, RMQ)。
设想这样一个问题:给定一个长度为
- 静态:这个词非常重要,它意味着数组
A 的元素在所有查询过程中都不会被修改。如果数组元素会发生变化,ST 表就不再适用了,需要使用线段树等更复杂的数据结构。 - 区间查询:询问的对象是数组的一个连续子区间。
如果用最朴素的暴力方法,每次询问都遍历一次区间
ST 表通过
1.5.2 ST 表的核心思想:倍增
ST 表的核心思想是 倍增(Binary Lifting)。倍增是一种“以
ST 表正是利用了这一点。它通过预处理,计算出数组中所有“长度为
我们定义一个二维数组 st[i][j],它表示的含义是:从数组下标 st[i][j] = max(A[i], A[i+1], ..., A[i + 2^j - 1])
有了这个定义,我们来看看如何计算 st 数组。
-
基础情况 (Base Case):当
j=0 时,区间的长度是2^0 = 1 。所以st[i][0]就表示从下标i 开始,长度为1 的区间的最大值,这显然就是A[i]本身。st[i][0] = A[i] -
递推关系 (Recurrence Relation):如何计算
st[i][j]呢?一个长度为2^j 的大区间,可以被精确地拆分成两个长度为2^{j-1} 的、相邻的小区间。- 第一个小区间:从
i 开始,长度为2^{j-1} 。它的最大值是st[i][j-1]。 - 第二个小区间:从
i + 2^{j-1} 开始,长度为2^{j-1} 。它的最大值是st[i + 2^(j-1)][j-1]。
整个大区间的最大值,就是这两个小区间最大值的较大者。
于是,我们得到了 ST 表的核心递推公式:
st[i][j] = max(st[i][j-1], st[i + 2^(j-1)][j-1]) - 第一个小区间:从
通过这个公式,我们就可以构建出整个 ST 表。
1.5.3 ST 表的构建(预处理)
构建过程就是填充 st 数组。根据递推公式,我们需要先知道所有长度为
伪代码:Build(A, N)
// 预计算 log2 的值,可以加速查询
log_table[1] = 0
for i from 2 to N:
log_table[i] = log_table[i / 2] + 1
// 初始化 j=0 的情况
for i from 1 to N:
st[i][0] = A[i]
// j 从 1 开始,表示区间长度从 2^1=2 开始
for j from 1 up to log_table[N]:
// i 的范围要保证区间 [i, i + 2^j - 1] 不越界
for i from 1 up to N - (1 << j) + 1:
st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1])
预处理的时间复杂度是
C++ 代码模板 (构建)
// 假设 MAXN 是数组最大长度,LOGN 是 log2(MAXN) 的最大值
const int MAXN = 200005;
const int LOGN = 18; // log2(200005) 约等于 17.6
int a[MAXN];
int st[MAXN][LOGN];
int log_table[MAXN];
void build(int n) {
// 预处理 log_table
log_table[1] = 0;
for (int i = 2; i <= n; i++) {
log_table[i] = log_table[i / 2] + 1;
}
// 初始化 j=0
for (int i = 1; i <= n; i++) {
st[i][0] = a[i];
}
// 递推计算
for (int j = 1; j <= log_table[n]; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
// st[i][j] = max(st[i][j-1], st[i + 2^(j-1)][j-1])
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
1.5.4 ST 表的查询
预处理完成后,如何进行 len = r - l + 1。
我们可以找到一个最大的整数 log_table[len] 快速得到。
现在,我们考虑两个长度为
- 第一个区间:从
l 开始,长度为2^k 。即[l, l+2^k-1] 。它的最大值是st[l][k]。 - 第二个区间:从
r-2^k+1 开始,长度为2^k 。即[r-2^k+1, r] 。它的最大值是st[r - (1 << k) + 1][k]。
由于我们选择的
对于求最大值(或最小值)的操作,一个元素被重复计算多次是不会影响最终结果的(例如 max(a, b, b, c) = max(a, b, c))。这种性质被称为 幂等性(Idempotence)。
因此,区间
查询公式:
query(l, r) = max(st[l][k], st[r - 2^k + 1][k])
其中 k = log_table[r - l + 1]。
由于 k 的计算和数组的访问都是
C++ 代码模板 (查询)
int query(int l, int r) {
int len = r - l + 1;
int k = log_table[len];
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
1.5.5 洛谷例题:P3865 【模板】ST表
这道题是 RMQ 问题的标准模板,用于检验对 ST 表的掌握程度。
题目描述
给定一个长度为
N 的数列,和M 次询问,求出每一次询问的区间[l, r] 中的最大值。
分析 这道题是静态区间最值查询,完全符合 ST 表的应用场景。我们只需要按照上面学习的步骤,先构建 ST 表,然后对于每次询问,调用查询函数即可。
C++ 完整代码
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
const int LOGN = 17; // log2(100005) 约等于 16.6
// st[i][j] 表示从 i 开始,长度为 2^j 的区间的最大值
int st[MAXN][LOGN + 1];
int log_table[MAXN];
// 预处理 log 表
void precompute_log(int n) {
log_table[1] = 0;
for (int i = 2; i <= n; i++) {
log_table[i] = log_table[i / 2] + 1;
}
}
// 构建 ST 表
void build(int n) {
// j=0 的情况已经在主函数读入时处理
for (int j = 1; j <= LOGN; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
// 查询 [l, r] 区间的最大值
int query(int l, int r) {
int k = log_table[r - l + 1];
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int main() {
// 加速输入输出
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
precompute_log(n);
// 读入原始数据,并初始化 st 表 j=0 的情况
for (int i = 1; i <= n; i++) {
cin >> st[i][0];
}
// O(N log N) 预处理
build(n);
// M 次 O(1) 查询
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
cout << query(l, r) << "\n";
}
return 0;
}
解题思路
- 定义好
st数组和log_table数组。 - 在
main函数中,首先读入N 和M 。 - 调用
precompute_log(n)预先计算好所有需要的\log_2 值,避免在查询时重复计算。 - 读入
N 个数,直接存入st[i][0],完成 ST 表的基础情况初始化。 - 调用
build(n)函数,完成整个 ST 表的预处理。 - 循环
M 次,每次读入查询区间[l, r] ,调用query(l, r)函数计算并输出结果。
ST 表是一个优雅且高效的数据结构,它将倍增思想和动态规划的预处理结合起来,是信息学竞赛中解决静态 RMQ 问题的有力武器。
:::align{center}
第二节\ \ \ \ 集合与特殊树
:::
2.1 【6】并查集
2.1.1 什么是并查集?
并查集(Disjoint Set Union, DSU)是一种非常精妙的树形数据结构,主要用于处理一些不相交集合(Disjoint Sets)的合并(Union)及查询(Find)问题。
想象一下,在江湖中有许多侠客,一开始每个人都自成一派。然后,一些侠客之间会结成联盟,形成一个个小门派。随着时间的推移,一些小门派之间又会合并,形成更大的门派。在这个过程中,我们经常需要关心两个问题:
那么,AVL 树的性质可以描述为:对于树中的任意节点
node,其平衡因子的取值只能是 -1、0 或 1。
- 当平衡因子为 -1 时,说明左子树比右子树高 1。
- 当平衡因子为 0 时,说明左右子树等高。
- 当平衡因子为 1 时,说明右子树比左子树高 1。
如果一个节点的平衡因子的绝对值变成了 2,我们就称这个节点失衡(Unbalanced),并且需要通过旋转操作来修复它。
2.7.1.2 核心操作:旋转
旋转是所有平衡树调整形态的原子操作。它可以在不破坏二叉搜索树性质的前提下,改变节点的父子关系,从而降低树的高度。旋转分为两种:左旋(Left Rotation) 和 右旋(Right Rotation)。
1. 右旋 (Right Rotation)
假设节点 p 是失衡节点,它的左孩子是 c。对 p 进行右旋,意味着将 c “提”上来成为新的根节点,而 p 则“降”下去成为 c 的右孩子。
-
操作过程(以
p为轴心右旋):p的左孩子c成为新的根。p成为c的右孩子。c原来的右子树,现在成为p的左子树。
-
性质观察:
- 旋转前,中序遍历的结果是
T1 -> c -> T2 -> p -> T3。 - 旋转后,中序遍历的结果是
T1 -> c -> T2 -> p -> T3。 - 中序遍历序列不变,所以它仍然是一棵二叉搜索树!但是树的结构改变了,高度也可能随之改变。
- 旋转前,中序遍历的结果是
2. 左旋 (Left Rotation)
左旋是右旋的镜像操作。假设节点 p 是失衡节点,它的右孩子是 c。对 p 进行左旋,意味着将 c “提”上来,p “降”下去成为 c 的左孩子。
- 操作过程(以
p为轴心左旋):p的右孩子c成为新的根。p成为c的左孩子。c原来的左子树(上图中的T2)现在成为p的右子树。
2.7.1.3 AVL 树的四种失衡情况与调整
当我们在 AVL 树中插入一个新节点后,可能会导致从插入点到根节点的路径上某些祖先节点的平衡因子绝对值变为 2。我们只需要找到离插入点最近的那个失衡节点,对它进行调整即可。失衡的情况可以分为四种:
1. LL 型(左-左)
- 成因:在新节点插入到失衡节点
p的左子树c的左子树中,导致p失衡。 - 调整:对失衡节点
p进行一次右旋。
2. RR 型(右-右)
- 成因:在新节点插入到失衡节点
p的右子树c的右子树中,导致p失衡。 - 调整:对失衡节点
p进行一次左旋。
3. LR 型(左-右)
- 成因:在新节点插入到失衡节点
p的左子树c的右子树中,导致p失衡。 - 调整:这种稍微复杂,需要两次旋转。
- 先对
p的左孩子c进行一次左旋。(把它变成 LL 型) - 再对
p本身进行一次右旋。
- 先对
4. RL 型(右-左)
- 成因:在新节点插入到失衡节点
p的右子树c的左子树中,导致p失衡。 - 调整:与 LR 型对称。
- 先对
p的右孩子c进行一次右旋。(把它变成 RR 型) - 再对
p本身进行一次左旋。
- 先对
2.7.1.4 AVL 树的伪代码与实现
节点结构
struct Node {
int val; // 节点的值
int height; // 以当前节点为根的子树的高度
Node *left, *right; // 左右孩子指针
};
插入操作伪代码
function insert(node, value):
if node is null:
return create_new_node(value)
if value < node.val:
node.left = insert(node.left, value)
else if value > node.val:
node.right = insert(node.right, value)
else: // 值已存在,不插入
return node
// 1. 更新高度
update_height(node)
// 2. 获取平衡因子,检查是否失衡
balance = get_balance_factor(node)
// 3. 如果失衡,进行旋转调整 (四种情况)
// LL Case
if balance < -1 and value < node.left.val:
return right_rotate(node)
// RR Case
if balance > 1 and value > node.right.val:
return left_rotate(node)
// LR Case
if balance < -1 and value > node.left.val:
node.left = left_rotate(node.left)
return right_rotate(node)
// RL Case
if balance > 1 and value < node.right.val:
node.right = right_rotate(node.right)
return left_rotate(node)
// 4. 如果未失衡,直接返回当前节点
return node
2.7.1.5 优缺点分析
- 优点:由于其严格的平衡限制,AVL 树的高度被严格控制在
O(\log n) ,因此其查找性能非常稳定且高效。 - 缺点:为了维持这种严格的平衡,插入和删除操作可能需要进行多次旋转(尽管最多两次),导致这些操作的常数因子较大,实现也相对复杂。
在实际应用和竞赛中,由于其实现的复杂性,AVL 树并不如接下来要讲的 Treap 和 Splay 常用。但理解它的平衡思想是学习其他平衡树的基础。
2.7.2 Treap
Treap 是一种非常有趣的平衡树,它的名字是 Tree (树) 和 Heap (堆) 的合成词。它巧妙地利用了“随机化”来大概率地维持树的平衡,代码实现比 AVL 树简单得多。
2.7.2.1 Treap 的双重性质
Treap 的每个节点除了存储一个键值 val 之外,还额外存储一个随机生成的优先级 priority。Treap 这棵树需要同时满足两个性质:
- 关于键值
val,它是一棵二叉搜索树(BST):- 对于任意节点,其左子树中所有节点的
val都小于该节点的val。 - 其右子树中所有节点的
val都大于该节点的val。
- 对于任意节点,其左子树中所有节点的
- 关于优先级
priority,它是一个大根堆(Max-Heap):- 对于任意节点,其
priority都大于等于它左右孩子的priority。 - 即父节点的优先级总是最高的。
- 对于任意节点,其
一个重要的结论:当一棵树上所有节点的键值 val 和优先级 priority 都确定后,如果这棵树同时满足 BST 和堆的性质,那么它的形态是唯一确定的。
正是因为优先级是随机赋予的,我们就可以认为这棵树的结构是“随机”的,从而在概率上期望树的高度为
2.7.2.2 Treap 的核心操作
Treap 维持平衡的方式完全依赖于旋转操作,但其触发旋转的条件比 AVL 树简单得多:当且仅当一个节点的优先级小于其子节点的优先级时(即违反了堆性质),才需要进行旋转。
1. 插入 (Insert)
- 第一步:忽略优先级,像普通二叉搜索树一样,根据键值
val找到合适的位置,插入一个新节点。为这个新节点随机赋予一个优先级priority。 - 第二步:检查新插入的节点是否满足堆性质。如果它的优先级比其父节点大,就违反了堆性质。此时,通过旋转来修复它。
- 如果该节点是其父节点的左孩子,就对父节点进行右旋。
- 如果该节点是其父节点的右孩子,就对父节点进行左旋。
- 这个过程就像在大根堆中插入元素后的“上浮”操作,不断旋转,直到该节点的父节点优先级比它大,或者它自己成为根节点为止。
2. 删除 (Delete)
删除一个节点比插入稍微麻烦一点,因为我们不能直接删除一个内部节点,那样会破坏树的结构。
- 第一步:在树中找到要删除的节点。
- 第二步:通过旋转,将这个要删除的节点“下沉”到叶子节点的位置。
- 比较其左右孩子的优先级。选择优先级较大的那个孩子进行旋转。
- 如果左孩子优先级大,就对当前节点进行右旋(把它作为右孩子换下去)。
- 如果右孩子优先级大,就对当前节点进行左旋(把它作为左孩子换下去)。
- 重复这个过程,直到要删除的节点成为一个叶子节点。
- 第三步:当要删除的节点成为叶子节点后,直接删除它。
2.7.2.3 Treap 的 C++ 实现模板
Treap 的实现通常采用指针方式,并且经常会把左右孩子 lson, rson 写成一个数组 ch[2],这样在旋转时代码可以写得更简洁。
#include <iostream>
#include <cstdlib> // For rand()
#include <ctime> // For srand()
using namespace std;
// 建议在程序开始时调用 srand(time(0)) 来初始化随机数种子
struct Node {
int val; // BST 的键值
int priority; // 堆的优先级
int size; // 子树大小(用于查询排名等)
Node *ch[2]; // ch[0] 是左孩子, ch[1] 是右孩子
Node(int v) {
val = v;
priority = rand();
size = 1;
ch[0] = ch[1] = nullptr;
}
};
// 更新节点 size 信息
void pushup(Node* p) {
p->size = 1;
if (p->ch[0]) p->size += p->ch[0]->size;
if (p->ch[1]) p->size += p->ch[1]->size;
}
// 旋转操作 (d=0 右旋, d=1 左旋)
// d=0: 将 p 的左孩子(ch[0]) 旋上来
// d=1: 将 p 的右孩子(ch[1]) 旋上来
void rotate(Node* &p, int d) {
Node* k = p->ch[d^1]; // d=0, k=p->ch[1]; d=1, k=p->ch[0]
p->ch[d^1] = k->ch[d];
k->ch[d] = p;
pushup(p);
pushup(k);
p = k;
}
// 插入操作
void insert(Node* &p, int val) {
if (!p) {
p = new Node(val);
return;
}
if (val == p->val) return; // 假设不插入重复值
int d = (val > p->val); // d=0 插入左子树, d=1 插入右子树
insert(p->ch[d], val);
// 维护堆性质
if (p->ch[d]->priority > p->priority) {
rotate(p, d^1); // 如果右孩子(d=1)优先级大,需要左旋(d^1=0)
// 如果左孩子(d=0)优先级大,需要右旋(d^1=1)
// 这里有个小技巧,可以思考一下
}
pushup(p);
}
// 删除操作
void remove(Node* &p, int val) {
if (!p) return;
if (val < p->val) {
remove(p->ch[0], val);
} else if (val > p->val) {
remove(p->ch[1], val);
} else { // 找到了要删除的节点 p
if (!p->ch[0] && !p->ch[1]) { // 叶子节点
delete p;
p = nullptr;
} else if (!p->ch[0]) { // 只有右孩子
Node* k = p;
p = p->ch[1];
delete k;
} else if (!p->ch[1]) { // 只有左孩子
Node* k = p;
p = p->ch[0];
delete k;
} else { // 有两个孩子
int d = (p->ch[0]->priority < p->ch[1]->priority); // 哪个孩子优先级大,就把它旋上来
rotate(p, d);
remove(p->ch[d], val); // 继续在旋转下去的子树中删除
}
}
if (p) pushup(p);
}
注意:rotate(p, d) 中 d 的含义是“哪个方向的孩子不动”。例如 d=0 时,p 的左孩子 p->ch[0] 和右子树 p->ch[1]->ch[1] 保持父子关系不变,所以是右旋。思考一下 d 和 d^1 的对应关系,这是 Treap 代码简洁的关键。
2.7.2.4 例题讲解:【洛谷 P3369】【模板】普通平衡树
这道题要求我们实现一个数据结构,支持插入、删除、查询排名、查询数值、找前驱、找后继等操作。这是平衡树的经典模板题,用 Treap 来实现非常合适。
除了上面讲的插入和删除,我们还需要实现其他几个查询功能。这些功能都利用了二叉搜索树的性质以及我们维护的 size 信息。
- 查询 x 的排名:从根节点开始,如果 x 小于当前节点值,就往左走;如果 x 大于当前节点值,答案加上左子树的
size和 1(当前节点),然后往右走;如果相等,答案就加上左子树的size再加 1。 - 查询排名为 k 的数:从根节点开始,比较 k 和左子树的
size。如果 k 小于等于左子树size,就往左走;如果 k 大于左子树size+ 1,就从 k 中减去左子树size+ 1,然后往右走;否则,当前节点就是答案。 - 找前驱:比 x 小的数中最大的那个。在树中查找 x,沿途经过的节点值如果小于 x,就可能是答案,记录下来。最后一次记录的值就是前驱。
- 找后继:比 x 大的数中最小的那个。与找前驱类似。
完整的题解代码较长,但核心就是上面 Treap 模板的扩展。Treap 代码短、思路清晰,是竞赛中性价比非常高的选择。
2.7.3 Splay 树
Splay 树,又称伸展树,是另一种高效的平衡二叉搜索树。它与 AVL 和 Treap 的思想完全不同。它不通过特定的“平衡因子”或“优先级”来维持平衡,而是遵循一个非常朴素的原则:每次访问一个节点后,都通过一系列旋转将这个节点移动到树的根部。
这个核心操作被称为伸展(Splay)。
2.7.3.1 Splay 的神奇之处:局部性原理
Splay 树的设计基于一个经验性的假设,叫做局部性原理(Locality of Reference)。这个原理指的是,在很多应用场景中,刚刚被访问过的数据,在接下来有很大概率会再次被访问。
Splay 树将最近访问的节点移动到根,就是为了让下一次对它的访问变得极快(
均摊复杂度:简单来说,虽然某一次操作可能很慢,但它会为后续的操作“铺路”,使得后续操作变快。将一系列操作的总时间除以操作次数,得到的平均时间复杂度是稳定的。Splay 树的所有操作的均摊时间复杂度都是
O(\log n) 。对于初学者,我们不需要深入证明,只需记住这个结论。
2.7.3.2 核心操作:伸展 (Splay)
伸展操作就是将指定节点 x 旋转到根。这个过程不是简单地一路单旋上去,否则仍然可能形成链。Splay 的精髓在于它的双层旋转。假设要伸展的节点是 x,它的父亲是 p,祖父是 g。根据 x, p, g 的相对位置,分为三种情况:
1. Zig (单旋)
- 情况:
p就是根节点。 - 操作:如果
x是p的左孩子,就右旋p;如果x是p的右孩子,就左旋p。
2. Zig-Zig (一字型)
- 情况:
x和p都是左孩子(或都是右孩子)。 - 操作:先旋转父亲
p,再旋转自己x。例如,g-p-x是一条左斜链,那么先右旋g,再右旋p。
3. Zig-Zag (之字型)
- 情况:
x是右孩子而p是左孩子(或反之)。 - 操作:连续旋转自己
x两次。例如,x是p的右孩子,p是g的左孩子。那么先对p左旋,再对g右旋。
Splay 操作流程:只要 x 还不是根节点,就反复执行上述三种情况之一,直到 x 成为根。
2.7.3.3 Splay 树的基本操作
Splay 树的所有操作都围绕 splay 函数展开。
-
插入 (Insert):
- 像普通 BST 一样插入新节点。
- 对新插入的节点执行
splay操作,将其移动到根。
-
查找 (Find):
- 像普通 BST 一样查找目标节点。
- 如果找到了,对该节点执行
splay操作。如果没找到,对最后访问到的那个节点执行splay操作。
-
删除 (Delete):
- 首先查找要删除的值,并将其
splay到根。假设现在的根是x。 - 此时
x的左子树中的所有值都比x小,右子树所有值都比x大。 - 将
x的左子树和右子树断开。 - 在
x的左子树中,找到值最大的那个节点(也就是左子树的根一直往右走到底),我们称之为max_left。 - 对
max_left执行splay操作,使其成为左子树的新根。 - 此时,
max_left一定没有右孩子。将x原来的右子树,连接为max_left的右孩子。 - 最后,删除节点
x,新的树根就是max_left。
- 首先查找要删除的值,并将其
2.7.3.4 Splay 树的 C++ 实现模板
Splay 树的实现通常不用递归,而是用 while 循环自底向上进行旋转,这样更高效。
#include <iostream>
#include <algorithm>
using namespace std;
struct Node {
int val;
int size;
Node *ch[2]; // ch[0] left, ch[1] right
Node *fa; // parent pointer
Node(int v, Node* f) {
val = v;
size = 1;
ch[0] = ch[1] = nullptr;
fa = f;
}
};
Node* root;
void pushup(Node* p) {
p->size = 1;
if (p->ch[0]) p->size += p->ch[0]->size;
if (p->ch[1]) p->size += p->ch[1]->size;
}
// d=0: 左孩子, d=1: 右孩子
// get(x) 判断 x 是其父节点的哪个孩子
int get(Node* p) {
return p == p->fa->ch[1];
}
void rotate(Node* p) {
Node *f = p->fa, *gf = f->fa;
int d = get(p);
// 连接 gf 和 p
if (gf) gf->ch[get(f)] = p;
p->fa = gf;
// 连接 f 和 p 的子树
f->ch[d] = p->ch[d^1];
if (p->ch[d^1]) p->ch[d^1]->fa = f;
// 连接 p 和 f
p->ch[d^1] = f;
f->fa = p;
pushup(f);
pushup(p);
}
void splay(Node* p, Node* goal = nullptr) {
while (p->fa != goal) {
Node *f = p->fa, *gf = f->fa;
if (gf != goal) { // 如果有祖父节点,判断 zig-zig or zig-zag
if (get(p) == get(f)) { // zig-zig
rotate(f);
} else { // zig-zag
rotate(p);
}
}
rotate(p);
}
if (goal == nullptr) { // 如果目标是根,更新 root 指针
root = p;
}
}
注意:这里的 Splay 代码是一个更常见的竞赛模板写法。splay(p, goal) 的意思是将 p 旋转到 goal 的下方。当 goal 为 nullptr 时,就是将 p 旋转到根。这种写法在处理区间操作时非常有用。
2.7.3.5 Splay 的应用
Splay 树非常灵活,除了能完成普通平衡树的所有操作外,它的 splay 操作能方便地将任意节点置于根,这使得它在处理需要区间合并、分裂等操作的场景时特别强大。例如,文艺平衡树(洛谷 P3391)就是 Splay 的一个经典应用,通过 Splay 维护一个序列,可以实现区间翻转等复杂操作。
2.7.3.6 总结与对比
| 特性 | AVL 树 | Treap | Splay 树 |
|---|---|---|---|
| 平衡策略 | 严格高度限制(平衡因子) | 随机优先级(堆性质) | 访问后伸展到根 |
| 时间复杂度 | 所有操作严格 |
所有操作期望 |
所有操作均摊 |
| 实现难度 | 复杂,情况讨论多 | 简单,代码短小 | 中等,旋转逻辑需要清晰 |
| 空间开销 | 每个节点需存 height |
每个节点需存 priority |
每个节点需存 parent 指针 |
| 常数 | 较大(旋转频繁) | 较小 | 较小(但splay操作长) |
| 适用场景 | 查找密集,修改较少 | 绝大多数平衡树场景 | 有区间操作,或数据访问有局部性 |
对于初学者和信息学竞赛选手来说,Treap 是最需要优先掌握的平衡树,因为它足够应对大多数模板题,且代码简单不易出错。Splay 树功能更强大,是进阶选手必须掌握的利器。而 AVL 树,则更多地作为理解平衡思想的经典案例出现在数据结构的教材中。
:::align{center}
第三节\ \ \ \ 哈希表
:::
在信息学竞赛中,经常会遇到需要在庞大的数据集中快速查找、统计或判断某个元素是否存在的问题。如果数据范围非常大,例如,需要判断一个范围在 1 到 10 亿之间的数字是否出现过,直接开一个大小为 10 亿的数组来记录是不现实的,因为它会占用巨量的内存空间。
为了解决这类问题,信息学家们设计了一种巧妙的工具——哈希算法(Hash Algorithm)。
哈希算法的核心思想是映射与压缩。它可以将任意长度的输入(可能是一个巨大的数字、一个长字符串,甚至更复杂的数据结构),通过一个特定的哈希函数(Hash Function),转换成一个固定长度的、通常是较小的数值,这个数值被称为哈希值(Hash Value)。
可以把哈希函数想象成一个神奇的“搅拌机”。无论你放进去的是什么水果(苹果、香蕉、西瓜),它都能输出一杯固定大小的果汁。即使是两种非常相似的水果,榨出来的果汁也可能看起来天差地别。哈希算法的目标就是让不同的输入(不同的水果)能够生成不同的哈希值(不同口味的果汁)。通过比较哈希值,我们就能快速地判断原始输入是否可能相同。
本章将详细介绍数值和字符串的哈希函数构造方法,以及一个不可避免的问题——哈希冲突及其处理方法。
3.1 【5】数值哈希函数构造
3.1.1 什么是数值哈希函数?
数值哈希函数处理的是数字。它的任务是,将一个取值范围可能非常大的整数,映射到一个相对较小的、可以用作数组下标的范围内。
例如,班级里有 50 名学生,他们的学号可能是从 20240001 到 20249999 之间任意的 50 个数字。如果我们想快速查询某个学号的学生是否存在,可以开一个大小为 10000 的数组,但这太浪费空间了。我们希望将这些巨大的学号,映射到 0 到 49(或者 1 到 50)这样的小范围里,方便我们用一个大小为 50 的数组来存储信息。这个将大学号映射到小下标的“规则”,就是数值哈希函数。
一个好的数值哈希函数应该具备两个特点:
- 计算简单:函数本身的计算过程不能太复杂,否则就失去了“快速”的意义。
- 分布均匀:应尽可能地将不同的数字映射到不同的位置,减少“多个不同学号被映射到同一个位置”的情况。这种情况被称为哈希冲突(Hash Collision)。
3.1.2 常见的数值哈希构造方法
在各种构造方法中,除留余数法(Division Method) 是最常用也是最简单的一种。
它的思想非常直接:选择一个合适的正整数
这里的 20240321 的哈希值就是 0 到 99 的范围内。
如何选择
其中,
如何选择
为了让哈希函数的效果更好,即冲突概率更低,
- 基数
P :应该选择一个质数,且这个质数要大于所有可能出现的字符的种类数。例如,如果字符串只包含小写字母,那么字符种类是 26。我们可以选择一个比 26 大的质数,比如 131 或者 13331。这些数字在实践中被证明效果很好。 - 模数
M :应该选择一个足够大的质数,以减小哈希冲突的概率。这个数的大小通常要能存放在一个long long类型的变量中。常用的模数有10^9+7 、10^9+9 、998244353 等。
一个特别的技巧:自然溢出
在信息学竞赛中,为了追求极致的效率和代码的简洁性,选手们常常使用一种被称为“自然溢出”的技巧。具体做法是,选择一个 unsigned long long 类型来存储哈希值,它的取值范围是 unsigned long long 的最大值时,它会自动“溢出”,效果等价于对
3.2.3 快速计算子串哈希:前缀哈希法
如果我们需要频繁计算一个长字符串中任意子串的哈希值,每次都从头遍历子串来计算会非常慢。这时,我们可以使用前缀哈希法来优化。
我们预处理出两个数组:
h数组:h[i]存储字符串S 前i 个字符组成的前缀S[1..i] 的哈希值。p数组:p[i]存储P^i \pmod M 的值。
h 数组的递推公式为:
现在,假设我们想求子串
- 前缀
S[1..r] 的哈希值是h[r] 。 - 前缀
S[1..l-1] 的哈希值是h[l-1] 。
观察哈希值的计算公式,
通过移项,我们得到计算子串
注意,在计算减法取模时,结果可能会是负数。为了保证结果非负,我们应该使用 (a - b % M + M) % M 的形式。如果使用 unsigned long long 自然溢出,则可以直接相减。
3.2.4 伪代码与C++代码模板
算法伪代码:
// --- 预处理 ---
function Precompute_Hash(S, n, P, M):
h[0] = 0
p[0] = 1
for i from 1 to n:
p[i] = (p[i-1] * P) mod M
h[i] = (h[i-1] * P + S[i]) mod M
// --- 查询子串哈希 ---
function Get_Substring_Hash(l, r):
// 计算 S[l..r] 的哈希值
len = r - l + 1
hash_val = (h[r] - h[l-1] * p[len] % M + M) % M
return hash_val
C++ 代码模板 (采用 unsigned long long 自然溢出):
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long ULL;
const int N = 1000010; // 字符串最大长度
const int P = 131; // 基数 P
ULL h[N]; // h[i] 存储字符串前 i 个字符的哈希值
ULL p[N]; // p[i] 存储 P 的 i 次方
/**
* @brief 计算字符串 s 从下标 l 到 r 的子串的哈希值
* @param l 子串左端点 (1-based)
* @param r 子串右端点 (1-based)
* @return 子串的哈希值
*/
ULL get_hash(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
string s;
cin >> s;
int n = s.length();
// 预处理 p 数组和 h 数组
p[0] = 1;
for (int i = 1; i <= n; ++i) {
p[i] = p[i - 1] * P;
// 注意字符串下标从 0 开始,而我们习惯从 1 开始处理
h[i] = h[i - 1] * P + s[i - 1];
}
// 示例:查询 "abacaba" 中 "aca" 的哈希值
// "aca" 是原串的第 3 到 5 个字符
// 假设 s = "abacaba"
int l = 3, r = 5;
cout << "子串 " << s.substr(l - 1, r - l + 1) << " 的哈希值是: " << get_hash(l, r) << endl;
// 示例:比较两个子串是否相同
// 比较 S[1..3] ("aba") 和 S[5..7] ("aba")
if (get_hash(1, 3) == get_hash(5, 7)) {
cout << "子串 S[1..3] 和 S[5..7] 相同" << endl;
}
return 0;
}
3.2.5 洛谷例题与题解
题目:P3370 【模板】字符串哈希
题目大意:
给定
解题思路: 这是字符串哈希最经典的应用。我们可以依次读入每个字符串,计算出它的哈希值。然后,将这些哈希值存入一个数据结构中,最后统计这个数据结构里有多少个不重复的元素即可。
为了方便地统计不重复元素的个数,我们可以:
- 将所有计算出的哈希值存入一个数组。
- 对这个数组进行排序。
- 使用
std::unique函数(或手动遍历)来统计排序后数组中不重复的元素个数。
C++ 题解代码:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int P = 131; // 基数
// 计算单个字符串的哈希值
ULL calculate_string_hash(const string& s) {
ULL hash_value = 0;
for (char c : s) {
hash_value = hash_value * P + c;
}
return hash_value;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<ULL> hash_values;
for (int i = 0; i < n; ++i) {
string str;
cin >> str;
hash_values.push_back(calculate_string_hash(str));
}
// 排序
sort(hash_values.begin(), hash_values.end());
// 使用 unique 函数去重,它会返回去重后最后一个元素的下一个位置
// 两个指针的差值就是不重复元素的个数
int unique_count = unique(hash_values.begin(), hash_values.end()) - hash_values.begin();
cout << unique_count << endl;
return 0;
}
3.3 【6】哈希冲突的常用处理方法
3.3.1 什么是哈希冲突?
哈希函数的目标是为每个不同的输入生成一个唯一的哈希值。然而,由于哈希值的范围(由模数
可以把哈希表想象成一个旅馆,每个房间有一个编号(哈希值)。哈希冲突就像来了两个不相识的客人,却被分配了同一个房间。旅馆管理员(我们的程序)必须有办法处理这种情况,让两个客人都能住下。
处理哈希冲突的方法有很多,这里介绍两种最经典的方法:拉链法和开放定址法。同时,介绍一种有效降低冲突概率的方法:双哈希。
3.3.2 方法一:拉链法 (Chaining)
拉链法,又称链地址法,是处理哈希冲突最常用的方法。
核心思想:
将哈希表(通常是一个数组)的每个位置都看作一个“桶”或“槽位”。这个桶里不是直接存储一个元素,而是存储一个链表(或者动态数组 std::vector)的头节点。所有哈希值相同的元素,都被依次放入对应位置的链表中。
工作流程:
- 插入元素
key :- 计算
key 的哈希值h = H(key) 。 - 在哈希表数组的第
h 个位置,找到对应的链表。 - 将元素
key 添加到这个链表的末尾。
- 计算
- 查找元素
key :- 计算
key 的哈希值h = H(key) 。 - 在哈希表数组的第
h 个位置,找到对应的链表。 - 遍历这个链表,逐一检查链表中的元素是否与要查找的
key 相等。如果找到,则查找成功;如果遍历完整个链表都未找到,则查找失败。
- 计算
伪代码:
// HashTable 是一个数组,每个元素是一个链表
HashTable table[M];
function Insert(key):
h = H(key)
// 在 table[h] 对应的链表中查找 key 是否已存在,避免重复插入
// ...
// 如果不存在,将 key 插入到 table[h] 链表的头部或尾部
function Find(key):
h = H(key)
// 遍历 table[h] 对应的链表
for each element in table[h]:
if element == key:
return true // 找到了
return false // 没找到
C++ 代码模板 (使用 std::vector)
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int M = 100003; // 选择一个质数作为哈希表的大小
vector<string> hashTable[M];
// 简单的字符串哈希函数
int get_hash(const string& s) {
long long hash_value = 0;
const int P = 131;
for (char c : s) {
hash_value = (hash_value * P + c) % M;
}
return (int)hash_value;
}
// 插入
void insert(const string& s) {
int h = get_hash(s);
// 简单起见,这里允许重复插入
// 严谨的实现会先查找是否存在
hashTable[h].push_back(s);
}
// 查找
bool find(const string& s) {
int h = get_hash(s);
for (const string& str_in_list : hashTable[h]) {
if (str_in_list == s) {
return true;
}
}
return false;
}
int main() {
insert("apple");
insert("banana");
insert("apply"); // 假设 "apply" 和 "apple" 哈希冲突
if (find("apple")) {
cout << "找到了 apple" << endl;
}
if (find("orange")) {
cout << "找到了 orange" << endl;
} else {
cout << "没有找到 orange" << endl;
}
return 0;
}
3.3.3 方法二:开放定址法 (Open Addressing)
开放定址法的核心思想是:如果计算出的哈希位置
工作流程(以最简单的线性探测为例):
- 插入元素
key :- 计算初始哈希位置
h_0 = H(key) 。 - 如果
table[h0]是空的,则将key 放入该位置。 - 如果
table[h0]已被占用,则尝试下一个位置h_1 = (h_0 + 1) \pmod M 。 - 如果
table[h1]仍被占用,则继续尝试h_2 = (h_0 + 2) \pmod M ,h_3 = (h_0 + 3) \pmod M ...... 直到找到一个空位。
- 计算初始哈希位置
- 查找元素
key :- 计算初始哈希位置
h_0 = H(key) 。 - 检查
table[h0]的元素。- 如果是
key ,则查找成功。 - 如果为空,则说明
key 不存在,查找失败。 - 如果是一个不等于
key 的其他元素,说明发生了冲突,继续探测下一个位置h_1 = (h_0 + 1) \pmod M ,重复此过程。
- 如果是
- 计算初始哈希位置
开放定址法相比于拉链法,没有链表的额外开销,但它容易产生“聚集”现象,即连续的位置都被占满,导致后续元素的插入和查找需要探测很长的距离,影响效率。
3.3.4 方法三:双哈希(降低冲突概率)
双哈希并不是一种处理冲突的结构性方法,而是一种从根源上极大地降低冲突概率的技巧,在信息学竞赛中尤为常用,特别是在字符串哈希中。
核心思想:
为同一个字符串计算两个不同的哈希值。我们可以选择两组不同的基数和模数(例如,
只有当两个字符串的
为什么有效?
假设使用单哈希时,两个不同字符串发生冲突的概率是
例如,如果
C++ 代码模板 (字符串双哈希)
#include <iostream>
#include <string>
#include <utility> // for std::pair
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<LL, LL> PII;
// 哈希函数1
const int P1 = 131, M1 = 1e9 + 7;
// 哈希函数2
const int P2 = 13331, M2 = 998244353;
// 计算字符串 s 的双哈希值
PII get_double_hash(const string& s) {
LL h1 = 0, h2 = 0;
for (char c : s) {
h1 = (h1 * P1 + c) % M1;
h2 = (h2 * P2 + c) % M2;
}
return {h1, h2};
}
int main() {
string s1 = "luogu";
string s2 = "luogu";
string s3 = "google";
PII hash1 = get_double_hash(s1);
PII hash2 = get_double_hash(s2);
PII hash3 = get_double_hash(s3);
if (hash1 == hash2) {
cout << "'" << s1 << "' 和 '" << s2 << "' 的双哈希值相同。" << endl;
}
if (hash1 != hash3) {
cout << "'" << s1 << "' 和 '" << s3 << "' 的双哈希值不同。" << endl;
cout << "Hash1: (" << hash1.first << ", " << hash1.second << ")" << endl;
cout << "Hash3: (" << hash3.first << ", " << hash3.second << ")" << endl;
}
return 0;
}
在解决类似洛谷 P3370 的问题时,如果担心单哈希会被特殊数据卡掉(即出题人故意构造冲突数据),使用双哈希或三哈希是一种非常稳妥的策略。
:::align{center}
第二章\ \ \ \ 算 法
第一节\ \ \ \ 搜索算法
:::
在信息学竞赛中,搜索算法是解决问题的一把利剑。无论是深度优先搜索(DFS)还是广度优先搜索(BFS),它们都为我们提供了一套系统性的方法来“暴力”地探索所有可能性。然而,随着问题规模的增大,单纯的暴力搜索会因为需要探索的状态空间过于庞大而导致“超时”(Time Limit Exceeded, TLE)。
这就好比在一座巨大的、拥有无数分岔路口的迷宫中寻找出口。如果我们漫无目的地把每一条路都走到黑,很可能会耗尽所有时间。因此,我们需要更聪明的策略,来优化我们的搜索过程。本章将深入探讨五种至关重要的搜索优化技术:剪枝优化、记忆化搜索、启发式搜索、双向广度优先搜索和迭代加深搜索。
1.1 【6】搜索的剪枝优化
1.1.1 什么是搜索?什么是搜索树?
在讨论剪枝之前,必须先理解我们到底在“搜索”什么。在很多问题中,我们可以把解决问题的过程看作是一系列决策的集合。例如,在N皇后问题中,第一个决策是在第一行放皇后,第二个决策是在第二行放皇后,以此类推。
所有这些决策点和它们之间的联系,可以构成一棵“树”的结构,我们称之为搜索树。树的根节点代表初始状态,每一个非叶子节点代表一个中间状态,每一条边代表一个决策,而每一个叶子节点则代表一个最终的解决方案或者一个死胡同。
深度优先搜索(DFS)的过程,本质上就是从根节点出发,遍历这棵搜索树,试图找到我们想要的答案。
1.1.2 剪枝:砍掉无用的树枝
一个朴素的DFS会尝试走遍搜索树的每一条路径,访问每一个节点。但很多时候,搜索树的某些“树枝”是完全没有意义的。
举个例子,假设我们在寻找从家里到学校的最短路径。我们正在探索一条路线,走了10分钟后发现,这条路的总长度已经超过了我们之前找到的一条只需要8分钟的路线。那么,我们还有必要继续沿着这条10分钟的路线走下去吗?显然没有,因为无论接下来怎么走,最终花费的时间都必定超过8分钟。
这个“放弃继续探索这条更长路线”的决策,就是剪枝(Pruning)。
剪枝的核心思想是:通过特定的判断,提前终止对搜索树中那些不可能产生有效解或最优解的分支的探索,从而避免不必要的计算,大幅度提高搜索算法的效率。
1.1.3 常见的剪枝策略
剪枝没有固定的公式,它更像是一种思维方式。根据问题的性质,我们可以设计出不同的剪枝策略。以下是几种最常见的剪枝类型:
-
可行性剪枝 (Feasibility Pruning) 这是最基础也最重要的一种剪枝。当我们在搜索过程中发现,当前的状态无论如何调整,都无法满足问题的约束条件,最终也无法得到一个合法的解时,就应该立即停止对这个分支的深入探索。
- 例子:N皇后问题
问题要求在
N \times N 的棋盘上放置N 个皇后,使得它们互相不能攻击。当我们在第row行尝试放置一个皇后在col列时,如果这个位置已经被其他皇后攻击(即同一列、同一对角线已有皇后),那么从这个位置出发的所有后续方案都是不合法的。此时,我们就不应该继续递归下去,而是直接尝试下一个列,这就是可行性剪枝。
- 例子:N皇后问题
问题要求在
-
最优性剪枝 (Optimality Pruning) 这种剪枝通常用于解决“最优化问题”,例如求最小值、最大值、最短路径等。如果我们维护一个全局变量来记录当前找到的最优解(例如
min_cost或max_value),在搜索过程中,一旦发现当前状态的“成本”已经不优于当前最优解了,那么这个分支就没有继续探索的必要了。- 例子:旅行商问题 (TSP) 的简化版
假设要找一条经过若干城市的最短路径。我们用一个变量
best_len记录已找到的最短路径长度。在DFS搜索时,我们记录当前已经走过的路径长度current_len。如果current_len已经大于等于best_len,那么无论接下来怎么走,总路径长度都只会更长,不可能比best_len更优。因此,可以直接返回,剪掉这个分支。
- 例子:旅行商问题 (TSP) 的简化版
假设要找一条经过若干城市的最短路径。我们用一个变量
-
搜索顺序优化 (Search Order Optimization) 这本身不是一种直接的“剪枝”,但它能极大地增强剪枝的效果。搜索的顺序会影响到搜索树的形态。一个好的搜索顺序可以让我们更快地到达最优解,或者更快地发现某个分支是不可行的。
- 核心思想:优先搜索那些“可能性更少”或者“约束更强”的分支。这样可以使搜索树变得更“瘦”,从而减少搜索的总节点数。同时,如果能先搜到优质解,最优性剪枝的效率会大大提高。
- 例子:在一个填数问题中,如果有些位置能填的数字选择很少,我们应该优先去填这些位置。因为选择少,更容易碰壁,从而触发可行性剪枝,避免了在其他选择多的位置上浪费时间。
-
等效冗余/重复性剪枝 (Symmetry/Redundancy Pruning) 在某些问题中,不同的搜索顺序可能会得到本质上相同的解。例如,求组合数“从5个球中选3个”,先选1号再选2号再选3号,与先选3号再选2号再选1号,得到的组合是完全一样的。为了避免这种重复计算,我们可以施加一个人为的约束。
- 例子:数的划分
将整数
n 划分为k 个正整数之和。例如n=7, k=3 ,1+1+5,1+5+1,5+1+1是同一种划分。为了避免重复,我们可以强制要求划分出的数是单调不减的。即dfs(n, k, last_num),规定下一次划分出的数不能小于last_num。这样,1+1+5会被搜到,而1+5+1这种不满足单调不减的顺序就不会被搜索,从而避免了冗余。
- 例子:数的划分
将整数
1.1.4 剪枝实战:洛谷 P1025 数的划分
题目描述:将整数
分析:
这是一个典型的DFS问题。我们可以定义一个函数 dfs(sum, count, prev),表示当前已经划分出的数的总和是 sum,已经划分了 count 个数,上一个划分的数是 prev。
-
基本框架 (未剪枝): 从
prev + 1开始枚举当前要划分的数i,然后递归调用dfs(sum + i, count + 1, i)。 -
剪枝策略:
-
等效冗余剪枝:题目要求“任意两份不能相同(即升序)”,这天然地为我们提供了一个剪枝方向。我们在搜索时,强制要求下一个选择的数必须比前一个大。这正是上面提到的第4种剪枝。我们的
dfs参数设计中的prev就是为了实现这一点。 -
可行性/最优性剪枝:
- 和的剪枝:如果当前已划分的和
sum加上接下来要尝试的数i已经超过了总数n,那么i和任何比i大的数都是不合法的。可以直接结束当前循环。 - 剩余数量剪枝:假设我们还需要划分
k - count个数。为了使和最小,我们接下来只能选择prev+1, prev+2, ..., prev + (k-count)这些数。如果当前和sum加上这些最小的数的和都已经超过了n,那么当前分支肯定无解。这个剪枝非常强力。 - 更简单的剩余数量剪枝:还需要划分
k - count个数,每个数至少是prev+1。那么至少还需要(k - count) * (prev + 1)的和。如果sum + (k - count) * (prev + 1) > n,则无解。
- 和的剪枝:如果当前已划分的和
-
1.1.5 C++ 代码实现
#include <iostream>
using namespace std;
int n, k;
int ans = 0;
// dfs(last, sum, cnt)
// last: 上一个选择的数
// sum: 当前已经划分的数的总和
// cnt: 当前已经划分了几个数
void dfs(int last, int sum, int cnt) {
// 1. 递归终止条件
if (cnt == k) {
if (sum == n) {
ans++;
}
return;
}
// 2. 剪枝优化
// 如果当前和已经超过n,或者剩余的数即使全取最小值也超过n,则剪枝
// 还需要 k-cnt 个数,每个数最小是 last+1
if (sum + (k - cnt) * (last + 1) > n) {
return;
}
// 3. 循环遍历所有可能的选择
// i 是当前要选择的数
for (int i = last + 1; sum + i <= n; ++i) {
dfs(i, sum + i, cnt + 1);
}
}
int main() {
cin >> n >> k;
// 初始状态:上一个数是0,和是0,划分了0个数
dfs(0, 0, 0);
cout << ans << endl;
return 0;
}
1.2 【6】记忆化搜索
1.2.1 重复的劳动:低效的根源
我们再来看一个经典的例子:斐波那契数列。其递推公式为
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
计算 fib(5) 的过程会是这样的:
fib(5) -> fib(4) + fib(3)
fib(4) -> fib(3) + fib(2)
fib(3) -> fib(2) + fib(1)
可以发现,fib(3) 被计算了两次,fib(2) 被计算了三次... 随着 n 的增大,这种重复计算会呈指数级增长,导致极低的效率。
在很多搜索问题中,我们也会遇到同样的情况:不同的搜索路径可能会到达同一个中间状态。如果我们每次到达这个状态都要重新计算一遍它的后续结果,无疑是巨大的浪费。
1.2.2 记忆化:好记性不如烂笔头
记忆化搜索 (Memoization Search) 就是为了解决这个问题而生的。它的核心思想非常朴素:将计算过的结果保存下来,下次再遇到相同的状态时,直接使用保存的结果,而不是重新计算。
这就像我们做数学题,一道复杂的题目需要一个中间步骤 A 的结果。我们第一次算出 A 的值后,把它记在草稿纸上。后面再次需要 A 的值时,直接看草稿纸就行了,无需再推导一遍。
实现记忆化搜索,通常需要一个数组或者哈希表(在C++中常用 map)来充当这个“草稿纸”(我们称之为 备忘录 或 缓存)。
1.2.3 记忆化搜索的“三步曲”
一个标准的记忆化搜索通常在递归函数的开头加上固定的逻辑:
- 检查备忘录:在函数开始时,检查当前状态
(state_params)对应的结果是否已经存在于备忘录中。 - 直接返回结果:如果备忘录中已有记录,说明这个子问题已经被解决了,直接返回储存的结果,不再进行后续的计算。
- 计算并存入备忘录:如果备忘录中没有记录,那么就正常进行计算。在计算出结果后,在函数返回前,将该结果存入备忘录,以便将来使用。
为了区分“未计算”和“计算结果为0”这两种情况,我们通常将备忘录数组初始化为一个特殊值,比如 -1。
1.2.4 记忆化搜索 vs. 动态规划
细心的同学可能会发现,记忆化搜索解决问题的思路(记录子问题解,避免重复计算)和动态规划(DP)非常相似。
- 关系:记忆化搜索是动态规划的一种实现方式。可以说,记忆化搜索就是“自顶向下”的DP。
- 区别:
- 常规DP(递推):通常是“自底向上”的。从最小的子问题开始,一步步算出更大问题的解。通常使用循环实现。
- 记忆化搜索(递归):是“自顶向下”的。从目标问题开始,通过递归分解成子问题。只计算那些在求解目标问题过程中真正需要用到的子问题。
- 优点:
- 直观:代码结构和朴素的递归搜索很像,容易理解和编写。
- 高效:只计算必要的子问题,对于某些状态空间稀疏的问题,可能比自底向上的DP更快。
1.2.5 记忆化搜索实战:洛谷 P1464 Function
题目描述:
对于一个递归函数
分析: 这是一个赤裸裸的递归函数定义。如果我们直接照着定义写递归代码,会因为大量的重复计算而超时。这正是记忆化搜索的用武之地。
- 状态:函数的解完全由参数
(a, b, c)决定。 - 备忘录:由于
a, b, c 的有效范围是0到20,我们可以创建一个三维数组long long memo[21][21][21];来存储计算结果。 - 实现:按照“三步曲”来改造递归函数即可。
1.2.6 伪代码模板
function solve(state):
// 1. 检查备忘录
if memo[state] has been computed:
// 2. 直接返回结果
return memo[state]
// 正常计算
result = ... // 根据递推关系计算
// 3. 存入备忘录
memo[state] = result
return result
1.2.7 C++ 代码实现
#include <iostream>
#include <vector>
using namespace std;
// 备忘录,初始化为一个特殊值,这里可以用0,因为题目保证结果都是正数
// 但为了通用性,用-1或者一个bool数组来标记更清晰
long long memo[21][21][21];
bool visited[21][21][21];
long long w(int a, int b, int c) {
// 基础边界条件
if (a <= 0 || b <= 0 || c <= 0) {
return 1;
}
if (a > 20 || b > 20 || c > 20) {
return w(20, 20, 20);
}
// 1. 检查备忘录
if (visited[a][b][c]) {
// 2. 直接返回结果
return memo[a][b][c];
}
// 3. 正常计算
long long result;
if (a < b && b < c) {
result = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
} else {
result = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}
// 4. 存入备忘录并返回
visited[a][b][c] = true;
memo[a][b][c] = result;
return result;
}
int main() {
int a, b, c;
while (cin >> a >> b >> c && (a != -1 || b != -1 || c != -1)) {
cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << endl;
}
return 0;
}
1.3 【7】启发式搜索
1.3.1 当剪枝和记忆化也不够用时
剪枝优化了搜索,避免了无效路径;记忆化避免了重复计算。但对于一些状态空间极其巨大的最优化问题(如最短路、最小代价),即使有了这些优化,我们可能仍然无法在规定时间内找到最优解。
问题在于,DFS和BFS在选择下一个要扩展的节点时,带有一定的“盲目性”。DFS是一条路走到黑,BFS是稳扎稳打、齐头并进。它们都没有考虑哪个分支“看起来更有希望”接近目标。
启发式搜索 (Heuristic Search) 引入了一个“评估函数”或“估价函数” (Heuristic Function),来评估当前状态距离目标状态的“远近”或“优劣”,并优先选择那些“看起来最有希望”的状态进行扩展。
1.3.2 核心:估价函数 h(n)
估价函数是启发式搜索的灵魂,通常记为
- 重要特性:
h(n) 只是一个估计,它不一定等于真实代价。 - 类比:你在一个陌生的城市要去火车站。你不知道具体路线,但你知道火车站大致在你的东北方向。于是,你每到一个路口,都会优先选择东北方向的路走。这个“朝东北方向走”的策略,就是一种启发式策略。它不能保证你走的是最短的路,但它大大提高了你找到火车站的效率,避免了你朝西南方向走冤枉路。
1.3.3 A* 算法:最经典的启发式搜索
A (A-star) 算法是启发式搜索中最著名、最常用的算法。它完美地结合了已知信息和未来估计。A 算法为每个状态
A* 算法的执行流程类似于Dijkstra算法或BFS,但它使用的不是普通的队列,而是一个优先队列 (Priority Queue),队列中的元素按照
1.3.4 A* 算法的伪代码
function A_Star_Search(start, goal):
// 1. 初始化优先队列和记录
open_list = a priority queue containing start
g_score[start] = 0
f_score[start] = h(start) // h是估价函数
// 2. 循环直到找到解或队列为空
while open_list is not empty:
// 取出f值最小的节点
current = node in open_list with the lowest f_score
if current is goal:
return construct_path(current) // 成功找到路径
remove current from open_list
// 3. 遍历邻居节点
for each neighbor of current:
// tentative_g_score 是从起点到这个邻居的g值
tentative_g_score = g_score[current] + cost(current, neighbor)
// 如果找到了到邻居的更短路径
if tentative_g_score < g_score[neighbor]:
g_score[neighbor] = tentative_g_score
f_score[neighbor] = g_score[neighbor] + h(neighbor)
if neighbor is not in open_list:
add neighbor to open_list
1.3.5 估价函数的设计:A* 的关键
估价函数
- 可采纳性:对于任何状态
n ,估价函数的值h(n) 必须小于或等于从状态n 到目标状态的真实最小代价。换句话说,h(n) 必须是乐观的,它永远不能高估代价。 - 为什么重要? 如果估价函数高估了代价,可能会导致A算法错过最优解。例如,一条实际上是最优的路径,因为它的
h(n) 被高估了,导致它的f(n) 值变得很大,使得A算法错误地放弃了对它的探索。
如果
1.3.6 A* 实战:洛谷 P1379 八数码难题
题目描述:在一个
分析: 这是一个典型的最短路问题,状态空间巨大,适合用A*算法解决。
- 状态:
3 \times 3 棋盘的布局。可以用一个二维数组或一个字符串来表示。 g(n) :从初始状态到当前状态n 所用的步数。h(n) :估价函数。一个简单且可采纳的估价函数是:所有数字当前位置与它在目标状态中位置的曼哈顿距离之和。- 曼哈顿距离:两个点
(x_1, y_1) 和(x_2, y_2) 的曼哈顿距离是|x_1 - x_2| + |y_1 - y_2| 。 - 为什么可采纳? 因为每个数字至少需要移动它与目标位置的曼哈顿距离那么多的步数才能归位,而且每次移动空格最多只能让一个数字向它的目标位置靠近一步。所以这个估计值永远不会超过真实的步数。
- 曼哈顿距离:两个点
- 数据结构:
- 一个优先队列,存放待扩展的状态,按
f(n) 排序。 - 一个
map<string, int>或哈希表,用来记录已经访问过的状态以及到达该状态的最小步数(g(n) ),防止走回头路和重复搜索。
- 一个优先队列,存放待扩展的状态,按
1.3.7 C++ 代码实现 (核心思路)
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <cmath>
using namespace std;
// 状态结构体
struct State {
string s; // 棋盘状态的字符串表示
int g; // 实际步数
int h; // 估价函数值
// 优先队列默认是最大堆,重载小于号实现最小堆
bool operator < (const State& other) const {
return g + h > other.g + other.h; // f = g + h
}
};
string goal = "123804765"; // 目标状态
map<char, pair<int, int>> goal_pos; // 预处理目标位置
// 计算h(n)
int calculate_h(const string& s) {
int dist = 0;
for (int i = 0; i < 9; ++i) {
if (s[i] != '0') {
int r1 = i / 3, c1 = i % 3;
int r2 = goal_pos[s[i]].first;
int c2 = goal_pos[s[i]].second;
dist += abs(r1 - r2) + abs(c1 - c2);
}
}
return dist;
}
void a_star(string start) {
priority_queue<State> pq;
map<string, int> g_score;
// 预处理目标位置
for (int i = 0; i < 9; ++i) {
goal_pos[goal[i]] = {i / 3, i % 3};
}
State initial_state = {start, 0, calculate_h(start)};
pq.push(initial_state);
g_score[start] = 0;
int dr[] = {-1, 1, 0, 0}; // 上下左右
int dc[] = {0, 0, -1, 1};
while (!pq.empty()) {
State current = pq.top();
pq.pop();
if (current.s == goal) {
cout << current.g << endl;
return;
}
// 找到空格位置
int zero_pos = current.s.find('0');
int r = zero_pos / 3;
int c = zero_pos % 3;
for (int i = 0; i < 4; ++i) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3) {
string next_s = current.s;
swap(next_s[zero_pos], next_s[nr * 3 + nc]);
int new_g = current.g + 1;
// 如果这个状态还没访问过,或者找到了更短的路
if (g_score.find(next_s) == g_score.end() || new_g < g_score[next_s]) {
g_score[next_s] = new_g;
State next_state = {next_s, new_g, calculate_h(next_s)};
pq.push(next_state);
}
}
}
}
}
int main() {
string start_s;
char c;
for(int i = 0; i < 9; ++i) {
cin >> c;
start_s += c;
}
a_star(start_s);
return 0;
}
1.4 【7】双向广度优先搜索
在学习双向广度优先搜索(Bidirectional BFS)之前,我们首先需要回顾一下普通的广度优先搜索(BFS)。BFS 是一种用于图和树的遍历算法,它从一个起始节点开始,逐层地向外探索,直到找到目标节点。由于其逐层搜索的特性,BFS 能够保证找到从起点到终点的最短路径(在所有边的权重都相同的情况下)。
然而,当搜索的范围非常大时,普通的 BFS 会遇到性能瓶颈。BFS 搜索的节点数量随着搜索深度的增加呈指数级增长。如果一个问题的状态空间非常广阔,普通的 BFS 可能会因为需要访问的节点太多而导致超时或内存溢出。
为了解决这个问题,双向广度优先搜索应运而生。
1.4.1 什么是双向广度优先搜索?
双向广度优先搜索是一种对普通 BFS 的优化策略。它的核心思想是,同时从起始状态和目标状态开始进行广度优先搜索,当两个搜索方向相遇时,就意味着找到了一条从起点到终点的路径。
可以想象一个生活中的场景:两个人 A 和 B 在一个巨大的迷宫里,A 在入口,B 在出口。如果只有 A 一个人寻找 B,他可能需要走遍大半个迷宫才能找到出口。但如果 A 和 B 约定好,同时从各自的位置出发向对方靠近,他们相遇的地点很可能在迷宫的中间区域。这样,他们每个人需要探索的区域都大大减小了,找到对方的速度自然也就快了很多。
这个“迷宫”就是我们算法中的“状态空间”,A 和 B 的搜索就是两个方向的 BFS。
(此处原为图片,已根据要求移除。文字描述如下:一个搜索空间中,起始点 S 和目标点 T 分别位于两侧。普通 BFS 从 S 出发,像一个逐渐扩大的圆形波纹,需要覆盖到 T 点。双向 BFS 从 S 和 T 同时出发,形成两个逐渐扩大的波纹,当两个波纹在中途相遇时,搜索即完成,两个波纹覆盖的总面积远小于单个波紋覆盖的面积。)
从数学上理解它的优势:假设每个状态可以扩展出
- 普通 BFS 需要访问的节点数量大约是
O(b^d) 。 - 双向 BFS 从两端同时搜索,理想情况下,它们会在深度约为
d/2 的地方相遇。此时,两个方向总共访问的节点数量大约是O(b^{d/2} + b^{d/2}) = O(2 \cdot b^{d/2}) 。
当
1.4.2 双向广度优先搜索的核心原理
实现双向 BFS,需要以下几个关键组件:
- 两个队列:一个用于正向搜索(从起点开始),我们称之为
q_start;另一个用于反向搜索(从终点开始),我们称之为q_end。 - 两个记录访问状态的数据结构:通常使用数组或哈希表(如 C++ STL 中的
std::map或std::unordered_map)。一个记录从起点出发到达各个状态的距离dist_start,另一个记录从终点出发到达各个状态的距离dist_end。这些数据结构同时也起到了标记已访问节点的作用,防止重复搜索。 - 交替搜索:为了保证两个搜索方向能够均衡地向中间扩展,通常采用交替进行的方式。即先扩展一层正向搜索的节点,再扩展一层反向搜索的节点,如此往复。一个更优化的策略是,每次选择当前节点数较少的那个队列进行扩展,这样可以使得两个搜索“波纹”的大小尽可能保持一致。
- 相遇判断:在某一方向的搜索扩展出一个新节点
u时,需要检查该节点是否已经被另一方向的搜索访问过。- 当正向搜索访问到节点
u时,检查dist_end中是否已经记录了u。如果记录过,说明反向搜索已经到达过这里,两个搜索在此“相遇”。 - 同理,当反向搜索访问到节点
v时,检查dist_start中是否已经记录了v。
- 当正向搜索访问到节点
- 计算最终结果:一旦在节点
meet_node处相遇,从起点到终点的最短路径长度就是dist_start[meet_node] + dist_end[meet_node]。
1.4.3 伪代码实现
下面是双向广度优先搜索的伪代码描述。
function BidirectionalBFS(start, end):
// 如果起点和终点相同,直接返回0
if start == end:
return 0
// 1. 初始化
q_start = new Queue()
q_end = new Queue()
dist_start = new Map() // 或者数组
dist_end = new Map() // 或者数组
// 2. 将起点和终点加入各自的队列和距离表
q_start.push(start)
dist_start[start] = 0
q_end.push(end)
dist_end[end] = 0
// 3. 开始交替搜索
while not q_start.empty() and not q_end.empty():
// 扩展正向搜索(可以加上优化:总是扩展较小的队列)
// 为了简化,这里只写扩展一层的逻辑
level_size = q_start.size()
for i from 1 to level_size:
current = q_start.pop()
for each neighbor of current:
if neighbor not in dist_start:
dist_start[neighbor] = dist_start[current] + 1
q_start.push(neighbor)
// 4. 相遇判断
if neighbor in dist_end:
return dist_start[neighbor] + dist_end[neighbor]
// 扩展反向搜索
level_size = q_end.size()
for i from 1 to level_size:
current = q_end.pop()
for each neighbor of current:
if neighbor not in dist_end:
dist_end[neighbor] = dist_end[current] + 1
q_end.push(neighbor)
// 4. 相遇判断
if neighbor in dist_start:
return dist_start[neighbor] + dist_end[neighbor]
// 5. 如果队列为空仍未相遇,则说明无解
return -1 // 表示无解
1.4.4 C++ 代码模板
对于状态复杂、无法直接用整数下标表示的情况(例如八数码问题中的棋盘布局),使用 std::map 或 std::unordered_map 来记录距离和访问状态非常方便。
#include <iostream>
#include <queue>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
// 假设状态可以用一个整数或字符串表示
// 这里以 int 为例,如果是复杂状态,替换成 string 即可
// get_neighbors 函数需要根据具体问题来实现,它返回一个状态的所有相邻状态
vector<int> get_neighbors(int state);
int bidirectional_bfs(int start_state, int end_state) {
if (start_state == end_state) {
return 0;
}
queue<int> q_start, q_end;
map<int, int> dist_start, dist_end;
q_start.push(start_state);
dist_start[start_state] = 0;
q_end.push(end_state);
dist_end[end_state] = 0;
while (!q_start.empty() && !q_end.empty()) {
// 优化:总是从较小的队列开始扩展
if (q_start.size() > q_end.size()) {
swap(q_start, q_end);
swap(dist_start, dist_end);
}
int u = q_start.front();
q_start.pop();
int d = dist_start[u];
// 假设 get_neighbors 返回一个包含所有邻居状态的 vector
for (int v : get_neighbors(u)) {
// 如果这个邻居还没有被正向搜索访问过
if (dist_start.find(v) == dist_start.end()) {
dist_start[v] = d + 1;
q_start.push(v);
// 检查是否与反向搜索相遇
if (dist_end.find(v) != dist_end.end()) {
return dist_start[v] + dist_end[v];
}
}
}
}
// 搜索结束仍未相遇,表示无解
return -1;
}
1.4.5 经典例题:P1379 八数码难题
1. 题目描述
在一个 3x3 的棋盘上,有 1 到 8 八个数字和一个空格(通常用 0 表示)。每次操作可以将空格与它上下左右相邻的数字交换位置。给定一个初始的棋盘布局和一个目标布局,求最少需要多少次交换才能从初始布局到达目标布局。
2. 题目分析
这是一个典型的状态空间搜索问题,并且要求最少步数,自然会想到使用 BFS。
- 状态表示:一个 3x3 的棋盘布局可以看作一个状态。为了方便存储和查询,我们可以将这个二维的布局 "压扁" 成一个一维的字符串或一个九位数。例如,
123456780就代表了目标状态。 - 状态转移:通过移动空格,一个状态可以转移到其相邻的 2 到 4 个新状态。
- 问题:八数码问题的状态总数是
9! = 362880 种。虽然这个数字看起来不大,但如果从起点到终点的步数较多(比如 30 步),普通 BFS 的搜索队列可能会变得非常庞大,导致超时或超内存。 - 解决方案:这正是双向 BFS 的用武之地。我们已知起点状态和终点状态(
123456780),可以从这两个状态同时开始搜索,直到在中途相遇。
3. 题解代码
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
// 初始状态和目标状态
string start_s, target_s = "123456780";
// 记录两个方向的距离
map<string, int> dist_start, dist_end;
// 记录两个方向的队列
queue<string> q_start, q_end;
// dx, dy 用于找到空格的邻居位置
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
void bfs() {
q_start.push(start_s);
dist_start[start_s] = 0;
q_end.push(target_s);
dist_end[target_s] = 0;
while (!q_start.empty() && !q_end.empty()) {
// 正向扩展
string u = q_start.front();
q_start.pop();
int d = dist_start[u];
// 找到'0'的位置
int zero_pos = u.find('0');
int x = zero_pos / 3;
int y = zero_pos % 3;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
string v = u;
swap(v[zero_pos], v[nx * 3 + ny]);
// 如果 v 状态还没被正向搜索访问过
if (dist_start.find(v) == dist_start.end()) {
dist_start[v] = d + 1;
q_start.push(v);
// 检查是否与反向搜索相遇
if (dist_end.find(v) != dist_end.end()) {
cout << dist_start[v] + dist_end[v] << endl;
return;
}
}
}
}
// 反向扩展
u = q_end.front();
q_end.pop();
d = dist_end[u];
zero_pos = u.find('0');
x = zero_pos / 3;
y = zero_pos % 3;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
string v = u;
swap(v[zero_pos], v[nx * 3 + ny]);
if (dist_end.find(v) == dist_end.end()) {
dist_end[v] = d + 1;
q_end.push(v);
if (dist_start.find(v) != dist_start.end()) {
cout << dist_start[v] + dist_end[v] << endl;
return;
}
}
}
}
}
}
int main() {
cin >> start_s;
if (start_s == target_s) {
cout << 0 << endl;
return 0;
}
bfs();
return 0;
}
注意:为了简化逻辑,上述代码没有采用“总是扩展小队列”的优化,而是简单地交替扩展。在实际比赛中,加入该优化可以获得更好的性能。
1.5 【7】迭代加深搜索
在信息学竞赛中,我们经常需要在庞大的状态空间中寻找解决方案。深度优先搜索(DFS)和广度优先搜索(BFS)是两种最基本的搜索策略,但它们各有优缺点:
-
DFS (Depth-First Search):
- 优点: 内存开销小,因为它只需要存储从起点到当前节点的路径。实现起来也相对简单(通常用递归)。
- 缺点: 如果搜索树有很深的分支或者无限分支,DFS 可能会陷入其中,找不到解。即使找到解,也不能保证是“层数”最浅的解(即最优解)。
-
BFS (Breadth-First Search):
- 优点: 能保证找到层数最浅的解,即最短路径解。
- 缺点: 内存开销巨大,因为它需要存储所有待扩展的节点。当搜索树的宽度很大时,队列会迅速膨胀,导致内存耗尽。
那么,是否存在一种算法,能够兼具 DFS 的小空间开销和 BFS 的寻找最优解的能力呢?答案是肯定的,它就是迭代加深搜索。
1.5.1 什么是迭代加深搜索?
迭代加深搜索(Iterative Deepening Search, IDS),全称为“迭代加深深度优先搜索”(IDDFS),是一种巧妙地结合了 DFS 和 BFS 优点的搜索算法。
它的核心思想是:对搜索深度进行限制,并逐步放大这个限制,反复地进行深度优先搜索。
让我们用一个比喻来理解它。假设你在一个大图书馆里找一本书,但你不知道它在哪一层。
- DFS 就像你一头扎进一个书架,沿着这个书架一直走到头,再换下一个书架……你可能会在图书馆的顶层绕了半天,而书其实就在一楼。
- BFS 就像你喊来一大群朋友,让大家把一楼的所有书架同时搜一遍,没找到,再让所有人去二楼同时搜……这样能最快找到书在哪一层,但你需要非常多的“朋友”(内存)。
- IDS 则像你一个人行动:
- 你先规定:“今天只找第 1 层。” 然后你用 DFS 的方式把第 1 层的所有书架都搜一遍。
- 如果没找到,你回家休息一下,第二天规定:“今天搜索范围扩大到第 2 层。” 然后你从头开始,用 DFS 的方式把第 1 层和第 2 层的所有书架都搜一遍。
- 如果还没找到,第三天规定:“搜索范围扩大到第 3 层。” 然后你再次从头开始,把第 1、2、3 层都搜一遍。
- ……如此循环,直到你在某一次搜索中找到了这本书。
因为你是逐层扩大搜索范围的,所以你第一次找到书时,它所在的层数一定是最浅的,这保证了解的最优性(同 BFS)。而在每一次的搜索中,你都采用 DFS 的方式,只需要记录当前的一条路径,所以空间开销很小(同 DFS)。
1.5.2 迭代加深搜索的核心原理
迭代加深搜索的算法框架非常清晰:
- 设置一个循环,用来控制当前允许搜索的最大深度
max_depth。这个max_depth从 0 或 1 开始,每次循环递增 1。 - 在循环内部,调用一个带深度限制的深度优先搜索函数
depth_limited_dfs(current_node, current_depth, max_depth)。 - 这个
depth_limited_dfs函数和普通的 DFS 几乎一样,但增加了一个剪枝判断:如果current_depth > max_depth,则立刻返回,不再继续向下搜索。 - 如果
depth_limited_dfs在当前max_depth的限制下找到了解,则整个算法结束,返回该解。如果没有找到,外层循环会增加max_depth,开始新一轮的搜索。
1.5.3 效率分析:为什么它不慢?
一个很自然的疑问是:迭代加深搜索反复地搜索浅层节点,这难道不是巨大的浪费吗?比如在搜索深度为 5 时,深度为 1, 2, 3, 4 的节点都被重复搜索了很多次。
这个担心在大多数情况下是多余的。其原因在于,在一个典型的搜索树中,绝大多数节点都集中在最底层。
让我们再次考虑一个分支因子为
- 在深度为
d 的那一次迭代中,它会访问所有深度小于等于d 的节点。 - 在之前的
d-1 次迭代中,它访问了所有深度小于等于d-1 的节点。
总访问节点数 T(d) 约等于:
而一次深度为
当分支因子
所以,迭代加深搜索用一个可以接受的、较小的常数时间代价,换来了巨大的空间优化。
1.5.4 伪代码实现
function IterativeDeepeningSearch(start_node, goal_node):
// 1. 外层循环,迭代加深
for max_depth from 0 to infinity:
// 创建一个集合或布尔数组来记录当前路径上的节点,防止在单次DFS中走回头路
visited_in_path = new Set()
// 2. 调用带深度限制的DFS
result = DepthLimitedSearch(start_node, goal_node, 0, max_depth, visited_in_path)
// 3. 如果找到解,则返回
if result is a solution:
return result
// 带深度限制的DFS函数
function DepthLimitedSearch(current_node, goal_node, depth, max_depth, visited_in_path):
// 4. 到达目标,返回成功
if current_node == goal_node:
return solution
// 5. 深度超限,剪枝
if depth >= max_depth:
return failure
// 将当前节点加入路径
visited_in_path.add(current_node)
// 扩展邻居
for each neighbor of current_node:
// 如果邻居不在当前路径上(防止环)
if neighbor not in visited_in_path:
result = DepthLimitedSearch(neighbor, goal_node, depth + 1, max_depth, visited_in_path)
// 如果找到了解,立刻层层返回
if result is a solution:
return result
// 回溯:将当前节点移出路径
visited_in_path.remove(current_node)
return failure
1.5.5 C++ 代码模板
#include <iostream>
#include <vector>
#include <cstring> // for memset
using namespace std;
const int MAXN = 100; // 假设节点数上限
vector<int> adj[MAXN]; // 邻接表存图
int start_node, goal_node;
bool found = false;
// 带深度限制的DFS
// u: 当前节点
// depth: 当前深度
// max_depth: 最大深度限制
void dfs(int u, int depth, int max_depth) {
if (found) return; // 如果已经找到答案,直接返回
if (depth > max_depth) return; // 深度超限
if (u == goal_node) {
found = true;
// 在这里可以记录路径或直接输出结果
return;
}
for (int v : adj[u]) {
// 如果需要防止在DFS的路径中走回头路,可以在这里加判断
// (例如,传入一个 bool visited[] 数组)
dfs(v, depth + 1, max_depth);
if (found) return;
}
}
void iterative_deepening_search() {
// 从深度 0 开始迭代,直到找到答案或达到一个合理的上限
for (int max_depth = 0; max_depth < MAXN; ++max_depth) {
// 每次开始新的深搜前,重置状态
found = false;
// 如果需要 visited 数组,也在这里重置
dfs(start_node, 0, max_depth);
if (found) {
cout << "Found solution at depth: " << max_depth << endl;
return;
}
}
cout << "No solution found." << endl;
}
1.5.6 经典例题:UVA529 Addition Chains
1. 题目描述
对于一个整数
-
a_0 = 1 -
a_m = n - 对于所有的
k (1 \le k \le m ),都存在i, j (0 \le j \le i < k ),使得a_k = a_i + a_j 。
要求找到对于给定的
2. 题目分析
这是一个典型的最优解搜索问题。我们要找最短的链,很自然想到 BFS。
- 状态:一个已经生成的加法链序列。
- 状态转移:从当前链的末尾元素
a_{k-1} ,我们可以通过a_k = a_i + a_j (j \le i < k ) 来生成下一个元素,从而扩展链,形成新状态。
但是,从一个链可以扩展出的新状态非常多,分支因子巨大。如果用 BFS,队列会迅速爆炸,内存不允許。
如果用普通的 DFS,我们不知道该搜多深。如果运气不好,可能会陷入一条非常长的无效链的搜索中,无法自拔。
这正是迭代加深搜索的用武之地:
- 搜索目标明确:寻找最短的链。
- 深度未知但不会无限大:链的长度是有限的。
- 分支因子大:不适合 BFS。
我们可以用迭代加深搜索,枚举链的长度 max_depth,从 1 开始。对于每一个 max_depth,我们用 DFS 去尝试能否构造出一个长度为 max_depth 的加法链。第一次成功时的 max_depth 就是答案。
3. 剪枝优化与题解代码
在 DFS 过程中,可以加入一些强大的剪枝来提高效率:
- 优化剪枝:要生成的下一个数
a_k 必须大于当前链中的最大数a_{k-1} 。 - 可行性剪枝:如果当前链中的最大数是
a_{k-1} ,那么通过剩下max_depth - (k-1)步,最多能达到的数是a_{k-1} \times 2^{\text{max\_depth} - (k-1)} 。如果这个数都小于目标n ,那么这条路肯定走不通,可以直接剪枝。
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int n;
vector<int> path; // 用来存储当前的加法链
bool found;
int max_d; // 当前迭代的最大深度
// u: 当前处理链的第 u 个位置 (从1开始)
void dfs(int u) {
if (found) return;
// 剪枝2: 可行性剪枝
// path[u-1] 是当前链的最大值
// 剩下的步数是 max_d - (u-1)
// 每一-步最多是把当前最大值翻倍
if ((path[u - 1] << (max_d - u + 1)) < n) {
return;
}
if (u > max_d) {
if (path[u - 1] == n) {
found = true;
}
return;
}
// 从大到小枚举 i 和 j, 这样可以更快地接近 n
for (int i = u - 1; i >= 0; --i) {
for (int j = i; j >= 0; --j) {
int next_val = path[i] + path[j];
// 剪枝1: 新生成的数必须更大,且不能超过 n
if (next_val > path[u - 1] && next_val <= n) {
path[u] = next_val;
dfs(u + 1);
if (found) return;
}
}
}
}
int main() {
while (cin >> n && n != 0) {
if (n == 1) {
cout << "1" << endl;
continue;
}
// 迭代加深
for (max_d = 1; ; ++max_d) {
path.assign(max_d + 1, 0);
path[0] = 1;
found = false;
dfs(1);
if (found) {
for (int i = 0; i <= max_d; ++i) {
cout << path[i] << (i == max_d ? "" : " ");
}
cout << endl;
break;
}
}
}
return 0;
}
这段代码展示了迭代加深搜索的威力。它通过限制深度,将一个看似无法解决的 BFS 问题,转化为了一个可以高效求解的 DFS 问题,并且保证了解的最优性。
:::align{center}
第二节\ \ \ \ 图论算法
:::
2.1 【6】最小生成树
在学习具体的算法之前,需要先理解几个基本概念。
图(Graph):图由若干个顶点(Vertex)和连接顶点的边(Edge)组成。可以把它想象成一张城市地图,城市就是顶点,连接城市的道路就是边。
权值(Weight):在地图上,每条道路都有自己的长度。在图论中,我们给每条边赋予一个数值,称为权值。它可以代表长度、费用、时间等。
连通图(Connected Graph):如果一个图中任意两个顶点之间都至少存在一条路径,那么这个图就是连通图。简单来说,就是从任何一个城市出发,都能到达其他任何一个城市。
树(Tree):树是一种特殊的图。它是一个无环的连通图。想象一下你家里的族谱,它就是一个树形结构,不会出现一个人既是自己的祖先又是自己的后代(这就是环)。在一个有
生成树(Spanning Tree):对于一个连通图,它的生成树是图的一个子图(即包含原图中的一部分顶点和边),这个子图需要满足两个条件:
- 包含原图中所有的
N 个顶点。 - 它本身是一棵树(连通且无环),所以它恰好有
N-1 条边。 一个图可以有很多个不同的生成树。
最小生成树(Minimum Spanning Tree, MST):在一个带权的连通图中,所有生成树中,边的权值之和最小的那一棵,就被称为最小生成树。
应用场景:想象一下,现在有
解决最小生成树问题主要有两种经典的贪心算法:Kruskal 算法和 Prim 算法。
2.1.1 【6】最小生成树:Kruskal 算法
Kruskal 算法是一种非常直观且容易理解的最小生成树算法。
2.1.1.1 核心思想:贪心的选择
Kruskal 算法的核心思想是“边的贪心”。它遵循一个简单的原则:为了让总权值最小,我们每次都选择当前可选的、权值最小的边,加入到我们的生成树中。
当然,这个选择有一个限制:新加入的边不能与已经选择的边构成一个环路。因为树是不能有环的。
所以,算法的思路就是:
- 将图中所有的边按照权值从小到大进行排序。
- 从权值最小的边开始,依次遍历每一条边。
- 对于当前遍历到的边,判断如果将它加入到已选择的边的集合中,是否会形成环路。
- 如果不会形成环路,就选择这条边。
- 如果会形成环路,就放弃这条边。
- 重复步骤3,直到我们选出了
N-1 条边为止。这N-1 条边和图中的N 个顶点就构成了最小生成树。
2.1.1.2 如何判断环路:并查集
Kruskal 算法的关键在于如何快速判断加入一条边后是否会形成环路。这里需要一个非常高效的数据结构——并查集(Disjoint Set Union, DSU)。
并查集可以把
- Find(查找):确定一个顶点属于哪个集合。通常用一个代表元素(根节点)来标识一个集合。
- Union(合并):将两个不同顶点所在的集合合并成一个大集合。
我们可以用并查集来维护图中的连通分量。一开始,每个顶点都自成一个连通分量(一个集合)。
当我们考虑一条连接顶点
- 我们使用
Find操作查找u 和v 的代表元素(它们分别属于哪个集合)。 - 如果
u 和v 的代表元素相同,说明它们早已处于同一个连通分量中。此时如果再连接它们,必然会形成一个环路。所以我们不能选择这条边。 - 如果
u 和v 的代表元素不同,说明它们分属于两个不同的连通分量。连接它们不会形成环路,只会将这两个连通分量合并成一个。于是,我们选择这条边,并使用Union操作合并这两个集合。
2.1.1.3 算法步骤
-
初始化:
- 创建一个并查集,其中每个顶点都是一个独立的集合。
- 将图中所有的
M 条边存储起来,并按权值从小到大排序。 - 初始化最小生成树的总权值为
0 ,已选择的边数量为0 。
-
遍历边:
- 依次遍历排好序的边。设当前边连接顶点
u 和v ,权值为w 。 - 使用并查集的
Find操作检查u 和v 是否在同一个集合中。 - 如果不在同一个集合:
- 将这条边加入最小生成树。
- 累加总权值:
ans += w 。 - 已选择的边数量加一:
edge\_count++ 。 - 使用并查集的
Union操作合并u 和v 所在的集合。
- 如果已选择的边数量达到了
N-1 ,则最小生成树已经构建完成,算法结束。
- 依次遍历排好序的边。设当前边连接顶点
2.1.1.4 伪代码
function Kruskal(N, edges):
// N 是顶点数, edges 是边的集合 (u, v, w)
// 1. 初始化并查集
parent = array of size N+1
for i from 1 to N:
parent[i] = i
// 2. 将所有边按权值排序
sort(edges)
total_weight = 0
edge_count = 0
// 3. 遍历所有边
for each edge (u, v, w) in edges:
// 查找 u 和 v 的根节点
root_u = find(u)
root_v = find(v)
// 如果它们不在同一个集合中
if root_u != root_v:
// 合并它们
union(root_u, root_v)
// 累加权值和边数
total_weight += w
edge_count += 1
// 如果已经选了 N-1 条边,提前结束
if edge_count == N - 1:
break
// 4. 判断是否连通
if edge_count < N - 1:
return "图不连通,无法构成生成树"
else:
return total_weight
2.1.1.5 C++ 代码模板
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 边的结构体
struct Edge {
int u, v, w;
};
// 用于 sort 函数的比较函数
bool cmp(const Edge& a, const Edge& b) {
return a.w < b.w;
}
const int MAXN = 5005; // 最大顶点数
int parent[MAXN]; // 并查集的父节点数组
// 并查集 - 查找操作(带路径压缩)
int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]); // 路径压缩
}
// Kruskal 算法
long long kruskal(int n, vector<Edge>& edges) {
// 1. 初始化并查集
for (int i = 1; i <= n; ++i) {
parent[i] = i;
}
// 2. 排序边
sort(edges.begin(), edges.end(), cmp);
long long total_weight = 0;
int edge_count = 0;
// 3. 遍历边
for (const auto& edge : edges) {
int root_u = find(edge.u);
int root_v = find(edge.v);
if (root_u != root_v) {
parent[root_u] = root_v; // 合并
total_weight += edge.w;
edge_count++;
// 剪枝:如果已经选够了 N-1 条边,就可以退出了
if (edge_count == n - 1) {
break;
}
}
}
if (edge_count < n - 1) {
return -1; // 表示图不连通
}
return total_weight;
}
int main() {
int n, m; // n: 顶点数, m: 边数
cin >> n >> m;
vector<Edge> edges(m);
for (int i = 0; i < m; ++i) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
long long result = kruskal(n, edges);
if (result == -1) {
cout << "orz" << endl; // 按照一些题目的要求输出
} else {
cout << result << endl;
}
return 0;
}
2.1.1.6 复杂度分析
- 时间复杂度:算法的主要时间开销在于对
M 条边进行排序,其时间复杂度为O(M \log M) 。并查集的操作(查找和合并)如果使用了路径压缩和按秩合并优化,其单次操作的平均时间复杂度接近O(1) ,总共M 次操作的复杂度远小于排序。因此,Kruskal 算法的总时间复杂度为O(M \log M) 。 - 空间复杂度:需要
O(M) 的空间存储边,以及O(N) 的空间用于并查集。
Kruskal 算法适用于稀疏图(边的数量
2.1.1.7 洛谷例题:P3366 【模板】最小生成树
题目描述:
如题,给出一个
输入格式:
第一行包含两个整数
输出格式: 共一行,若存在最小生成树,则输出一个整数,表示最小生成树的权值之和,否则输出 "orz"。
题解:
这道题是最小生成树的模板题。可以直接使用上面提供的 Kruskal 算法代码模板来解决。将输入的 kruskal 函数即可。函数返回值如果是 -1(在代码中判断 edge_count < n - 1),则说明图不连通,输出 "orz";否则输出计算得到的最小权值和。
2.1.2 【6】最小生成树:Prim 算法
Prim 算法是另一种经典的最小生成树算法。如果说 Kruskal 是“选边”的贪心,那么 Prim 就是“选点”的贪心。
2.1.2.1 核心思想:从点出发的贪心
Prim 算法的思路是从一个任意的顶点开始,逐步扩大一棵“已经建好的树”。
-
初始化:
- 将图中的顶点分为两个集合:
S 集合(已加入最小生成树的顶点)和T 集合(未加入的顶点)。 - 一开始,任选一个顶点(比如 1 号顶点)放入集合
S 中,其他所有顶点都在集合T 中。
- 将图中的顶点分为两个集合:
-
循环扩展:
- 重复以下操作
N-1 次,直到所有顶点都加入集合S 。 - 在每一步中,寻找一条权值最小的边
(u, v) ,其中u \in S 且v \in T 。也就是说,找到一条连接“树内”和“树外”的、最短的“桥梁”。 - 将这条最短的边加入最小生成树,并将顶点
v 从集合T 移动到集合S 。
- 重复以下操作
这个过程就像在一个孤岛上(初始顶点),每次都选择修建一座通往最近的新岛屿的最短的桥,然后把新岛屿也纳入自己的版图,不断重复这个过程,直到所有岛屿都连接起来。
2.1.2.2 算法步骤
-
初始化:
dist[i]:表示顶点i到集合S 的最短距离。初始化dist[1] = 0,其他dist[i]为无穷大。visited[i]:布尔数组,标记顶点i是否已加入集合S 。初始化所有顶点都为false。- 总权值
total_weight = 0。
-
循环 N 次:
- 在所有未被访问的顶点中,找到一个
dist值最小的顶点u。 - 将
u标记为已访问visited[u] = true。 - 将
dist[u]加入总权值total_weight。 - 遍历所有与
u相连的顶点v:- 如果
v未被访问,并且从u到v的边权值w(u, v)小于dist[v],则更新dist[v] = w(u, v)。这被称为“松弛”操作,意味着我们找到了一个更短的方式从集合S 连接到顶点v。
- 如果
- 在所有未被访问的顶点中,找到一个
-
结束:循环结束后,
total_weight就是最小生成树的权值和。
2.1.2.3 如何实现:朴素版本与堆优化
朴素版本:
在上面步骤的第二步,“找到一个 dist 值最小的顶点 u”,我们可以通过一个循环遍历所有未访问的顶点来实现。
- 外层循环
N 次。 - 内层循环
O(N) 寻找dist最小的顶点。 - 总时间复杂度为
O(N^2) 。这适用于稠密图(边的数量M 接近N^2 )。
堆优化版本:
注意到“找到 dist 值最小的顶点”这个操作非常适合用优先队列(最小堆)来优化。
-
初始化:
dist数组和visited数组同上。- 创建一个优先队列
pq,存储二元组(距离, 顶点编号),按距离从小到大排序。 - 将
(0, 1)放入优先队列。
-
循环:
- 当优先队列不为空时,取出队首元素
(d, u)。 - 如果
u已经被访问过,跳过。 - 将
u标记为已访问,累加总权值。 - 遍历
u的邻居v,如果v未被访问且w(u, v) < dist[v],则更新dist[v] = w(u, v),并将(dist[v], v)加入优先队列。
- 当优先队列不为空时,取出队首元素
这个过程和后面要讲的 Dijkstra 算法非常相似。
2.1.2.4 伪代码(堆优化版)
function Prim(N, graph):
// graph 是邻接表表示的图
dist = array of size N+1, initialized to infinity
visited = array of size N+1, initialized to false
pq = new PriorityQueue() // 最小堆
dist[1] = 0
pq.push((0, 1))
total_weight = 0
edge_count = 0
while pq is not empty:
d, u = pq.pop()
// 如果已经处理过,则跳过
if visited[u]:
continue
visited[u] = true
total_weight += d
edge_count += 1
// 遍历 u 的邻居 v
for each neighbor v of u with edge weight w:
if not visited[v] and w < dist[v]:
dist[v] = w
pq.push((w, v))
if edge_count < N:
return "图不连通"
else:
return total_weight
2.1.2.5 C++ 代码模板(堆优化版)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 5005;
const int INF = 0x3f3f3f3f; // 代表无穷大
// 邻接表存储图
struct Edge {
int to, weight;
};
vector<Edge> graph[MAXN];
// 优先队列中存储的节点状态
struct Node {
int u, dist;
// 重载小于号,用于优先队列排序
bool operator<(const Node& other) const {
return dist > other.dist;
}
};
bool visited[MAXN];
int dist[MAXN];
long long prim(int n) {
// 1. 初始化
for (int i = 1; i <= n; ++i) {
dist[i] = INF;
visited[i] = false;
}
priority_queue<Node> pq;
dist[1] = 0;
pq.push({1, 0});
long long total_weight = 0;
int node_count = 0;
// 2. 主循环
while (!pq.empty() && node_count < n) {
Node current = pq.top();
pq.pop();
int u = current.u;
int d = current.dist;
if (visited[u]) {
continue;
}
visited[u] = true;
total_weight += d;
node_count++;
// 3. 松弛操作
for (const auto& edge : graph[u]) {
int v = edge.to;
int w = edge.weight;
if (!visited[v] && w < dist[v]) {
dist[v] = w;
pq.push({v, dist[v]});
}
}
}
if (node_count < n) {
return -1; // 图不连通
}
return total_weight;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
graph[v].push_back({u, w}); // 无向图
}
long long result = prim(n);
if (result == -1) {
cout << "orz" << endl;
} else {
cout << result << endl;
}
return 0;
}
2.1.2.6 复杂度分析
- 朴素版本:时间复杂度为
O(N^2) ,空间复杂度为O(N^2) (如果用邻接矩阵存图)或O(M) (如果用邻接表)。 - 堆优化版本:每个顶点入队一次,出队一次。每次出队后,会遍历其所有出边,可能导致其他顶点入队。每条边最多被考虑两次(在无向图中)。因此,时间复杂度为
O(M \log N) (因为优先队列的操作是\log 级别的)。空间复杂度为O(M) (邻接表)+O(N) (优先队列)。
2.1.2.7 Kruskal 与 Prim 的比较
| 特性 | Kruskal 算法 | Prim 算法 |
|---|---|---|
| 核心思想 | 边的贪心 | 点的贪心 |
| 数据结构 | 并查集 | 优先队列(堆) |
| 时间复杂度 | ||
| 适用图 | 稀疏图( |
稠密图( |
| 实现 | 相对简单,只需排序和并查集 | 堆优化版与 Dijkstra 算法类似 |
对于大部分题目,由于
2.2 【6】单源最短路
单源最短路(Single-Source Shortest Path, SSSP)问题是图论中最基本也是最重要的问题之一。
问题描述:给定一个带权有向图(或无向图)和一个源顶点(起点)
这里的“最短”指的是路径上所有边的权值之和最小。
在学习算法前,需要理解一个所有最短路算法共有的核心操作——松弛(Relaxation)。
dist[v] 表示从源点 dist[u] + w(u,v) 是否小于 dist[v]。
如果小于,就说明从 dist[v] = dist[u] + w(u,v)。
if dist[u] + w(u,v) < dist[v]:
dist[v] = dist[u] + w(u,v)
所有单源最短路算法,本质上都是在用不同的策略,反复对图中的边进行松弛操作,直到无法再松弛为止。
2.2.1 【6】单源最短路:Dijkstra 算法
Dijkstra(迪杰斯特拉)算法是解决单源最短路问题最经典的算法之一。它适用于所有边权均为非负数的图。
2.2.1.1 核心思想:贪心的扩展
Dijkstra 算法的思想与 Prim 算法非常相似。它也是将顶点分为两个集合:
算法的贪心策略是:每次都从集合
为什么这个贪心是正确的?因为边权都是非负的。当我们选择了当前最近的顶点 dist[u] 的值就已经被确定为最终的最短路径了。任何其他从 dist[v] + w(v, u)。由于 dist[v] >= dist[u](因为 dist[v] + w(v, u) \ge dist[u]。这保证了不可能再有比 dist[u] 更短的路径了。
2.2.1.2 无法处理负权边的原因
正是上面这个贪心策略的正确性证明,揭示了它为什么不能处理负权边。如果存在负权边 dist[v] + w(v, u) 就可能小于 dist[u],导致我们过早地确定了
例如:从
2.2.1.3 算法步骤
-
初始化:
dist数组:dist[s] = 0,其他dist[i]为无穷大。visited数组:标记顶点是否已加入集合S (即已确定最短路),全部初始化为false。
-
循环 N 次:
- 在所有未被访问的顶点中,找到一个
dist值最小的顶点u。 - 将
u标记为已访问visited[u] = true。 - 遍历所有从
u出发的边(u, v) ,对顶点v进行松弛操作:if (dist[u] + w(u,v) < dist[v]) dist[v] = dist[u] + w(u,v)。
- 在所有未被访问的顶点中,找到一个
2.2.1.4 实现:朴素版本与堆优化
这和 Prim 算法的实现几乎一模一样。
朴素版本:时间复杂度 dist 值最小的未访问顶点。时间复杂度
2.2.1.5 伪代码(堆优化版)
function Dijkstra(graph, source):
dist = array of size N+1, initialized to infinity
pq = new PriorityQueue() // 最小堆
dist[source] = 0
pq.push((0, source)) // 存 (距离, 顶点)
while pq is not empty:
d, u = pq.pop()
// 这是一个重要的优化:如果取出的距离比已知的还大,说明是旧信息,跳过
if d > dist[u]:
continue
// 对 u 的所有邻居 v 进行松弛
for each neighbor v of u with edge weight w:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
pq.push((dist[v], v))
return dist
2.2.1.6 C++ 代码模板(堆优化版)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100005;
const long long INF = 1e18; // 距离可能很大,用 long long
// 邻接表
struct Edge {
int to;
int weight;
};
vector<Edge> graph[MAXN];
// 优先队列中的节点
struct Node {
int u;
long long dist;
bool operator>(const Node& other) const {
return dist > other.dist;
}
};
long long dist[MAXN];
bool visited[MAXN]; // 在堆优化版中,visited 可省略,用 d > dist[u] 判断
void dijkstra(int s, int n) {
// 1. 初始化
for (int i = 1; i <= n; ++i) {
dist[i] = INF;
}
dist[s] = 0;
priority_queue<Node, vector<Node>, greater<Node>> pq;
pq.push({s, 0});
while (!pq.empty()) {
Node current = pq.top();
pq.pop();
int u = current.u;
long long d = current.dist;
if (d > dist[u]) {
continue;
}
// 2. 松弛
for (const auto& edge : graph[u]) {
int v = edge.to;
int w = edge.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({v, dist[v]});
}
}
}
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
// 如果是无向图,需要加反向边
// graph[v].push_back({u, w});
}
dijkstra(s, n);
for (int i = 1; i <= n; ++i) {
if (dist[i] == INF) {
cout << 2147483647 << " "; // 按题目要求
} else {
cout << dist[i] << " ";
}
}
cout << endl;
return 0;
}
2.2.1.7 洛谷例题:P4779 【模板】单源最短路径(标准版)
题目描述:
给出一个
输入格式:
第一行包含三个整数
输出格式:
输出一行
题解:
题目保证了边权为正,是标准版的 Dijkstra 算法应用。直接使用上面的堆优化 Dijkstra 代码模板即可通过。注意数据范围,dist 数组要使用 long long 来防止溢出。
2.2.2 【6】单源最短路:Bellman-Ford 算法
与 Dijkstra 不同,Bellman-Ford 算法可以处理带有负权边的图,并且还能检测负环。当然,它的代价是时间复杂度更高。
负环(Negative Cycle):一个权值之和为负数的环路。如果图中存在负环,并且从源点可以到达这个环,那么最短路就不存在了。因为每绕这个环一圈,路径长度就会变得更小,可以无限地小下去。
2.2.2.1 核心思想:迭代松弛
Bellman-Ford 的思想非常暴力而有效。它基于这样一个事实:在一个不包含负环的图中,从源点
于是,算法进行了
- 第 1 轮迭代后,
dist[v]记录的是从s 出发,最多经过 1 条边,到达v 的最短路。 - 第 2 轮迭代后,
dist[v]记录的是从s 出发,最多经过 2 条边,到达v 的最短路。 - ...
- 第
N-1 轮迭代后,dist[v]记录的是从s 出发,最多经过N-1 条边,到达v 的最短路。
由于最短路最多就
2.2.2.2 处理负权边
Dijkstra 的贪心策略在负权边面前会失效,但 Bellman-Ford 的“蛮力”迭代法则不会。它不依赖任何贪心选择,而是系统性地考虑了所有可能性(路径长度从 1 到
2.2.2.3 负环判断
这是 Bellman-Ford 算法一个非常重要的功能。如果在完成了
dist[u] + w(u,v) < dist[v] 仍然成立,说明从
所以,如果在第
2.2.2.4 算法步骤
-
初始化:
dist数组:dist[s] = 0,其他dist[i]为无穷大。- 存储所有边(例如用一个结构体数组)。
-
迭代:
- 循环
N-1 次(for i from 1 to N-1):- 遍历图中的每一条边
(u, v) ,权值为w :- 进行松弛操作:
if (dist[u] + w < dist[v]) dist[v] = dist[u] + w。
- 进行松弛操作:
- 遍历图中的每一条边
- 循环
-
负环检测:
- 再进行一轮遍历(第
N 轮):- 遍历图中的每一条边
(u, v) ,权值为w :- 如果
dist[u] + w < dist[v]仍然成立,则说明图中存在负环。
- 如果
- 遍历图中的每一条边
- 再进行一轮遍历(第
2.2.2.5 伪代码
function BellmanFord(edges, N, source):
dist = array of size N+1, initialized to infinity
dist[source] = 0
// N-1 轮松弛
repeat N-1 times:
for each edge (u, v, w) in edges:
if dist[u] != infinity and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
// 第 N 轮检测负环
for each edge (u, v, w) in edges:
if dist[u] != infinity and dist[u] + w < dist[v]:
return "Graph contains a negative cycle"
return dist
2.2.2.6 C++ 代码模板
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 505;
const int MAXM = 10005;
const int INF = 0x3f3f3f3f;
struct Edge {
int u, v, w;
};
Edge edges[MAXM];
int dist[MAXN];
int n, m;
bool bellman_ford(int s) {
// 1. 初始化
for (int i = 1; i <= n; ++i) {
dist[i] = INF;
}
dist[s] = 0;
// 2. N-1 轮松弛
for (int i = 1; i < n; ++i) {
bool relaxed = false;
for (int j = 0; j < m; ++j) {
int u = edges[j].u;
int v = edges[j].v;
int w = edges[j].w;
if (dist[u] != INF && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
relaxed = true;
}
}
// 一个优化:如果某一轮没有发生任何松弛,说明已经收敛,可以提前退出
if (!relaxed) break;
}
// 3. 第 N 轮检测负环
for (int j = 0; j < m; ++j) {
int u = edges[j].u;
int v = edges[j].v;
int w = edges[j].w;
if (dist[u] != INF && dist[u] + w < dist[v]) {
return true; // 存在负环
}
}
return false; // 不存在负环
}
int main() {
int s; // 假设源点为1
cin >> n >> m >> s;
for (int i = 0; i < m; ++i) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
if (bellman_ford(s)) {
cout << "存在负环" << endl;
} else {
for (int i = 1; i <= n; ++i) {
if (dist[i] == INF) {
cout << "INF ";
} else {
cout << dist[i] << " ";
}
}
cout << endl;
}
return 0;
}
2.2.2.7 复杂度分析
- 时间复杂度:算法有两层循环,外层循环
N-1 次,内层循环遍历M 条边。因此,时间复杂度为O(N \cdot M) 。 - 空间复杂度:需要
O(M) 存储边,O(N) 存储dist数组。
Bellman-Ford 算法比 Dijkstra 慢,但在有负权边时是必需的。
2.2.2.8 洛谷例题:P3385 【模板】负环
题目描述:
给出一个
输入格式:
第一行一个正整数
题解: 这道题正是 Bellman-Ford 算法的经典应用。对每组数据,运行一次 Bellman-Ford 算法。如果算法的返回值表示存在负环,则输出 "YES"(或题目要求的肯定回答),否则输出 "NO"。源点可以设为 1。
2.2.3 【6】单源最短路:SPFA 算法
SPFA(Shortest Path Faster Algorithm)算法,从名字就能看出它的特点——“更快”。实际上,它是 Bellman-Ford 算法的一种队列优化版本。
2.2.3.1 核心思想:Bellman-Ford 的队列优化
回顾 Bellman-Ford,它在每一轮都盲目地对所有 dist 值发生变化的顶点的出边,才有可能去松弛其他顶点。
SPFA 敏锐地抓住了这一点。它使用一个队列来维护那些 dist 值被成功松弛的顶点。
- 初始化:将源点
s 入队。 - 循环:当队列不为空时,取出队首顶点
u 。 - 松弛:遍历
u 的所有出边(u,v) ,进行松弛操作。 - 入队:如果顶点
v 的dist值被成功更新了,并且v 当前不在队列中,就将v 入队。
这样,只有“有潜力”去更新别人的顶点才会被放入队列,并作为松弛的起点,大大减少了冗余的计算。
2.2.3.2 算法步骤
-
初始化:
dist数组:dist[s] = 0,其他为无穷大。in_queue数组:标记顶点是否在队列中,全为false。cnt数组:记录每个顶点入队的次数,用于判负环。- 创建一个队列
q,将源点s 入队,in_queue[s] = true,cnt[s] = 1。
-
主循环:
- 当队列
q不为空时:- 取出队首顶点
u,q.pop(),in_queue[u] = false。 - 遍历
u的所有出边(u, v) ,权值为w :- 进行松弛:
if (dist[u] + w < dist[v]) - 如果松弛成功:
- 更新
dist[v] = dist[u] + w。 - 如果
v不在队列中:q.push(v),in_queue[v] = true。cnt[v]++。- 如果
cnt[v] > n,则说明发现了负环,算法结束。
- 更新
- 进行松弛:
- 取出队首顶点
- 当队列
2.2.3.3 负环判断
SPFA 判断负环的原理是:如果一个顶点入队超过 dist 值最多被更新
2.2.3.4 伪代码
function SPFA(graph, N, source):
dist = array of size N+1, initialized to infinity
in_queue = array of size N+1, initialized to false
count = array of size N+1, initialized to 0
q = new Queue()
dist[source] = 0
q.push(source)
in_queue[source] = true
count[source] = 1
while q is not empty:
u = q.front()
q.pop()
in_queue[u] = false
for each neighbor v of u with edge weight w:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if not in_queue[v]:
q.push(v)
in_queue[v] = true
count[v] += 1
if count[v] > N:
return "Graph contains a negative cycle"
return dist
2.2.3.5 C++ 代码模板
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100005;
const long long INF = 1e18;
struct Edge {
int to;
int weight;
};
vector<Edge> graph[MAXN];
long long dist[MAXN];
bool in_queue[MAXN];
int cnt[MAXN]; // 记录入队次数
int n, m;
bool spfa(int s) {
// 1. 初始化
for (int i = 1; i <= n; ++i) {
dist[i] = INF;
in_queue[i] = false;
cnt[i] = 0;
}
queue<int> q;
dist[s] = 0;
q.push(s);
in_queue[s] = true;
cnt[s]++;
// 2. 主循环
while (!q.empty()) {
int u = q.front();
q.pop();
in_queue[u] = false;
for (const auto& edge : graph[u]) {
int v = edge.to;
int w = edge.weight;
if (dist[u] != INF && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!in_queue[v]) {
q.push(v);
in_queue[v] = true;
cnt[v]++;
if (cnt[v] > n) {
return true; // 存在负环
}
}
}
}
}
return false; // 不存在负环
}
int main() {
int s;
cin >> n >> m >> s;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
}
if (spfa(s)) {
cout << "存在负环" << endl;
} else {
// ... 输出结果 ...
}
return 0;
}
2.2.3.6 复杂度分析
- 时间复杂度:SPFA 的时间复杂度在随机数据下表现非常好,期望是
O(k \cdot M) ,其中k 是一个很小的常数,通常认为是O(M) 级别的。但在一些特殊构造的网格图、链式图上,SPFA 会被“卡”到其最坏时间复杂度O(N \cdot M) ,与 Bellman-Ford 相同。因此在没有负权边的图中,Dijkstra 依然是首选。 - 空间复杂度:
O(M) (邻接表)+O(N) (队列及辅助数组)。
2.2.3.7 SPFA, Dijkstra, Bellman-Ford 的选择
-
图中没有负权边:
- 首选堆优化的 Dijkstra 算法。它的时间复杂度
O(M \log N) 非常稳定高效。
- 首选堆优化的 Dijkstra 算法。它的时间复杂度
-
图中有负权边:
- 需要判断负环:使用 Bellman-Ford 或 SPFA。SPFA 在绝大多数情况下更快,但如果担心被特殊数据卡,Bellman-Ford 是更稳妥的选择。
- 保证没有负环:同样使用 Bellman-Ford 或 SPFA。
在信息学竞赛中,如果题目包含负权边,通常 SPFA 是可以通过的。只有在出题人特意构造数据卡 SPFA 时,才需要换成 Bellman-Ford 或其他更复杂的算法。
2.3 【7】单源次短路
在掌握了最短路之后,一个自然的延伸问题就是:如果最短路走不了,第二短的路是哪条?这就是单源次短路问题。
问题描述:给定一个带权图、一个源点
注意,次短路和最短路的路线可以有部分甚至完全重合,只要它们的总权值不同即可。
2.3.1 核心思想:记录两种最短路
解决这个问题的关键在于,我们不能只关心每个点的最短路了。对于图中的任意一个顶点
- 从某个邻居
v 的最短路走过来。 - 从某个邻居
v 的次短路走过来。
这就启发我们,在求解过程中,需要为每个顶点维护两个信息:
dist[u]:从源点s 到u 的最短路径长度。dist2[u]:从源点s 到u 的次短路径长度。
2.3.2 类似于 Dijkstra 的算法
我们可以对 Dijkstra 算法进行魔改,来同时计算 dist 和 dist2。
-
状态定义:
dist[i]和dist2[i]分别表示s 到i 的最短和次短路,初始化为无穷大。dist[s] = 0。
-
优先队列:
- 优先队列中存储的不再是
(距离, 顶点),而是(d, u),表示一条长度为d 的路径到达了顶点u 。我们不再需要visited数组,因为一个点可能会因为找到了更短的次短路而再次入队。
- 优先队列中存储的不再是
-
松弛操作的扩展:
- 当从优先队列中取出
(d, u)时,我们遍历u 的邻居v ,设边权为w 。有一条新路径到达v ,长度为new_dist = d + w。 - 现在,用
new_dist去更新dist[v]和dist2[v]:- Case 1:
new_dist < dist[v]- 这说明我们找到了一个更短的“最短路”。
- 那么,原来的最短路
dist[v]就变成了当前的“次短路”候选。所以dist2[v] = dist[v]。 - 新的最短路是
dist[v] = new_dist。 - 将新的最短路
(dist[v], v)和次短路(dist2[v], v)都放入优先队列。
- Case 2:
dist[v] < new_dist < dist2[v]- 这条新路径比最短路长,但比已知的次短路短。
- 这正是我们想要的,更新次短路:
dist2[v] = new_dist。 - 将新的次短路
(dist2[v], v)放入优先队列。
- Case 1:
- 当从优先队列中取出
-
最终结果:
- 算法结束后,
dist2[t]就是从s 到t 的次短路长度。
- 算法结束后,
这个算法本质上是在图上跑 Dijkstra,但把状态扩充了。每个点都有“最短”和“次短”两个状态,只要能更新这两个状态之一,就继续扩展。
2.3.3 伪代码
function SecondShortestPath(graph, N, s, t):
dist = array of size N+1, initialized to infinity
dist2 = array of size N+1, initialized to infinity
pq = new PriorityQueue()
dist[s] = 0
pq.push((0, s))
while pq is not empty:
d, u = pq.pop()
// 如果当前取出的路径比已知的次短路还长,没必要扩展了
if d > dist2[u]:
continue
for each neighbor v of u with edge weight w:
new_dist = d + w
// Case 1: 发现更短的最短路
if new_dist < dist[v]:
dist2[v] = dist[v]
dist[v] = new_dist
pq.push((dist[v], v))
pq.push((dist2[v], v))
// Case 2: 发现更短的次短路
else if new_dist > dist[v] and new_dist < dist2[v]:
dist2[v] = new_dist
pq.push((dist2[v], v))
return dist2[t]
2.3.4 C++ 代码模板
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 5005;
const int INF = 0x3f3f3f3f;
struct Edge {
int to, weight;
};
vector<Edge> graph[MAXN];
struct Node {
int u, dist;
bool operator>(const Node& other) const {
return dist > other.dist;
}
};
int dist[MAXN], dist2[MAXN];
int n, m;
void find_second_shortest(int s) {
// 1. 初始化
for (int i = 1; i <= n; ++i) {
dist[i] = INF;
dist2[i] = INF;
}
priority_queue<Node, vector<Node>, greater<Node>> pq;
dist[s] = 0;
pq.push({s, 0});
while (!pq.empty()) {
Node current = pq.top();
pq.pop();
int u = current.u;
int d = current.dist;
// 剪枝:如果当前路径比已知的次短路还长,则无需继续
if (d > dist2[u]) {
continue;
}
for (const auto& edge : graph[u]) {
int v = edge.to;
int w = edge.weight;
int new_dist = d + w;
if (new_dist < dist[v]) {
dist2[v] = dist[v];
dist[v] = new_dist;
pq.push({v, dist[v]});
pq.push({v, dist2[v]});
} else if (new_dist > dist[v] && new_dist < dist2[v]) {
dist2[v] = new_dist;
pq.push({v, dist2[v]});
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
graph[v].push_back({u, w}); // 假设是无向图
}
find_second_shortest(1); // 从 1 号点开始
cout << dist2[n] << endl; // 输出到 n 号点的次短路
return 0;
}
2.3.5 复杂度分析
- 时间复杂度:虽然看起来我们向优先队列中推送了更多的状态,但可以分析得出,每条边最多会使
dist和dist2被更新常数次。因此,算法的整体时间复杂度与堆优化的 Dijkstra 类似,约为O(M \log N) 。 - 空间复杂度:
O(M) (邻接表)+O(N) (辅助数组和优先队列)。
2.3.6 洛谷例题:P2865 [USACO06NOV]Roadblocks G
题目描述:
给出一张
输入格式:
第一行两个整数
输出格式:
输出 1 到
题解:
这是一道标准的次短路模板题。题目保证了边权非负,可以直接套用上面讲解的“Dijkstra魔改版”次短路算法。将起点设为 1,终点为 dist2[N] 即可。上面的代码模板就是针对这道题的解法。
2.4 【6】Floyd-Warshall算法
2.4.1 算法简介
Floyd-Warshall 算法(通常简称为 Floyd 算法)是一种用于求解所有节点对之间的最短路径(All-Pairs Shortest Path, APSP)的经典动态规划算法。
想象一张地图,上面有若干个城市和连接它们的道路,每条道路都有一个长度。Dijkstra 算法或 SPFA 算法可以帮助我们计算出从某一个特定的城市(源点)出发,到所有其他城市的最短距离。但如果我们需要知道地图上任意两个城市之间的最短距离,怎么办呢?
一个显而易见的想法是,对每个城市都运行一次 Dijkstra 算法。如果图中有
然而,在稠密图(边的数量接近
2.4.2 核心思想
Floyd 算法的核心思想是动态规划。它基于一个非常朴素却强大的思想:“中转”。
设 dist[i][j] 表示从节点
- 直接从
i 走到j ,不经过任何其他节点。 - 从
i 先走到某个中转点k ,再从k 走到j 。
Floyd 算法将这个思想进行了扩展。它定义了一个状态 dp[k][i][j],表示“只允许经过编号从
当我们考虑 dp[k][i][j] 时,路径同样可以分为两种:
- 不经过 节点
k 作为中转点。这种情况下,最短路径等同于“只允许经过编号从1 到k-1 的节点作为中转点”时的最短路径,即dp[k-1][i][j]。 - 经过 节点
k 作为中转点。这种情况下,路径一定是从i 先走到k ,再从k 走到j 。由于中途不能再经过比k 编号更大的节点,所以从i 到k 的路径和从k 到j 的路径都只能使用编号从1 到k-1 的节点作为中转。因此,这条路径的长度就是dp[k-1][i][k] + dp[k-1][k][j]。
综合以上两种情况,我们就得到了状态转移方程:
观察这个方程,可以发现计算第 dp[k] 时,只依赖于第 dp[k-1]。这意味着我们可以进行空间优化,省略掉第一维的
这个方程的含义是:我们依次尝试让每个节点 dist[i][j] 中存储的就是从
2.4.3 算法流程与模拟
初始化:
- 创建一个二维数组
dist[N+1][N+1]。 - 对于所有的
i 和j (i \neq j ),将dist[i][j]初始化为一个非常大的值(代表无穷大,表示两点不直接相连)。 - 对于所有的
i ,将dist[i][i]初始化为0 (自己到自己的距离为0)。 - 对于图中存在的每一条边
(u, v) ,其权重为w ,更新dist[u][v] = w。如果是无向图,同时更新dist[v][u] = w。
核心循环:
算法的主体是三层嵌套循环,最外层必须是中转点 k。
for k from 1 to N
for i from 1 to N
for j from 1 to N
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
这个顺序至关重要。最外层循环 k 保证了在尝试用 dist[i][k] 和 dist[k][j] 的值已经是“只允许经过
模拟示例: 假设有一个4个节点的有向图,其邻接矩阵如下(INF代表无穷大):
| from\to | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 3 | INF | 5 |
| 2 | 2 | 0 | INF | INF |
| 3 | INF | 7 | 0 | 1 |
| 4 | 6 | INF | INF | 0 |
k = 1 (以1为中转点):
dist[2][4] = min(dist[2][4], dist[2][1] + dist[1][4]) = min(INF, 2 + 5) = 7- ... 其他更新 ...
| 更新后的矩阵: | from\to | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 1 | 0 | 3 | INF | 5 | |
| 2 | 2 | 0 | INF | 7 | |
| 3 | INF | 7 | 0 | 1 | |
| 4 | 6 | 9 | INF | 0 |
k = 2 (以2为中转点):
dist[1][4] = min(dist[1][4], dist[1][2] + dist[2][4]) = min(5, 3 + 7) = 5(没有更新)dist[4][1] = min(dist[4][1], dist[4][2] + dist[2][1]) = min(6, 9 + 2) = 6(没有更新)- ...
k = 3 (以3为中转点):
dist[1][4] = min(dist[1][4], dist[1][3] + dist[3][4])(dist[1][3]是INF,不更新)dist[2][4] = min(dist[2][4], dist[2][3] + dist[3][4])(dist[2][3]是INF,不更新)dist[1][2] = min(dist[1][2], dist[1][3] + dist[3][2])(INF)dist[4][2] = min(dist[4][2], dist[4][3] + dist[3][2])(INF)
k = 4 (以4为中转点):
dist[2][1] = min(dist[2][1], dist[2][4] + dist[4][1]) = min(2, 7 + 6) = 2(没有更新)dist[3][1] = min(dist[3][1], dist[3][4] + dist[4][1]) = min(INF, 1 + 6) = 7dist[3][2] = min(dist[3][2], dist[3][4] + dist[4][2]) = min(7, 1 + 9) = 7(没有更新)
经过四轮迭代后,最终的 dist 矩阵就包含了所有点对之间的最短路径。
2.4.4 伪代码
function FloydWarshall(graph):
n = a number of vertices in graph
dist = an n x n matrix initialized with infinity, diagonal with 0
// Initialize dist with direct edge weights
for each edge (u, v) with weight w in graph:
dist[u][v] = w
// Main algorithm
for k from 1 to n:
for i from 1 to n:
for j from 1 to n:
if dist[i][k] != infinity and dist[k][j] != infinity:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
2.4.5 C++ 代码模板
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 505; // 节点数量上限
const long long INF = 1e18; // 使用 long long 防止溢出,无穷大也设大一些
int n, m, q; // n: 节点数, m: 边数, q: 查询数
long long dist[MAXN][MAXN];
void floyd_warshall() {
// 核心三层循环
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
// 防止因无穷大相加导致溢出
if (dist[i][k] != INF && dist[k][j] != INF) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}
int main() {
// 提高cin/cout效率
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> q;
// 1. 初始化距离矩阵
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j) {
dist[i][j] = 0;
} else {
dist[i][j] = INF;
}
}
}
// 2. 读入边信息
for (int i = 0; i < m; ++i) {
int u, v;
long long w;
cin >> u >> v >> w;
// 对于有重边的情况,只保留权值最小的边
dist[u][v] = min(dist[u][v], w);
// 如果是无向图,加上下面这句
// dist[v][u] = min(dist[v][u], w);
}
// 3. 执行 Floyd-Warshall 算法
floyd_warshall();
// 4. 回答查询
for (int i = 0; i < q; ++i) {
int u, v;
cin >> u >> v;
if (dist[u][v] >= INF / 2) { // 用 INF/2 判断是为了避免一些微小的误差
cout << "impossible" << endl;
} else {
cout << dist[u][v] << endl;
}
}
return 0;
}
2.4.6 时间与空间复杂度分析
- 时间复杂度: 算法的核心是三层嵌套循环,每一层都从
1 循环到N 。因此,时间复杂度非常稳定,就是O(N^3) 。 - 空间复杂度: 算法需要一个二维数组来存储所有点对之间的距离,所以空间复杂度是
O(N^2) 。
2.4.7 应用与例题
Floyd 算法除了直接求解所有点对最短路径外,还有一些巧妙的应用,例如:
- 判断图的连通性: 算法结束后,若
dist[i][j]仍为无穷大,则i 和j 不连通。 - 求最小环: 在一个图中,包含节点
k 的最小环的长度,就是dist_before_k[i][j] + w[j][k] + w[k][i],其中dist_before_k是外层循环到k-1 时的距离矩阵。 - 传递闭包: 修改状态转移方程为
dist[i][j] = dist[i][j] or (dist[i][k] and dist[k][j]),可以求出图中任意两点是否可达。
例题:洛谷 P1119 灾后重建
题目大意:
有
题解思路: 这道题有一个关键的限制:时间。一个村庄和连接它的道路只有在特定时间点之后才能使用。这恰好与 Floyd 算法中“中转点”的概念完美契合。
Floyd 算法的 for (int k = 1; k <= n; ++k) 循环,本质上是“解锁”了节点
我们可以将村庄按照修复时间从小到大排序。然后,我们不再是简单地从 k,而是根据询问的时间
具体做法是:
- 将村庄按修复时间
t[i]从小到大排序。 - 初始化
dist矩阵。 - 对于每次询问
(u, v, T) ,我们只将修复时间t[k] <= T的村庄k 作为中转点来更新dist矩阵。
为了避免每次询问都重复计算,我们可以离线处理所有询问。将询问也按时间 k,表示当前已经修复好的村庄。随着询问时间的增加,我们不断地将新修复好的村庄 k 加入中转点集合,并用它来更新全局的 dist 矩阵。
这样,对于时间为 dist 矩阵了。这巧妙地将时间维度融入了 Floyd 算法的执行过程中。
核心逻辑修改如下:
// 假设村庄已经按修复时间排好序
int k_ptr = 0;
for (each query (u, v, t) sorted by t) {
// 不断解锁新的中转点,直到当前中转点的修复时间超过询问时间
while (village[k_ptr].repaire_time <= t && k_ptr < n) {
int k = village[k_ptr].id;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
k_ptr++;
}
// 此时的 dist 矩阵就是 t 时刻下的最短路情况
// 回答询问
}
2.5 【6】有向无环图的拓扑排序
2.5.1 什么是拓扑排序?
拓扑排序 (Topological Sort) 是对有向无环图 (Directed Acyclic Graph, DAG) 的顶点进行排序,使得对于图中任意一条有向边
通俗地讲,如果我们将图中的节点看作是一系列需要完成的任务,边
例如,大学里修课程,想修《算法设计》,必须先修完《数据结构》和《C++程序设计》。这就可以表示为一个有向图,从《数据结构》到《算法设计》有一条边,从《C++程序设计》到《算法设计》也有一条边。拓扑排序给出的就是一个合法的修课顺序。
关键点:
- 拓扑排序的结果不是唯一的。一个 DAG 可能有多个合法的拓扑序列。
- 只有有向无环图(DAG)才能进行拓扑排序。如果图中存在环(例如,任务A依赖B,B依赖C,C又依赖A),那么就不可能存在一个合法的任务顺序,也就无法进行拓扑排序。这个特性也可以用来判断一个有向图是否存在环。
2.5.2 核心思想与算法流程 (Kahn算法)
最常用和最容易理解的拓扑排序算法是 Kahn 算法,它基于贪心的思想。
核心思想:
在一个有向图中,入度为
算法流程如下:
- 统计入度: 计算图中所有节点的入度(in-degree),即指向该节点的边的数量。
- 初始化队列: 将所有入度为
0 的节点放入一个队列中。这些是起始任务。 - 循环处理: 当队列不为空时,执行以下操作:
a. 从队列中取出一个节点
u (队首元素),并将其加入到拓扑排序的结果序列中。 b. “消除影响”: 遍历所有从u 出发的边(u, v) 。对于每一个邻居节点v ,将其入度减1 。这模拟了“完成了任务u 后,以它为前置条件的那些任务的依赖就少了一个”。 c. 检查新节点: 在将v 的入度减1 后,如果v 的入度变为0 ,说明v 的所有前置任务都已完成,此时将v 加入队列。 - 结束与判断: 循环结束后,检查结果序列中的节点个数是否等于图中总节点数。
- 如果相等,则该序列就是一个合法的拓扑排序。
- 如果不相等,说明图中存在环,导致有些节点的入度永远无法变为
0 ,无法加入队列。
2.5.3 伪代码
function TopologicalSort(graph):
n = a number of vertices in graph
in_degree = array of size n, initialized to 0
adj = adjacency list representation of graph
// 1. Calculate in-degrees
for each vertex u in graph:
for each neighbor v of u:
in_degree[v]++
// 2. Initialize queue with zero-in-degree vertices
queue = a new queue
for i from 1 to n:
if in_degree[i] == 0:
queue.enqueue(i)
result = an empty list
// 3. Main loop
while queue is not empty:
u = queue.dequeue()
result.append(u)
// "Remove" u's outgoing edges
for each neighbor v of u in adj[u]:
in_degree[v]--
if in_degree[v] == 0:
queue.enqueue(v)
// 4. Check for cycle
if length of result == n:
return result // Success
else:
return "Graph has a cycle" // Failure
2.5.4 C++ 代码模板
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int n, m;
vector<int> adj[MAXN]; // 邻接表存图
int in_degree[MAXN]; // 存放入度
vector<int> result; // 存放拓扑排序结果
bool topological_sort() {
queue<int> q;
// 1. 将所有入度为0的节点入队
for (int i = 1; i <= n; ++i) {
if (in_degree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
// 2. 遍历u的所有出边,更新邻居的入度
for (int v : adj[u]) {
in_degree[v]--;
if (in_degree[v] == 0) {
q.push(v);
}
}
}
// 3. 判断是否存在环
return result.size() == n;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v); // u -> v
in_degree[v]++;
}
if (topological_sort()) {
cout << "A valid topological sort is: ";
for (int i = 0; i < result.size(); ++i) {
cout << result[i] << (i == result.size() - 1 ? "" : " ");
}
cout << endl;
} else {
cout << "The graph has a cycle, no topological sort exists." << endl;
}
return 0;
}
2.5.5 时间与空间复杂度分析
- 时间复杂度:
- 计算所有节点的入度,需要遍历所有边,复杂度为
O(M) 。 - 将入度为
0 的节点入队,最多N 个节点,复杂度为O(N) 。 - 主循环中,每个节点最多入队一次、出队一次,复杂度为
O(N) 。在处理每个出队节点u 时,会遍历其所有出边,所有节点的出边加起来就是总边数M 。因此这部分复杂度为O(M) 。 - 综上,总时间复杂度为
O(N+M) 。
- 计算所有节点的入度,需要遍历所有边,复杂度为
- 空间复杂度:
- 邻接表需要
O(N+M) 的空间。 in_degree数组需要O(N) 的空间。- 队列在最坏情况下可能存储所有节点,需要
O(N) 的空间。 - 综上,总空间复杂度为
O(N+M) 。
- 邻接表需要
2.5.6 应用与例题
例题:洛谷 P1347 车站分级
题目大意:
有 A < B,表示 A 车站的等级低于 B 车站。你需要根据这些消息判断:
- 是否存在一个唯一的、确定的车站等级排列。如果是,输出这个排列并指出是在第几条消息后确定的。
- 是否存在矛盾(即出现环)。如果是,指出是在第几条消息后发现的矛盾。
- 如果到最后所有消息都处理完,仍然无法确定唯一的排列,则输出无法确定。
题解思路:
这道题是拓扑排序的经典应用。车站等级关系 A < B 可以看作一条有向边 A -> B。一个确定的车站等级排列就是一个唯一的拓扑序列。
我们可以在读入每条消息后,都尝试进行一次拓扑排序。
- 建图: 读入一条消息
u < v,就在图中加一条边(u, v),并更新节点v 的入度。 - 拓扑排序: 执行 Kahn 算法。
- 判断结果:
- 发现矛盾(环): 如果在拓扑排序后,结果序列的长度小于当前已出现过的车站总数,说明形成了环。此时就找到了矛盾,输出信息并结束程序。
- 确定唯一序列: 如何判断序列唯一?在 Kahn 算法的任何时刻,如果队列中的元素个数大于1,说明此时有多个入度为
0 的节点可供选择,那么最终的拓扑序列就不是唯一的。所以,我们在算法过程中可以加一个判断。如果在整个拓扑排序过程中,队列大小始终不大于1 ,并且最终能得到一个完整的拓ゆ序列,那么这个序列就是唯一的。 - 无法确定: 如果处理完所有
M 条消息,既没有发现矛盾,也没有找到唯一序列,就输出无法确定。
我们需要维护一个变量来记录当前处理到第几条消息,以及一个变量记录图中出现了多少个不同的车站。在每次拓扑排序时,都要重置 in_degree 和 result 等数据结构,或者使用一个副本进行操作。
这个题目综合考察了拓扑排序本身、利用拓扑排序判环,以及对拓扑排序过程的深入理解(唯一序列的判断)。
2.6 【7】割点、割边
2.6.1 基本概念
在无向连通图中,割点和割边是两个非常重要的概念,它们反映了图的“脆弱性”。
-
割点 (Cut Vertex / Articulation Point): 在一个无向图中,如果移除某个节点
u 以及所有与它相连的边后,图的连通分量数量增加,那么节点u 就被称为一个割点。通俗地说,割点就是图中的一个“关键节点”,去掉它会使得图“断开”。 -
割边 (Cut Edge / Bridge): 在一个无向图中,如果移除某条边
e 后,图的连通分量数量增加,那么边e 就被称为一条割边或桥。割边是不属于任何环的边。
理解这两个概念对于分析网络稳定性、寻找关键路径等问题至关重要。
2.6.2 核心思想与 Tarjan 算法
寻找割点和割边的标准算法是 Tarjan 算法,它基于深度优先搜索(DFS)和“时间戳”的概念。
为了理解 Tarjan 算法,我们需要先定义两个关键的数组:
dfn[u](Discovery Time): 在 DFS 过程中,节点u 第一次被访问到的次序(时间戳)。low[u](Lowest Reachable Ancestor): 从节点u 出发,通过其在 DFS 树中的后代节点,以及从这些后代节点出发最多走一条非树边(返祖边),能够到达的时间戳最小的节点的dfn值。
听起来很绕口,我们来分解 low[u] 的含义:
low[u]的初始值是dfn[u]。low[u]可以通过两种方式更新:- 通过 DFS 树中的子节点
v 更新:low[u] = min(low[u], low[v])。这意味着u 的子孙v 能到达一个更早的祖先,那么u 自然也能通过v 到达那个祖先。 - 通过一条直接连接到已访问过的祖先
v 的返祖边(u, v) 更新:low[u] = min(low[u], dfn[v])。这表示u 有一条“捷径”可以回到它的祖先v 。
- 通过 DFS 树中的子节点
dfn 数组是在 DFS 向下递归时确定的,而 low 数组是在回溯时,利用子节点的信息来更新的。
2.6.3 割边的判定法则
一条边
直观理解:
这个不等式的含义是,从节点
2.6.4 割点的判定法则
割点的判定比割边稍微复杂一些,需要分两种情况:
-
根节点: 如果节点
u 是 DFS 树的根节点,那么u 是割点的充要条件是:u 在 DFS 树中拥有两个或两个以上的子树。 直观理解: 如果根节点只有一个孩子,那么即使去掉根节点,剩下的部分仍然是一个连通的子树。但如果有多个孩子,去掉根节点后,这些子树之间就失去了联系,图会分裂。 -
非根节点: 如果节点
u 不是根节点,那么u 是割点的充要条件是:存在一个它的子节点v ,满足:low[v] \geq dfn[u] 直观理解: 这个不等式的含义是,子节点
v 和它的子树,能到达的最早的祖先节点就是u 自己(或者更晚,但不可能比u 更早)。这意味着v 这棵子树想要连接到图的其他部分,必须通过父节点u 。如果把u 去掉,v 这棵子树就无法连接到u 的祖先,从而与图分离。 注意这里是low[v] >= dfn[u]。=的情况意味着v 最多只能回到u ,但回不到u 的祖先,所以去掉u 仍然会使v 子树分离。
2.6.5 C++ 代码模板 (Tarjan算法)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
const int MAXM = 1000005;
int n, m;
vector<pair<int, int>> adj[MAXN]; // 存储边和边的原始编号
int dfn[MAXN], low[MAXN], timestamp;
bool is_cut[MAXN]; // 标记是否为割点
vector<int> bridges; // 存储割边的原始编号
void tarjan(int u, int parent_edge_id) {
dfn[u] = low[u] = ++timestamp;
int child_count = 0; // 用于根节点判断
for (auto& edge : adj[u]) {
int v = edge.first;
int edge_id = edge.second;
// 避免通过同一条边返回父节点
if (edge_id == parent_edge_id) {
continue;
}
if (!dfn[v]) { // v 未被访问,是 u 的子节点
child_count++;
tarjan(v, edge_id);
low[u] = min(low[u], low[v]);
// 割点判定 (非根节点)
if (parent_edge_id != -1 && low[v] >= dfn[u]) {
is_cut[u] = true;
}
// 割边判定
if (low[v] > dfn[u]) {
bridges.push_back(edge_id);
}
} else { // v 已被访问,是 u 的祖先
low[u] = min(low[u], dfn[v]);
}
}
// 割点判定 (根节点)
if (parent_edge_id == -1 && child_count >= 2) {
is_cut[u] = true;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
// Tarjan算法可能从多个连通分量开始
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
// parent_edge_id 设为 -1 表示根节点
tarjan(i, -1);
}
}
// 输出割点
vector<int> cut_vertices;
for (int i = 1; i <= n; ++i) {
if (is_cut[i]) {
cut_vertices.push_back(i);
}
}
cout << cut_vertices.size() << endl;
for (int i = 0; i < cut_vertices.size(); ++i) {
cout << cut_vertices[i] << (i == cut_vertices.size() - 1 ? "" : " ");
}
cout << endl;
// 输出割边(可选)
// sort(bridges.begin(), bridges.end());
// cout << "Bridges: " << endl;
// for(int id : bridges) {
// cout << id << " ";
// }
// cout << endl;
return 0;
}
注意:
- 在
tarjan函数中,传递parent_edge_id而不是parent_node是为了正确处理重边的情况。 - 对于非连通图,需要对每个未访问过的节点都调用一次
tarjan函数。
2.6.6 时间与空间复杂度分析
- 时间复杂度: Tarjan 算法的本质是一次深度优先搜索。每个节点和每条边都只会被访问常数次。因此,时间复杂度为
O(N+M) 。 - 空间复杂度: 算法需要邻接表存储图,以及
dfn和low等辅助数组,所以空间复杂度为O(N+M) 。
2.6.7 应用与例题
例题:洛谷 P3388 【模板】割点(割顶)
题目大意:
给一个
题解思路: 这道题就是割点定义的裸题。直接套用上面给出的 Tarjan 算法模板即可。
- 使用邻接表存储无向图。
- 初始化
dfn,low等数组。 - 从节点 1 开始(或者遍历所有节点以处理非连通图),调用
tarjan函数。 - 在
tarjan函数中,根据根节点和非根节点的判定法则,标记出所有割点。 - 最后,遍历
is_cut数组,输出所有被标记为true的节点。
代码与上面的模板基本一致,只需要按照题目的输入输出格式进行调整即可。这个模板是解决割点、割边问题的基础,必须熟练掌握。
2.7 【6】树的重心
2.7.1 什么是树的重心?
在一棵树中,每一个节点都有其独特的位置。我们可以想象一下,如果把一棵树的结构看作一个用小球(节点)和细杆(边)连接成的手机挂饰,那么是否有一个点,我们提着它,整个挂饰能达到最“平衡”的状态?这个点,在信息学中就被形象地称为树的重心。
更严谨的定义是:对于树中的一个节点
换句话说,重心是让树“最平衡”的点,它避免了某一个分支“过重”的情况。
一棵树可能有一个重心,也可能有两个重心。当有两个重心时,这两个重心一定是相邻的。
2.7.2 如何求解树的重心?
求解树的重心通常需要两次深度优先搜索(DFS)。
-
第一次 DFS: 这次 DFS 的目的是计算出以每个节点为根的子树的大小(即包含的节点总数)。我们用
size[u] 表示以节点u 为根的子树的大小。计算公式是:size[u] = 1 + \sum_{v \in \text{children}(u)} size[v] 。这里的1 代表节点u 本身。 -
第二次 DFS: 这次 DFS 的目的是遍历每个节点,并计算删除它之后,所产生的最大子树的大小。对于一个节点
u ,删除它之后,产生的子树分为两类:- 向下的子树:即以
u 的各个孩子节点v 为根的子树。它们的大小就是第一次 DFS 中已经计算出的size[v] 。 - 向上的部分:即除去以
u 为根的整个子树后,树剩下的部分。这部分的大小为n - size[u] ,其中n 是整棵树的总节点数。
对于节点
u ,我们把它所有向下子树的大小和向上部分的大小进行比较,取其中的最大值,记为max\_part[u] 。 我们的目标是找到一个节点u ,使得max\_part[u] 最小。这个节点就是树的重心。我们可以在第二次 DFS 的过程中,维护一个全局变量来记录当前找到的最小的
max\_part 值以及对应的重心节点编号。 - 向下的子树:即以
2.7.3 树的重心的性质
树的重心有一些非常重要的性质,在解决问题时非常有用:
- 以重心为根,所有子树的大小都不会超过整棵树大小的一半,即
size[v] \le n/2 。这是重心的核心性质,也是其“平衡”的体现。 - 树中所有节点到某个点的距离之和,当且仅当这个点是重心时最小。
- 一棵树最多有两个重心,且这两个重心相邻。
2.7.4 算法伪代码
// 全局变量
n: 树的总节点数
adj: 邻接表,存储树的结构
size: 数组,size[u] 存储以 u 为根的子树大小
max_part: 数组,max_part[u] 存储删除 u 后最大子树的大小
ans_node: 最终找到的重心节点
min_max_part: 记录最小的 max_part 值,初始为无穷大
// 第一次 DFS,计算子树大小
function DFS1(u, parent):
size[u] = 1
for each neighbor v of u:
if v is not parent:
DFS1(v, u)
size[u] = size[u] + size[v]
// 第二次 DFS,寻找重心
function DFS2(u, parent):
// 计算删除 u 后的最大子树大小
current_max = n - size[u] // 向上部分的大小
for each neighbor v of u:
if v is not parent:
current_max = max(current_max, size[v]) // 向下子树的大小
// 更新答案
if current_max < min_max_part:
min_max_part = current_max
ans_node = u
else if current_max == min_max_part and u < ans_node: // 如果有多个重心,取编号最小的
ans_node = u
// 递归处理子节点
for each neighbor v of u:
if v is not parent:
DFS2(v, u)
// 主过程
main():
读入 n 和树的边
DFS1(1, 0) // 从任意节点开始,比如 1 号节点,0 表示没有父节点
DFS2(1, 0)
输出 ans_node
注:实际上,两次DFS可以合并为一次。在计算完一个节点所有子树的size后,就可以立即计算该节点的max_part并更新答案。
2.7.5 C++ 代码模板
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
vector<int> adj[MAXN];
int n;
int sz[MAXN]; // sz[u] 存储以u为根的子树大小
int min_max_part = MAXN; // 记录最小的max_part值
int ans_node; // 存储重心编号
// 一次DFS完成所有操作
void find_centroid(int u, int parent) {
sz[u] = 1;
int current_max_part = 0; // 删除u后,产生的最大子树的大小
for (int v : adj[u]) {
if (v == parent) {
continue;
}
find_centroid(v, u);
sz[u] += sz[v];
current_max_part = max(current_max_part, sz[v]);
}
// 向上部分的大小
current_max_part = max(current_max_part, n - sz[u]);
// 更新重心
if (current_max_part < min_max_part) {
min_max_part = current_max_part;
ans_node = u;
} else if (current_max_part == min_max_part) {
ans_node = min(ans_node, u); // 若有多个重心,取编号最小的
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
find_centroid(1, 0);
cout << ans_node << endl;
return 0;
}
2.7.6 洛谷例题与题解
例题:P1364 医院设置
题意简述:
在一个由
题解思路:
这道题直接应用了树的重心的性质2:所有节点到某个点的加权距离之和,当且仅当这个点是加权重心时最小。
本题中,每个点的“重量”就是病人的数量。
我们可以把求解普通重心的过程稍作修改。在计算
-
diff[v]++ -
diff[LCA(u,v)] -= 2 经过
K 次操作后,进行一次DFS,求出每个点u 的子树差分和,这个和就是边(fa[u], u) 被经过的次数。 最后遍历所有边,求一个最大值即可。 这个点差分操作的逻辑是:u 的标记会给(u, \text{root}) 路径上所有边都+1,v 的标记也一样。而(LCA(u,v), \text{root}) 路径上的边被加了两次,所以需要在LCA(u,v) 处减2来抵消。LCA(u,v) 本身没有父边在路径上,所以这个操作是正确的。
2.11 【6】倍增
2.11.1 什么是倍增?
倍增(Binary Lifting)是一种重要的算法思想,它的核心是“二进制拆分”。一个整数可以被拆分成若干个2的次幂之和,例如
2.11.2 倍增在树上的应用
倍增在树上最经典的应用就是求解最近公共祖先 (LCA) 和查询k级祖先。
我们定义一个二维数组
由此我们得到一个递推式:
这个递推式是倍增的核心。它告诉我们,要想到达
2.11.3 预处理过程
预处理通常通过一次DFS完成。
- DFS遍历树:在DFS过程中,确定每个节点的深度
dep[u]和它的直接父节点fa[u][0]。 - 动态规划填充fa表:在DFS之后,我们用递推式
fa[u][k] = fa[ fa[u][k-1] ][k-1] 来填充整个fa 表。 循环的顺序是,外层循环k 从 1 到\log n ,内层循环u 从 1 到n 。这样能保证在计算fa[u][k] 时,fa[\cdot][k-1] 的值都已经被计算出来了。
2.11.4 查询k级祖先
如何找到节点
2.11.5 算法伪代码(预处理)
// 全局变量
MAX_LOGN = 20
fa[MAXN][MAX_LOGN]
dep[MAXN] // 深度
adj: 邻接表
// DFS 预处理深度和直接父节点
function dfs_pre(u, p, d):
dep[u] = d
fa[u][0] = p
for each neighbor v of u:
if v is not p:
dfs_pre(v, u, d + 1)
// 倍增预处理
function build_lca(root, n):
dfs_pre(root, 0, 1) // 假设根深度为1, 父节点为0
for k = 1 to MAX_LOGN-1:
for u = 1 to n:
if fa[u][k-1] != 0:
fa[u][k] = fa[ fa[u][k-1] ][k-1]
2.11.6 C++ 代码模板(k级祖先查询)
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MAXN = 100005;
const int LOGN = 17; // log2(100005)约等于16.6
vector<int> adj[MAXN];
int fa[MAXN][LOGN + 1];
int dep[MAXN];
int n;
void dfs_pre(int u, int p, int d) {
dep[u] = d;
fa[u][0] = p;
for (int v : adj[u]) {
if (v == p) continue;
dfs_pre(v, u, d + 1);
}
}
void build() {
dfs_pre(1, 0, 1); // 假设1为根
for (int k = 1; k <= LOGN; ++k) {
for (int u = 1; u <= n; ++u) {
if (fa[u][k - 1] != 0) {
fa[u][k] = fa[fa[u][k - 1]][k - 1];
}
}
}
}
int query_kth_ancestor(int u, int k) {
if (dep[u] <= k) return 0; // 不存在k级祖先
for (int i = LOGN; i >= 0; --i) {
if ((k >> i) & 1) { // 如果k的第i个二进制位是1
u = fa[u][i];
}
}
return u;
}
int main() {
cin >> n;
// ... 读入树的边 ...
build();
// ... 查询 ...
return 0;
}
2.11.7 洛谷例题与题解
例题:P1967 货车运输
题意简述: 给定一个图,求任意两点之间所有路径中,路径上边权的最小值的最大值。如果两点不连通,输出-1。
题解思路:
这个问题等价于求图的最大生成树上,两点之间路径的最小边权。因为要让最小边权最大化,我们肯定优先选择权值大的边来构建连通性,这就是最大生成树的定义。
所以第一步是使用Kruskal或Prim算法构建最大生成树。如果图不连通,建成的是一个森林。
第二步,问题转化为在树上查询两点
在查询
2.12 【6】最近公共祖先
2.12.1 什么是最近公共祖先?
最近公共祖先(Lowest Common Ancestor, LCA)是树形结构中一个非常基础且重要的概念。对于树中的两个节点
2.12.2 如何求解LCA(倍增法)?
求解LCA有多种方法,如暴力向上爬、Tarjan离线算法、转换为RMQ问题等。其中,倍增法是在线算法中综合效率和实现难度最优秀的方法之一,非常常用。
该方法分为预处理和查询两个阶段。
预处理阶段:
就是上一节讲的倍增预处理。通过一次DFS和一次DP,计算出 dep[u] (深度) 和 fa[u][k] (
查询阶段
- 将两点提到同一深度:
首先比较
u 和v 的深度,假设dep[u] < dep[v]。我们需要将较深的节点v 向上跳dep[v] - dep[u]步,使其与u 处于同一深度。这个跳跃过程可以用倍增高效完成,复杂度O(\log n) 。 - 两点同时向上跳,直到相遇:
现在
u 和v 在同一深度。- 如果此时
u 和v 已经是同一个节点,那么这个节点就是它们的LCA。 - 如果不是,说明它们的LCA还在更上方。我们需要让
u 和v 同步向上跳。关键是,我们要跳到LCA的子节点。 为了做到这一点,我们从大到小遍历k (从\log n 到 0)。如果fa[u][k] 不等于fa[v][k] ,说明它们跳了2^k 步之后仍然没有相遇,它们的LCA还在更上方。并且,这次跳跃是安全的(不会跳过LCA)。于是,我们就让它们都跳:u = fa[u][k],v = fa[v][k]。 当这个循环结束后,u 和v 就一定是LCA的两个不同的子节点。那么,它们的父节点fa[u][0]就是所求的LCA。
- 如果此时
查询阶段的时间复杂度为
2.12.3 算法伪代码(查询部分)
function LCA_Query(u, v):
// 1. 将两点提到同一深度
if dep[u] < dep[v]:
swap(u, v)
// 将 u 提升到和 v 同样深度
diff = dep[u] - dep[v]
for k = MAX_LOGN-1 down to 0:
if (diff >> k) & 1: // 如果 diff 的第 k 位是 1
u = fa[u][k]
// 2. 如果 v 是 u 的祖先,v 就是LCA
if u == v:
return u
// 3. 同步向上跳
for k = MAX_LOGN-1 down to 0:
if fa[u][k] != 0 and fa[u][k] != fa[v][k]:
u = fa[u][k]
v = fa[v][k]
// 此时 fa[u][0] 就是LCA
return fa[u][0]
2.12.4 C++ 代码模板
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 500005;
const int LOGN = 19; // log2(500005)
vector<int> adj[MAXN];
int fa[MAXN][LOGN + 1];
int dep[MAXN];
int n, m, s; // n节点, m查询, s根
void dfs_pre(int u, int p, int d) {
dep[u] = d;
fa[u][0] = p;
for (int v : adj[u]) {
if (v == p) continue;
dfs_pre(v, u, d + 1);
}
}
void build_lca() {
dfs_pre(s, 0, 1);
for (int k = 1; k <= LOGN; ++k) {
for (int u = 1; u <= n; ++u) {
if (fa[u][k - 1] != 0) {
fa[u][k] = fa[fa[u][k - 1]][k - 1];
}
}
}
}
int lca_query(int u, int v) {
if (dep[u] < dep[v]) {
swap(u, v);
}
int diff = dep[u] - dep[v];
for (int k = LOGN; k >= 0; --k) {
if ((diff >> k) & 1) {
u = fa[u][k];
}
}
if (u == v) {
return u;
}
for (int k = LOGN; k >= 0; --k) {
if (fa[u][k] != 0 && fa[u][k] != fa[v][k]) {
u = fa[u][k];
v = fa[v][k];
}
}
return fa[u][0];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> s;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
build_lca();
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
cout << lca_query(u, v) << "\n";
}
return 0;
}
2.12.5 洛谷例题与题解
例题:P3379 【模板】最近公共祖先(LCA)
题意简述: 给定一棵有根树和多次询问,每次询问两个节点的最近公共祖先。
题解思路: 这道题是LCA的模板题,可以直接使用上面介绍的倍增法来解决。
- 输入和建图:读入节点数
n 、查询数m 和根节点s 。然后读入n-1 条边,建立邻接表来表示树的结构。 - 预处理:调用
build_lca()函数。该函数首先通过一次DFS从根节点s 开始遍历整棵树,计算出每个节点的深度dep和直接父节点fa[u][0]。然后,使用动态规划填充fa数组,计算出所有节点的2^k 级祖先。 - 处理查询:循环
m 次,每次读入两个节点u, v ,调用lca_query(u, v)函数,并输出其返回值。
整个算法的预处理时间复杂度为
LCA是许多更复杂树上问题的基础构件,例如前面提到的树上差分、求树上两点距离 (
第三节\ \ \ \ 动态规划
:::
3.1 【4】动态规划的基本思路
在正式学习具体的动态规划模型之前,首先需要理解其核心思想。动态规划的本质是将一个复杂的问题分解为若干个更小的、相互关联的子问题,通过求解这些子问题,并记录它们的结果,最终组合成原问题的解。
3.1.1 什么是动态规划?
让我们从一个简单的例子开始:爬楼梯问题。
假设有一座
对于这个问题,可以进行简单的分析。要想到达第
- 从第
n-1 级爬1级上来。 - 从第
n-2 级爬2级上来。
因此,到达第
如果用
这个关系式是不是很眼熟?它就是著名的斐波那契数列。
这个过程就蕴含了动态规划最核心的思想:将原问题(如何到达第
动态规划解决的问题通常具备两个重要性质:
- 最优子结构 (Optimal Substructure):问题的最优解包含了其子问题的最优解。换句话说,一个大问题的最优解可以由小问题的最优解推导出来。在爬楼梯问题中,到达第
n 级的总方法数,就是由到达前面台阶的方法数(子问题的解)组合而成的。 - 无后效性 (No Aftereffect):一旦某个子问题的解确定下来,它将不再受后续决策的影响。当我们计算
f(i) 时,我们只关心f(i-1) 和f(i-2) 的值是多少,而不关心它们是如何计算出来的。未来的决策也不会反过来改变已经计算好的子问题的解。
3.1.2 动态规划的核心要素:状态与转移
在动态规划中,有两个核心概念:
- 状态 (State):状态是对问题在某个阶段的描述。通常用一个或多个变量来表示。在动态规划中,我们常常用一个数组来存储不同状态下的解,这个数组被称为“DP数组”。例如,在爬楼梯问题中,
dp[i]就是一个状态,它表示“到达第i 级的方法数”。 - 状态转移方程 (State Transition Equation):状态转移方程描述了不同状态之间的递推关系。它是动态规划的灵魂,指明了如何从一个或多个已知的子问题状态,计算出当前状态的解。爬楼梯问题中的状态转移方程就是:
dp[i] = dp[i-1] + dp[i-2]。
3.1.3 动态规划的解题步骤
通常,解决一个动态规划问题可以遵循以下四个步骤:
- 定义状态:明确
dp数组的含义。例如,dp[i]代表什么?dp[i][j]又代表什么?这是最关键的一步,一个好的状态定义会使后续步骤变得清晰。 - 寻找状态转移方程:找出当前状态和它依赖的前序状态之间的关系。这是动态规划最核心的一步。
- 确定初始状态(边界条件):任何递推都需要一个起点。例如,在爬楼梯问题中,
dp[0] = 1(在地面上也算一种方法),dp[1] = 1。 - 确定计算顺序:根据状态转移方程,通常需要从小规模的子问题开始计算,逐步推导到大规模的子问题。例如,要计算
dp[i],必须先计算出dp[i-1]和dp[i-2],所以计算顺序应该是从小到大遍历i。
通过这四个步骤,就可以构建出解决大多数动态规划问题的框架。
3.2 【4】简单一维动态规划
一维动态规划是指问题的状态可以用一个一维数组来表示。这是最基础、最简单的动态规划模型。
3.2.1 概念与模型
一维DP的状态通常定义为 dp[i],表示问题在规模为 i 时的解。其状态转移方程通常依赖于 dp[i-1], dp[i-2] ... 等前面的状态。
经典例题:最长上升子序列 (LIS)
给定一个长度为
例如,序列 (3, 1, 4, 1, 5, 9, 2, 6) 的最长上升子序列是 (1, 4, 5, 9) 或者 (1, 4, 5, 6),长度为4。
下面我们用动态规划的四步法来解决这个问题。
-
定义状态:
dp[i]表示以第i 个数a_i 结尾的最长上升子序列的长度。这个定义非常关键,必须是以a_i 结尾。 -
寻找状态转移方程: 对于第
i 个数a_i ,我们需要考虑如何计算dp[i]。为了构成一个以a_i 结尾的上升子序列,我们可以将a_i 接在前面某个上升子序列的末尾。 这个“前面”的子序列必须满足两个条件:- 它是一个上升子序列。
- 它的末尾元素必须小于
a_i 。
因此,我们可以遍历
j 从1 到i-1 ,如果a_j < a_i ,说明a_i 可以接在以a_j 结尾的上升子序列后面,形成一个新的、更长的上升子序列。这个新序列的长度就是dp[j] + 1。 由于我们要找最长的,所以需要遍历所有满足条件的j ,取其中的最大值。 所以,状态转移方程为: -
确定初始状态: 对于任何一个数
a_i ,它自身就可以构成一个长度为1的上升子序列。所以,dp[i]的初始值至少为1。dp[i] = 1(对于所有的i=1, 2, ..., N )。 -
确定计算顺序:
dp[i]的计算依赖于dp[1]到dp[i-1],所以我们应该按照i 从1 到N 的顺序来计算。 最终的答案不是dp[N],因为最长上升子序列不一定以a_N 结尾。答案应该是所有dp[i]中的最大值,即\max \{ dp[1], dp[2], ..., dp[N] \} 。
3.2.2 算法伪代码与C++模板
伪代码:
function LIS(A, N):
// A是输入序列,N是序列长度
dp = array of size N+1, initialized to 1
for i from 2 to N:
for j from 1 to i-1:
if A[j] < A[i]:
dp[i] = max(dp[i], dp[j] + 1)
max_len = 0
for i from 1 to N:
max_len = max(max_len, dp[i])
return max_len
C++代码模板:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 1005;
int a[MAXN];
int dp[MAXN];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
// 初始化
for (int i = 1; i <= n; ++i) {
dp[i] = 1;
}
// 状态转移
for (int i = 2; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
// 寻找最终答案
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans = max(ans, dp[i]);
}
cout << ans << endl;
return 0;
}
这个算法的时间复杂度是
3.2.3 洛谷例题与题解
例题:P1020 导弹拦截
题目大意: 第一问:求一个序列的最长不上升子序列的长度。 第二问:求最少需要多少个不上升子序列来覆盖整个序列。
题解:
-
第一问: “不上升”即“小于或等于”。这和我们刚才讲的最长上升子序列(LIS)非常相似,只需要把状态转移方程中的
<条件改为>=即可。 状态定义:dp[i]表示以第i 个导弹结尾的最长不上升子序列的长度。 状态转移方程:dp[i] = \max \{ dp[j] + 1 \} ,其中1 \le j < i 且a_j \ge a_i 。 初始条件:dp[i] = 1。 最终答案:\max \{ dp[1], ..., dp[n] \} 。 用O(n^2) 的DP方法即可解决。 -
第二问: 第二问的结论是一个非常著名的定理:Dilworth定理。对于一个偏序集,其最长反链的长度等于最小链划分的大小。在序列问题中,这个定理可以简化为: 一个序列的最长上升子序列的长度,等于将其划分为若干个不上升子序列时所需的最少子序列个数。 所以,第二问的答案就是原序列的最长上升子序列的长度。 因此,这个问题只需要分别求一次最长不上升子序列和最长上升子序列的长度即可。
注:对于这道题,数据范围较大,
O(n^2) 的算法只能通过部分测试点。更优的解法是使用贪心+二分查找,可以将时间复杂度优化到O(n \log n) ,这在后续进阶课程中会学习到。但作为一维DP的练习,理解O(n^2) 的解法是基础。
3.3 【5】简单背包类型动态规划
背包问题是动态规划中一个非常经典的分类,它有多种变体,但核心思想是相似的。这里我们从最基础的0/1背包开始。
3.3.1 0/1 背包问题
问题描述:
有
DP四步法分析:
-
定义状态: 解决背包问题,我们需要同时考虑两个维度:物品和容量。因此,状态也需要用二维来表示。
dp[i][j]:表示从前i 件物品中任意选择,放入一个容量为j 的背包中所能获得的最大价值。 -
寻找状态转移方程: 当我们决策第
i 件物品时,有两种选择:- 不放入第
i 件物品:如果我们不把第i 件物品放入背包,那么问题就转化为:用前i-1 件物品填满容量为j 的背包,能获得的最大价值。这个值就是dp[i-1][j]。 - 放入第
i 件物品:如果决定放入第i 件物品,前提是背包的容量必须足够大,即j \ge w_i 。放入后,背包的剩余容量为j - w_i 。此时,我们能获得第i 件物品的价值v_i ,再加上用前i-1 件物品填满剩余容量j - w_i 的背包所能获得的最大价值,即dp[i-1][j - w_i]。总价值为v_i + dp[i-1][j-w_i] 。
我们需要在这两种选择中取一个最优的(价值最大的)。因此,状态转移方程为:
如果 $j < w_i$,第 $i$ 件物品肯定放不下,只能选择不放: $dp[i][j] = dp[i-1][j]$ (当 $j < w_i$ 时) - 不放入第
-
确定初始状态:
dp[0][j] = 0(当没有物品可选时,任何容量的背包价值都为0)。 或者,可以认为dp数组在声明时默认为0,循环从i=1 开始即可。 -
确定计算顺序:
dp[i][j]依赖于dp[i-1]行的状态,所以外层循环应该是物品i 从1 到N ,内层循环是容量j 从1 到V 。
3.3.2 空间优化:滚动数组
观察状态转移方程,可以发现计算第 dp[i] 时,只用到了第
我们定义一维状态 dp[j]:表示容量为 dp[j] 更新的方程变为:
dp[j] = max(dp[j], dp[j - w[i]] + v[i])
这里有一个非常关键的细节:内层循环 j 必须从 V 向下遍历到 w[i]。
为什么?
思考一下,当我们计算 dp[j] 时,方程右边的 dp[j] 是代表不放第 dp[i-1][j]。而方程右边的 dp[j - w[i]],应该等于 dp[i-1][j - w[i]]。
如果 j 从小到大遍历,当我们计算 dp[j] 时,dp[j - w[i]] 可能已经被本次循环(关于物品 dp[i][j - w[i]] 的值,而不是我们需要的 dp[i-1][j - w[i]]。这就导致一件物品可能被重复放入,变成了完全背包问题。
而当 j 从大到小遍历时,我们计算 dp[j] 需要用到的 dp[j - w[i]] 还没有在本次循环中被更新,它保留的还是上一轮(关于物品
3.3.3 算法伪代码与C++模板
伪代码 (空间优化版):
function ZeroOneKnapsack(W, V, N, Cap):
// W: 重量数组, V: 价值数组, N: 物品数量, Cap: 背包容量
dp = array of size Cap+1, initialized to 0
for i from 1 to N:
for j from Cap down to W[i]:
dp[j] = max(dp[j], dp[j - W[i]] + V[i])
return dp[Cap]
C++代码模板:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 105; // 物品数量
const int MAXV = 1005; // 背包容量
int w[MAXN]; // 体积
int v[MAXN]; // 价值
int dp[MAXV];
int main() {
int n, V; // n: 物品数量, V: 背包容量
cin >> n >> V;
for (int i = 1; i <= n; ++i) {
cin >> w[i] >> v[i];
}
// dp数组默认初始化为0
for (int i = 1; i <= n; ++i) {
for (int j = V; j >= w[i]; --j) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[V] << endl;
return 0;
}
3.3.4 洛谷例题与题解
例题:P1048 采药
题目大意:
一个采药人有 time[i] 的时间,价值为 value[i]。问在规定时间内,能采到草药的最大总价值。
题解: 这是一个非常标准的0/1背包问题。
- 背包容量
V 就相当于总时间T 。 - 物品数量
N 就相当于草药数量M 。 - 每件物品的体积
w_i 就相当于采摘第i 株药花费的时间time[i]。 - 每件物品的价值
v_i 就相当于第i 株药的价值value[i]。
问题转化为:有 time[i],价值是 value[i],求最大总价值。
直接套用0/1背包的空间优化模板即可解决。
3.4 【5】简单区间类型动态规划
区间DP是一类在区间上进行动态规划的算法。它的主要思想是,通过合并小区间的信息来求得大区间的信息。
3.4.1 什么是区间DP?
区间DP的模型特征非常明显:
- 问题形式:通常是求解一个序列上,一段连续区间的最优值。例如,将一排石子合并成一堆的最小代价。
- 状态定义:状态通常用
dp[i][j]表示,代表区间[i, j]上的最优解。 - 状态转移:大区间的解由其内部的子区间合并而来。状态转移方程通常形式为:
dp[i][j] = min/max (dp[i][k] + dp[k+1][j] + cost)这里的k是区间[i, j]的一个“分割点”,cost是合并两个子区间的代价。我们需要遍历所有可能的分割点k来找到最优解。 - 计算顺序:因为大区间的解依赖于小区间的解,所以我们必须先计算出所有长度为2的区间的解,然后是长度为3的,以此类推,直到计算出整个区间
[1, n]的解。 通常的实现方式是:第一层循环枚举区间长度len,第二层循环枚举区间的起始点i,然后根据len和i计算出区间的结束点j。
3.4.2 经典例题:石子合并
问题描述:
有
DP四步法分析:
-
定义状态:
dp[i][j]表示将第i 堆到第j 堆石子合并成一堆的最小代价。我们的最终目标是求dp[1][N]。 -
寻找状态转移方程: 考虑区间
[i, j],它的最后一次合并,一定是将某个子区间[i, k]和它右边相邻的子区间[k+1, j]合并而成的(其中i \le k < j )。 将[i, k]合并的最小代价是dp[i][k],将[k+1, j]合并的最小代价是dp[k+1][j]。 当这两部分合并时,产生的代价是区间[i, j]内所有石子的总质量。 我们可以预处理一个前缀和数组sum,sum[i]表示前i 堆石子的总质量。那么区间[i, j]的石子总质量就是sum[j] - sum[i-1]。 因此,通过分割点k进行合并的总代价为:dp[i][k] + dp[k+1][j] + (sum[j] - sum[i-1])我们需要遍历所有可能的分割点k (从i 到j-1 ),找到使这个总代价最小的那个k 。 状态转移方程为:dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] + \sum_{t=i}^{j} w_t \} -
确定初始状态: 当区间长度为1时,即
i == j,只有一堆石子,不需要合并,所以代价为0。dp[i][i] = 0(对于所有的i=1, 2, ..., N )。 -
确定计算顺序:
- 外层循环枚举区间长度
len,从 2 到N 。 - 中层循环枚举区间的起始点
i,从 1 到N - len + 1 。 - 根据
len和i计算出结束点j = i + len - 1。 - 内层循环枚举分割点
k,从i到j - 1,进行状态转移。
- 外层循环枚举区间长度
3.4.3 算法伪代码与C++模板
伪代码:
function StoneMerge(W, N):
// W: 石子质量数组, N: 石子堆数
sum = prefix sum array of W
dp = 2D array of size (N+1)x(N+1), initialized to infinity
for i from 1 to N:
dp[i][i] = 0
for len from 2 to N:
for i from 1 to N - len + 1:
j = i + len - 1
for k from i to j - 1:
cost = sum[j] - sum[i-1]
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost)
return dp[1][N]
C++代码模板:
#include <iostream>
#include <algorithm>
#include <cstring> // For memset
using namespace std;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;
int w[MAXN];
int sum[MAXN];
int dp[MAXN][MAXN];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> w[i];
sum[i] = sum[i - 1] + w[i];
}
// 初始化dp数组
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; ++i) {
dp[i][i] = 0;
}
// 枚举区间长度
for (int len = 2; len <= n; ++len) {
// 枚举起始点
for (int i = 1; i <= n - len + 1; ++i) {
int j = i + len - 1; // 计算结束点
// 枚举分割点
for (int k = i; k < j; ++k) {
int cost = sum[j] - sum[i - 1];
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost);
}
}
}
cout << dp[1][n] << endl;
return 0;
}
3.4.4 洛谷例题与题解
例题:P1880 [NOI1995] 石子合并
题目大意:
在一个圆形的操场上摆放着
题解:
这个问题是经典石子合并问题的变体,区别在于石子是环形排列的。
处理环形问题有一个经典技巧:破环成链。
我们可以将原来长度为 (1, 2, 3, 4),新序列就是 (1, 2, 3, 4, 1, 2, 3, 4)。
这样,原来环上的任意一个长度为 (4, 1, 2, 3) 就对应新链上的 [4, 7] 这个区间。
于是,问题就转化为了:在这个长度为 dp[1][N], dp[2][N+1], ..., dp[N][2N-1],然后取其中的最小值和最大值。
具体实现时:
- 将输入的
N 个数存入数组w[1...N],然后复制一份到w[N+1...2N],即w[i+N] = w[i]。 - 计算这个新数组的前缀和
sum。 - 用区间DP的方法,计算出所有
dp[i][j]的值,其中1 \le i \le j < 2N 。 - 最后,遍历所有可能的长度为
N 的区间,找出最优解。min_ans = min(dp[1][N], dp[2][N+1], ..., dp[N][2*N-1])max_ans = max(dp[1][N], dp[2][N+1], ..., dp[N][2*N-1])(求最大值时,只需将min操作改为max,初始值设为0即可)。
这样,就通过“破环成链”的技巧,将一个环形DP问题转化为了我们熟悉的链上区间DP问题。
3.5 【6】多维动态规划
在前面的学习中,我们接触到的动态规划问题,其状态通常可以用一个一维数组来表示,例如
3.5.1 什么是多维动态规划?
多维动态规划,顾名思义,就是其状态表示是多维的。最常见的是二维动态规划,其状态通常用一个二维数组
可以做一个简单的类比:
- 一维DP:就像在一条数轴上前进,当前的位置只和之前的位置有关。例如,
f[i] 的值由f[i-1] 推导而来。 - 二维DP:就像在一个棋盘或地图上移动,当前位置
(i, j) 的状态,可能与它的上方(i-1, j) 和左方(i, j-1) 的状态都有关系。
多维动态规划的核心思想没有改变,依然是寻找最优子结构和设计状态转移方程。只是状态的定义变得更复杂,需要考虑的维度增加了。
3.5.2 多维动态规划的核心要素
解决一个多维DP问题,通常需要明确以下几个步骤:
- 状态定义:这是最关键的一步。需要明确
f[i][j] (或者更多维度f[i][j][k]... ) 究竟代表什么。一个好的状态定义应该满足无后效性,即当前状态的决策不会影响到之前的状态,同时它应该能包含推导出后续状态所需的所有信息。 - 状态转移方程:这是算法的灵魂。它描述了状态之间是如何演进的。你需要思考
f[i][j] 是如何由一个或多个“更小”的子问题状态(例如f[i-1][j] ,f[i][j-1] ,f[i-1][j-1] 等)计算出来的。 - 初始化:确定DP的边界条件或起始状态。就像多米诺骨牌,你需要推倒第一张牌。对于二维DP,通常需要初始化第0行和第0列,或者某个特定的起始点。
- 计算顺序:确保在计算一个状态
f[i][j] 时,所有它所依赖的状态都已经被计算出来。对于二维DP,通常是从小到大枚举i ,再从小到大枚举j ,即逐行逐列地填满整个DP表格。 - 最终答案:在所有状态都计算完毕后,确定问题的最终解在DP表格的哪个位置。有时是
f[n][m] ,有时是某一行或某一列的最大值。
3.5.3 经典例题:数字三角形 (P1216 [USACO1.5] Number Triangles)
这是一个非常经典的多维DP入门题,能很好地帮助理解其思想。
题目描述
观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径,使路径上所有数字的和最大。每一步可以从当前点走到左下方的点或右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
思路分析
-
状态定义:路径是从上到下走的,我们可以定义一个状态来表示“走到某一个点的最大路径和”。因此,定义
f[i][j] 为从金字塔顶端 (第1行第1列) 走到第i 行第j 列这个位置时,所能获得的最大数字和。 -
状态转移方程:考虑如何到达第
i 行第j 列的数字。根据题目规则,只能从它的左上方或右上方的点走过来。- 左上方的点是第
i-1 行的第j-1 列。 - 右上方的点是第
i-1 行的第j 列。 为了使得到达(i, j) 的路径和最大,我们应该从这两个可能的来源点中选择一个路径和更大的。所以,状态转移方程为:f[i][j] = \max(f[i-1][j-1], f[i-1][j]) + a[i][j] 其中
a[i][j] 是数字三角形中第i 行第j 列的数字本身。
- 左上方的点是第
-
初始化:整个过程的起点是金字塔的顶端,即第1行第1列。所以,初始状态为
f[1][1] = a[1][1] 。为了方便处理边界,可以让f[i-1][j-1] 或f[i-1][j] 在j=1 或j=i 时取到一个不会影响结果的值(例如0)。 -
计算顺序:我们发现,计算第
i 行的状态只需要第i-1 行的信息。所以,我们可以从上到下,逐行计算。对于每一行,从左到右计算即可。 -
最终答案:题目要求的是从最高点到底部任意处结束的最大路径和。这意味着终点可以是最后一行的任何一个位置。所以,最终答案就是最后一行所有
f[n][j] (其中1 \le j \le n ) 中的最大值。
伪代码
输入数字三角形 a[n][n]
定义二维数组 f[n+1][n+1] 并初始化为0
f[1][1] = a[1][1]
对于 i 从 2 到 n:
对于 j 从 1 到 i:
f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j]
max_sum = 0
对于 j 从 1 到 n:
max_sum = max(max_sum, f[n][j])
输出 max_sum
C++ 代码模板
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int a[N][N];
int f[N][N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
cin >> a[i][j];
}
}
// 初始化
f[1][1] = a[1][1];
// 状态转移
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
// f[i-1][0] 和 f[i-1][i] 默认是0,不会影响max结果
// 所以不需要特殊处理边界
f[i][j] = max(f[i-1][j - 1], f[i-1][j]) + a[i][j];
}
}
// 寻找最终答案
int ans = 0;
for (int j = 1; j <= n; ++j) {
ans = max(ans, f[n][j]);
}
cout << ans << endl;
return 0;
}
3.6 【6】树型动态规划
树型动态规划,简称树形DP,是一种在树形结构上进行的动态规划。与线性DP不同,树形DP的状态转移不再是简单的从前一个到后一个,而是依赖于树的父子关系。
3.6.1 什么是树型动态规划?
当一个问题可以被抽象成一个树形结构,并且问题的解可以通过解决其子树的解来合并得到时,我们通常可以考虑使用树形DP。
树形DP的典型特征是:
- 问题的输入是一个树结构。
- 状态定义通常与树的节点有关,例如
f[u][...] 表示在以节点u 为根的子树中,满足某种条件的最优解。 - 状态的转移依赖于其子节点的DP结果。
为了实现这种依赖关系,树形DP通常和树的遍历算法(深度优先搜索DFS)结合在一起。计算一个节点的状态,需要先递归地计算完它所有子节点的状态,这个过程天然地符合DFS的回溯过程。
3.6.2 树型动态规划的核心要素
- 找到树的根:对于有根树,根是明确的。对于无根树,可以任选一个节点作为根,或者根据题意找到一个合适的根。
- 状态定义:定义
f[u][\text{state}] ,其中u 是当前节点编号,\text{state} 是一个附加状态。这个附加状态非常重要,通常表示节点u 本身的某种选择或情况。例如,\text{state} 可以是0或1,代表节点u 是否被选中。 - 状态转移方程:在DFS回溯的过程中,当一个节点
u 的所有子节点v_1, v_2, \dots 都已经访问完毕并计算出了它们的DP值后,就可以利用这些子节点的DP值来计算节点u 的DP值。f[u][\text{state}_u] = \text{combine}(f[v_1][\text{state}_{v1}], f[v_2][\text{state}_{v2}], \dots) 这个
combine操作是根据具体题目逻辑来设计的。 - 遍历顺序:通常使用一次DFS来完成整个DP过程。在DFS函数中,先递归进入所有子节点,在从子节点回溯之后,进行状态转移计算。这保证了在计算父节点时,其所有子节点的状态都已是最终结果。
3.6.3 经典例题:没有上司的舞会 (P1352)
题目描述
某大学有
思路分析
-
模型抽象:这是一个典型的树形结构。每个职员是一个节点,上级关系是树的边。问题是在这个树上选出一些点(参加舞会),要求任意被选中的点都没有父子关系,并使得这些点的权值(快乐指数)之和最大。这被称为“树的最大权独立集”问题。
-
状态定义:对于每个职员(节点
u ),他有两种状态:参加舞会或不参加舞会。这两种选择会影响其子节点的决策。因此,我们需要为每个节点定义两种状态: -
-
状态转移方程:我们通过一次DFS,从叶子节点往根节点计算。对于当前节点
u 和它的每一个直接下属(子节点)v :- 计算
f[u][1] :如果邀请了u ,那么根据规则,它的所有直接下属v 都不能参加。所以,u 参加时能获得的最大快乐指数,等于u 自己的快乐指数,加上它所有子树在“子节点不参加”情况下的最大快乐指数。f[u][1] = \text{happy}[u] + \sum_{v \in \text{children}(u)} f[v][0] - 计算
f[u][0] :如果不邀请u ,那么对于它的每个直接下属v ,我们可以自由选择邀请或不邀请v 。为了整体快乐指数最大,我们应该为每个子树选择最优的方案,即\max(f[v][0], f[v][1]) 。f[u][0] = \sum_{v \in \text{children}(u)} \max(f[v][0], f[v][1])
- 计算
-
初始化/边界:对于叶子节点(没有下属的职员)
u :-
f[u][1] = \text{happy}[u] -
f[u][0] = 0 这个初始化过程可以在DFS中自然完成。
-
-
最终答案:整个公司的舞会快乐指数最大值,取决于校长(树的根节点)是否参加。所以最终答案是
\max(f[\text{root}][0], f[\text{root}][1]) 。我们需要先找到谁是根节点(没有上司的那个职员)。
伪代码
// 邻接表存储树
// has_parent[i] 记录i是否有父节点,用于找根
// DFS函数,计算节点u的DP值
function dfs(u):
// 初始化当前节点u的值
f[u][1] = happy[u]
f[u][0] = 0
// 遍历u的每一个子节点v
对于 u 的每个子节点 v:
dfs(v) // 递归计算子节点的DP值
// 状态转移
f[u][0] = f[u][0] + max(f[v][0], f[v][1])
f[u][1] = f[u][1] + f[v][0]
// 主函数
读入数据,建树,记录父子关系
找到根节点 root (has_parent[root] == false)
dfs(root)
输出 max(f[root][0], f[root][1])
C++ 代码模板
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 6005;
int happy[N];
vector<int> son[N]; // 存储每个节点的直接下属(子节点)
bool has_father[N];
long long f[N][2]; // f[i][1]表示i参加, f[i][0]表示i不参加
void dfs(int u) {
// 初始化
f[u][1] = happy[u];
f[u][0] = 0;
// 遍历所有子节点
for (int i = 0; i < son[u].size(); ++i) {
int v = son[u][i];
// 递归计算子节点的DP值
dfs(v);
// 根据子节点的DP值更新父节点的DP值
f[u][1] += f[v][0];
f[u][0] += max(f[v][0], f[v][1]);
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> happy[i];
}
for (int i = 0; i < n - 1; ++i) {
int l, k;
cin >> l >> k; // l是k的上司
son[k].push_back(l);
has_father[l] = true;
}
// 找到根节点
int root = 1;
while (has_father[root]) {
root++;
}
// 从根节点开始进行树形DP
dfs(root);
// 输出最终答案
cout << max(f[root][0], f[root][1]) << endl;
return 0;
}
3.7 【7】状态压缩动态规划
状态压缩动态规划(简称状压DP)是一种特殊的动态规划,它通过将一个“状态集合”压缩成一个整数来表示,从而解决了某些看似状态数量庞大、无法用常规DP处理的问题。
3.7.1 为什么需要状态压缩?
在一些DP问题中,状态的一个维度可能不是一个简单的数字,而是一个集合。例如,我们需要知道“当前已经访问了哪些城市”或者“棋盘的这一行中,哪些位置已经放了棋子”。
如果城市数量是
一个
- 第
i 位是 1,代表集合中包含第i 个元素。 - 第
i 位是 0,代表集合中不包含第i 个元素。
这样,一个复杂的状态集合就被“压缩”成了一个整数。
3.7.2 核心工具:位运算
状压DP离不开位运算。以下是几个关键的位运算操作,假设我们用整数 mask 来表示集合:
- 判断元素
i是否在集合中:if (mask & (1 << i))1 << i会生成一个只有第i位是1的二进制数。&(按位与) 运算后,如果结果不为0,说明mask的第i位也是1。
- 将元素
i加入集合:mask = mask | (1 << i)|(按位或) 运算可以将mask的第i位置为1,而不改变其他位。
- 从集合中移除元素
i:mask = mask & (~(1 << i))或者mask = mask ^ (1 << i)(当确定i在集合中时)^(按位异或) 可以翻转指定位。
- 表示空集:
0 - 表示包含所有
N 个元素的全集:(1 << N) - 1,这是一个所有前N 位都是1的二进制数。
注意:在代码实现中,我们通常用 1 << i 表示第 i 个元素(从0开始计数)。如果问题是从1开始编号,那么第 i 个元素对应 1 << (i-1)。
3.7.3 状态压缩DP的核心要素
- 识别状压特征:题目的数据范围是关键信号。当看到某个关键维度
N 的范围特别小,比如N \le 20 ,就要考虑是否可以使用状压DP。 - 状态定义:状态通常包含一个压缩后的整数。例如,
f[\text{mask}][i] 表示当前访问过的城市集合是mask,并且最后停留在城市i时的最优解。 - 状态转移方程:思考如何从一个“小”的集合状态转移到一个“大”的集合状态。通常是枚举当前集合
mask,再枚举集合中的最后一个元素i,然后考虑它是从哪个元素j转移过来的。f[\text{mask}][i] = \text{最优操作}(f[\text{mask} \setminus \{i\}][j] + \text{cost}(j, i)) 这里的
\text{mask} \setminus \{i\} 表示从集合mask中去掉元素i,在位运算中对应mask ^ (1 << i)。 - 计算顺序:通常按照集合的大小(即二进制表示中1的个数)从小到大进行转移。或者直接从
1到(1 << N) - 1遍历mask,因为任何mask所依赖的mask'必然比mask小,所以这样遍历是有效的。
3.7.4 经典例题:最短Hamilton路径 (P1171)
这是一个状压DP的模板题,本质是旅行商问题(TSP)的简化版。
题目描述
给定一张
思路分析
-
识别状压特征:
N \le 20 ,这个数据范围是状压DP的强烈暗示。我们需要记录“哪些点被访问过”,这个集合可以用一个整数来压缩。 -
状态定义:我们需要知道两个信息:当前访问过的点的集合,以及当前路径的终点是哪个点。
- 定义
f[\text{mask}][i] :表示访问过的点集为mask,且当前停留在点i时的最短路径长度。 mask是一个整数,它的二进制表示中,第j位为1表示点j已经被访问过。i必须是mask集合中的一个点。
- 定义
-
状态转移方程:考虑如何计算
f[\text{mask}][i] 。要想到达状态(mask, i),上一步必然是在另一个状态(mask', j)。- 这个
mask'是mask去掉点i后的集合。位运算表示为mask ^ (1 << i)。 j是mask'集合中的任意一个点。- 从
j走到i的成本是dist[j][i]。 - 为了让路径最短,我们应该从所有可能的上一个点
j中,选择一个能使总路径最短的。 所以,状态转移方程为:f[\text{mask}][i] = \min_{j \in \text{mask'}, j \neq i} \{ f[\text{mask'}][j] + \text{dist}[j][i] \} 其中
mask'是mask ^ (1 << i)。
- 这个
-
初始化:
- 首先将所有
f 值初始化为一个极大值(表示不可达)。 - 起点是
0 。初始状态是只访问了点0 ,并且停留在点0 。所以f[1][0] = 0 。(mask=1的二进制是...001,表示只访问了第0个点)。
- 首先将所有
-
计算顺序:
- 外层循环枚举状态
mask,从1到(1 << N) - 1。 - 中层循环枚举当前终点
i,从0到N-1。 - 内层循环枚举上一个终点
j,从0到N-1。 - 在转移时,需要判断
i和j是否在对应的集合中。
- 外层循环枚举状态
-
最终答案:题目要求经过所有点,最后到达点
N-1 。- “经过所有点”对应的集合是全集,即
mask = (1 << N) - 1。 - “最后到达点
N-1 ”意味着我们寻找的答案是f[(1 \ll N) - 1][N-1] 。
- “经过所有点”对应的集合是全集,即
伪代码
输入邻接矩阵 dist[N][N]
定义 f[(1<<N)][N],并全部初始化为无穷大
// 初始化起点
f[1][0] = 0
// 遍历所有状态集合
对于 mask 从 1 到 (1 << N) - 1:
// 遍历当前集合的终点 i
对于 i 从 0 到 N-1:
// 如果 i 在集合 mask 中
if (mask & (1 << i)):
// 遍历上一个终点 j
对于 j 从 0 到 N-1:
// 如果 j 在集合 mask 中, 且 j 不等于 i
if ((mask & (1 << j)) and (i != j)):
// 考虑从 j 转移到 i
// 上一个状态的集合是 mask 去掉 i
prev_mask = mask ^ (1 << i)
// 确保 j 在上一个状态的集合中
if (prev_mask & (1 << j)):
f[mask][i] = min(f[mask][i], f[prev_mask][j] + dist[j][i])
输出 f[(1 << N) - 1][N - 1]
C++ 代码模板
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
const int INF = 0x3f3f3f3f;
int dist[N][N];
int f[1 << N][N]; // 1 << N 表示 2^N
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> dist[i][j];
}
}
// 初始化DP数组
memset(f, 0x3f, sizeof(f));
// 起点状态
f[1][0] = 0; // mask=1表示只经过了0号点,当前在0号点
// 遍历所有状态集合
for (int mask = 1; mask < (1 << n); ++mask) {
// 遍历当前终点 i
for (int i = 0; i < n; ++i) {
// 确保 i 在集合 mask 中
if (mask & (1 << i)) {
// 遍历上一个终点 j
for (int j = 0; j < n; ++j) {
// 确保 j 也在集合 mask 中,且 j != i
// 并且 j 是从去掉i之前的集合转移来的
int prev_mask = mask ^ (1 << i);
if (prev_mask & (1 << j)) {
f[mask][i] = min(f[mask][i], f[prev_mask][j] + dist[j][i]);
}
}
}
}
}
cout << f[(1 << n) - 1][n - 1] << endl;
return 0;
}
:::align{center}
第四节\ \ \ \ 字符串算法
:::
字符串是信息学竞赛中一种非常基础而又重要的数据类型。在前面的学习中,我们已经接触了字符串的基本操作。本章将深入探讨两种高效的字符串处理算法:KMP 算法和 Manacher 算法。它们分别是解决字符串匹配和最长回文子串问题的利器,能够将原本朴素算法的平方级复杂度优化到线性复杂度,是每一位追求更高水平的 Oier 必须掌握的核心知识。
4.1 【6】字符串匹配:KMP算法
4.1.1 朴素的字符串匹配:一个引子
在讨论 KMP 算法之前,我们首先需要理解它要解决的问题是什么。这个问题就是字符串匹配:给定一个主字符串(通常称为文本串)
例如,文本串
一个最容易想到的方法是“暴力匹配”,或者叫朴素算法。它的思路非常直接:
- 将
P 的开头对准T 的第 1 个字符。 - 逐一比较
P 和T 对应位置的字符。 - 如果所有字符都匹配成功,就记录下这个位置。
- 如果中途有一个字符不匹配,就将
P 整体向右移动一位,回到第 2 步,从T 的第 2 个字符开始重新比较。 - 重复这个过程,直到
P 的开头对准了T 中所有可能的位置。
让我们用上面的例子模拟一下:
-
-
-
- ... 以此类推
这个算法虽然直观,但效率不高。在最坏情况下,例如在文本串
4.1.2 KMP算法的核心思想:聪明的“跳跃”
朴素算法的低效根源在于,它在失配后没有利用任何已知的信息,只是盲目地将模式串右移一位。而 KMP 算法的精髓就在于,它能充分利用已经匹配过的信息,在失配后进行一次聪明的“跳跃”,从而跳过大量不必要的比较。
这个“已知的信息”是什么呢?信息就藏在模式串
设想一下,当我们在文本串
朴素算法会把
KMP 算法的答案是:可以。我们可以在已经匹配的模式串部分
前缀和后缀
- 前缀:指字符串中从第一个字符开始的任意长度的连续子串(不包括字符串本身)。例如,字符串 "ababa" 的前缀有 "a", "ab", "aba", "abab"。
- 后缀:指字符串中到最后一个字符结束的任意长度的连续子串(不包括字符串本身)。例如,字符串 "ababa" 的后缀有 "a", "ba", "aba", "baba"。
最长公共前后缀 就是在一个字符串的所有“前缀”和“后缀”中,找到一个最长的、内容相同的字符串。 例如,对于 "ababa":
- 前缀集合:{"a", "ab", "aba", "abab"}
- 后缀集合:{"a", "ba", "aba", "baba"}
- 公共前后缀有 "a" 和 "aba"。其中最长的是 "aba",长度为 3。
现在回到失配的场景。当
结合上面两个等式,我们可以推导出:
这个推导非常关键!它告诉我们,文本串中
为了实现这个聪明的“跳跃”,我们需要对模式串 next 数组(或 border 数组、fail 数组)中。next[j] 的值,就定义为
例如,对于模式串
next[1]("a"): 0next[2]("ab"): 0next[3]("aba"): "a"是公共前后缀,长度为 1。next[3] = 1。next[4]("abab"): "ab"是公共前后缀,长度为 2。next[4] = 2。next[5]("ababc"): 0
4.1.3 如何计算next数组?
计算 next 数组的过程,是一个“自己匹配自己”的过程。我们可以用递推的方式来计算。假设我们已经求出了 next[1], next[2], ..., next[i-1],现在要求 next[i]。
我们使用两个指针,i 和 j。指针 i 从 2 遍历到 next[i]。指针 j 代表 j = next[i-1]。
- 我们比较
P[i] 和P[j+1] 。 - 如果
P[i] == P[j+1] ,说明P[1 \dots i-1] 的最长公共前后缀后面接上一个P[i] ,恰好等于P[1 \dots j] 的最长公共前后缀后面接上一个P[j+1] 。这样,我们就找到了一个更长的公共前后缀。所以next[i] = j + 1。 - 如果
P[i] \ne P[j+1] ,说明直接扩展失败了。我们需要在P[1 \dots j] 中寻找一个更短的公共前后缀,然后再次尝试匹配。P[1 \dots j] 的最长公共前后缀是P[1 \dots \text{next}[j]] ,所以我们就令j = next[j],然后回到步骤 1,继续比较P[i] 和新的P[j+1] 。这个过程不断重复,直到j 变为 0(表示找不到任何公共前后缀)或者匹配成功。
伪代码:计算next数组
GET_NEXT(P, m):
next[1] = 0
j = 0
FOR i FROM 2 TO m:
WHILE j > 0 AND P[i] != P[j+1]:
j = next[j]
IF P[i] == P[j+1]:
j = j + 1
next[i] = j
RETURN next
C++ 代码模板:计算next数组
// P是模式串,长度为m
// next数组存储结果
void get_next(char P[], int m, int next[]) {
next[1] = 0;
for (int i = 2, j = 0; i <= m; i++) {
while (j > 0 && P[i] != P[j + 1]) {
j = next[j];
}
if (P[i] == P[j + 1]) {
j++;
}
next[i] = j;
}
}
4.1.4 KMP算法的完整流程
有了 next 数组,KMP 匹配过程就变得非常清晰了。我们同样使用两个指针,i 遍历文本串 j 遍历模式串
- 从
i=1, j=0开始。 - 比较
T[i] 和P[j+1] 。 - 如果
T[i] == P[j+1] ,则两个指针都向后移动,即i++,j++。 - 如果
j 移动到了m (模式串末尾),说明我们找到了一个完整的匹配。记录下匹配的起始位置i-m+1。然后,为了继续寻找下一个可能的匹配,我们不能让j停在这里,而是应该让它“跳跃”到next[m]的位置,即j = next[j],继续匹配过程。 - 如果
T[i] \ne P[j+1] ,失配发生。此时,文本串的指针i不需要回溯,模式串的指针j则利用next数组进行跳跃,令j = next[j]。然后回到步骤 2,比较新的P[j+1] 和T[i] 。如果j已经为 0 仍失配,说明当前T[i] 无法与P 的任何一个前缀的后继字符匹配,则直接i++。
伪代码:KMP匹配
KMP_MATCH(T, n, P, m, next):
j = 0
FOR i FROM 1 TO n:
WHILE j > 0 AND T[i] != P[j+1]:
j = next[j]
IF T[i] == P[j+1]:
j = j + 1
IF j == m:
PRINT "找到一个匹配,起始位置为", i - m + 1
j = next[j] // 继续寻找下一个匹配
C++ 代码模板:KMP算法
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// T是文本串,长度为n
// P是模式串,长度为m
// next数组由get_next函数计算得出
// 假设字符串下标从1开始
void kmp_search(char T[], int n, char P[], int m, int next[]) {
for (int i = 1, j = 0; i <= n; i++) {
while (j > 0 && T[i] != P[j + 1]) {
j = next[j];
}
if (T[i] == P[j + 1]) {
j++;
}
if (j == m) {
// 找到一个匹配,起始位置是 i - m + 1
cout << i - m + 1 << endl;
// 继续寻找下一个可能的匹配
// 这等价于模式串P[1...next[m]]与文本串T的对应部分已经匹配
j = next[j];
}
}
}
KMP算法通过 next 数组避免了主串指针 i 的回溯,并且模式串指针 j 的移动(包括增加和跳跃)总次数是线性的。因此,计算 next 数组的时间复杂度是
4.1.5 洛谷例题:P3375 【模板】KMP字符串匹配
题目描述
给出两个字符串
s_1 和s_2 ,其中s_2 为s_1 的前缀,求出s_2 在s_1 中所有出现的位置。 为了减少输出量,您只需要输出s_2 在s_1 中所有出现的位置的起始下标(下标从 1 开始)。 另外,您还需要输出s_2 的next数组。
题解思路 这道题是 KMP 算法的模板题。题目要求我们做两件事:
- 找出模式串(
s_2 )在文本串(s_1 )中所有出现的起始位置。 - 输出模式串(
s_2 )的next数组。
这完全符合我们上面学习的内容。我们只需要先调用 get_next 函数计算出 next 数组,然后将它输出。接着,调用 kmp_search 函数,在函数内找到匹配时输出起始位置即可。
参考代码
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MAXN = 1000005;
char s1[MAXN], s2[MAXN]; // 文本串和模式串
int next_arr[MAXN];
int n, m;
// 计算模式串s2的next数组
void get_next() {
next_arr[1] = 0;
for (int i = 2, j = 0; i <= m; i++) {
while (j > 0 && s2[i] != s2[j + 1]) {
j = next_arr[j];
}
if (s2[i] == s2[j + 1]) {
j++;
}
next_arr[i] = j;
}
}
// 在文本串s1中查找模式串s2
void kmp_search() {
for (int i = 1, j = 0; i <= n; i++) {
while (j > 0 && s1[i] != s2[j + 1]) {
j = next_arr[j];
}
if (s1[i] == s2[j + 1]) {
j++;
}
if (j == m) {
cout << i - m + 1 << endl;
j = next_arr[j];
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// cin读取字符串时,会自动在末尾添加'\0'
// C-style字符串的长度可以通过strlen获取,但我们直接用cin读取到s1+1, s2+1
// 这样可以直接使用1-based索引
cin >> (s1 + 1);
cin >> (s2 + 1);
// 计算字符串长度
n = 0;
while(s1[n + 1] != '\0') n++;
m = 0;
while(s2[m + 1] != '\0') m++;
get_next();
kmp_search();
for (int i = 1; i <= m; i++) {
cout << next_arr[i] << (i == m ? "" : " ");
}
cout << endl;
return 0;
}
4.2 【7】Manacher算法
4.2.1 最长回文子串:另一个挑战
回文串是指正读和反读都一样的字符串,例如 "level", "noon"。最长回文子串问题,就是给定一个字符串,找出其中最长的一个回文子串。
例如,对于字符串 "abacaba",最长回文子串是它本身。对于 "google",最长回文子串是 "goog"。
解决这个问题,同样可以从朴素算法入手。最直接的想法是:
- 枚举回文串的中心。
- 从这个中心开始,向两边同时扩展,判断两边的字符是否相等。
- 直到两边字符不相等,或者到达了字符串的边界,就找到了以该点为中心的最长回文串。
- 遍历所有的中心,记录下最长的回文串长度。
这里有一个细节:回文串的长度可能是奇数(如 "aba",中心是字符 'b'),也可能是偶数(如 "abba",中心是两个 'b' 之间的空隙)。所以,我们需要枚举
这种“中心扩展法”的思路是正确的,但效率如何?我们有大约
Manacher 算法(“马拉车”算法)正是解决这个问题的线性时间复杂度的算法。
4.2.2 Manacher算法的巧妙构思:化零为整
Manacher 算法的第一个巧妙之处,就是通过一个简单的预处理,将奇数长度和偶数长度的回文串统一起来处理。
方法是:在原字符串的每个字符之间,以及字符串的开头和结尾,都插入一个不会在原串中出现的特殊字符(例如 '#')。
- 原串
s = "aba"-> 新串t = "#a#b#a#" - 原串
s = "abba"-> 新串t = "#a#b#b#a#"
观察新串 t:
- 原先长度为奇数的回文串 "aba",在新串中变成了 "#a#b#a#",长度为 7,中心是 'b'。
- 原先长度为偶数的回文串 "abba",在新串中变成了 "#a#b#b#a#",长度为 9,中心是 'b' 和 'b' 中间的那个 '#'。
神奇的事情发生了:在新串 t 中,任何一个回文子串的长度都是奇数,并且它们的中心都落在了一个具体的字符上(要么是原字符,要么是 '#')!
这样,我们就不用再区分奇偶了,只需要用同一种方式——以每个字符为中心向外扩展——来寻找回文串。
为了方便记录,我们定义一个辅助数组 p,其中 p[i] 表示以新串 t 中第 i 个字符为中心的最长回文子串的半径。例如,对于 t = "#a#b#a#",以 'b' (下标为 4) 为中心的最长回文子串是 "#a#b#a#",它的半径是 4(包含中心'b'自己,以及向一侧扩展的'#', 'a', '#')。
新串中的回文半径 p[i] 和原串中的回文长度有什么关系呢?
- 如果中心
t[i]是原字符,如 "aba" -> "#a#b#a#" 中以 'b' 为中心的回文串,p[4]=4,对应原串长度为p[4]-1 = 3。 - 如果中心
t[i]是 '#',如 "abba" -> "#a#b#b#a#" 中以中间的 '#' 为中心的回文串,p[5]=5,对应原串长度为p[5]-1 = 4。
可以发现,规律是统一的:新串中以 i 为中心的回文串,在原串中对应的回文子串长度就是 p[i] - 1。因此,我们只需要求出所有 p[i] 的最大值,就能得到最长回文子串的长度。
4.2.3 加速扩展:利用已知回文信息
解决了奇偶问题后,我们依然面临着
算法维护两个变量:
max_right: 到目前为止,所有找到的回文串中,其右边界能到达的最远位置。mid: 对应max_right的那个回文串的中心。
当我们从左到右计算 p[i] 时,假设我们正在计算位置 i 的回文半径:
-
如果
i在max_right的右边 (即i > max_right): 这说明我们对i位置一无所知,没有任何历史信息可以利用。我们只能老老实实地进行中心扩展,从半径为 1 开始,一点点尝试扩大,直到失败。然后用这个新找到的回文串更新max_right和mid。 -
如果
i在max_right的内部 (即i <= max_right): 这是 Manacher 算法的精华所在!因为i在以mid为中心、右边界为max_right的大回文串内部,所以我们可以利用回文的对称性。 找到i关于mid的对称点j,其坐标为j = 2 * mid - i。 由于j在i的左边,p[j]的值我们是已经计算出来的。现在我们有了来自
p[j]的宝贵信息。根据大回文串的对称性,以i为中心的回文串,在一定范围内,和以j为中心的回文串是镜像对称的。-
情况A:以
j为中心的回文串完全被包含在以mid为中心的大回文串的内部。 这意味着j的回文半径p[j]没有超出大回文串的左边界。根据对称性,i的回文半径p[i]至少也等于p[j]。所以我们可以直接令p[i] = p[j],并且此时无需继续扩展,因为p[j]的回文串两端已经是不同字符了,对称过来p[i]的两端也必然不同。 -
情况B:以
j为中心的回文串超出了以mid为中心的大回文串的左边界。 这意味着j的回文串有一部分在mid的大回文串之外。根据对称性,我们只能保证i的回文串在mid大回文串内部的部分是对称的。这部分的半径就是从i到max_right的距离,即max_right - i + 1。所以我们可以确定p[i]的值至少是max_right - i + 1。至于它能否更长,我们不知道,需要从这个基础上继续向外尝试扩展。
聪明的你可能发现,情况 A 和 B 可以合并。我们可以给
p[i]一个初始值min(p[j], max_right - i + 1),然后在这个基础上继续尝试中心扩展。在情况 A 下,p[j]更小,扩展一次就会失败;在情况 B 下,max_right - i + 1更小或相等,我们从这个保底值继续扩展。 -
在每次计算完 p[i] 后,如果 i + p[i] - 1 的值超过了当前的 max_right,我们就更新 max_right 和 mid。
4.2.4 Manacher算法的复杂度
为什么这样就能把复杂度降到 max_right 这个变量。在整个算法流程中,max_right 只会不断地向右移动,永远不会向左回退。
暴力扩展(while 循环)只会在我们尝试将 max_right 推向更右边的时候才会执行。max_right 最多从 1 移动到 for 本身也是
4.2.5 算法实现与模板
伪代码:Manacher算法
MANACHER(s):
t = 预处理字符串s,加'#'
n = length of t
p = new array of size n
mid = 0, max_right = 0
FOR i FROM 1 TO n-1:
IF i <= max_right:
p[i] = min(p[2*mid - i], max_right - i + 1)
ELSE:
p[i] = 1
WHILE t[i - p[i]] == t[i + p[i]]: // 边界检查
p[i]++
IF i + p[i] - 1 > max_right:
max_right = i + p[i] - 1
mid = i
max_len = 0
FOR i FROM 1 TO n-1:
max_len = max(max_len, p[i] - 1)
RETURN max_len
C++ 代码模板:Manacher算法 为了防止中心扩展时数组越界,我们可以在预处理后的字符串开头再加一个永远不会匹配的字符,比如 '$'。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 22000005; // 2 * n + 5
char s[MAXN]; // 原字符串
char t[MAXN]; // 预处理后的字符串
int p[MAXN]; // 回文半径数组
// 预处理字符串
int init(char* str) {
int n = 0;
while(str[n] != '\0') n++;
t[0] = '$';
t[1] = '#';
int j = 2;
for (int i = 0; i < n; i++) {
t[j++] = str[i];
t[j++] = '#';
}
t[j] = '\0'; // 字符串结束符
return j; // 返回新字符串的长度
}
int manacher(char* str) {
int len = init(str);
int max_right = 0, mid = 0;
int max_len = 0;
for (int i = 1; i < len; i++) {
// 计算p[i]的初始值
if (i <= max_right) {
p[i] = min(p[2 * mid - i], max_right - i + 1);
} else {
p[i] = 1;
}
// 中心扩展
// 因为t[0]是'$',所以t[i-p[i]]不会越界到负数
while (t[i - p[i]] == t[i + p[i]]) {
p[i]++;
}
// 更新max_right和mid
if (i + p[i] - 1 > max_right) {
max_right = i + p[i] - 1;
mid = i;
}
// 更新答案
max_len = max(max_len, p[i] - 1);
}
return max_len;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> s;
cout << manacher(s) << endl;
return 0;
}
4.2.6 洛谷例题:P3829 【模板】Manacher算法
题目描述
给定一个字符串
s ,求其最长回文子串的长度。
题解思路 这道题目正是 Manacher 算法解决的经典问题。我们只需要将上述的 Manacher 算法模板应用到这道题中即可。
- 读入字符串
s。 - 调用
init函数对s进行预处理,得到新串t。 - 执行 Manacher 算法的核心循环,计算出
p数组。 - 在循环过程中,不断用
p[i] - 1更新最终答案max_len。 - 循环结束后,输出
max_len。
上述模板代码就是针对这个问题的完整解决方案。通过这道题,可以加深对 Manacher 算法的理解和代码实现能力的锻炼。