CSP-S 复赛指南（2025年版）

呼延冰枫 · 7 天前

此文章为 daiyulong 独家原创，耗时比较长。部分借助 AI。文章有点长（10 万字左右），请保持耐心。点击下载 PDF 版。
第一章$\ \ \ \ $数据结构

第一节$\ \ \ \ $线性结构

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 非常简单。首先需要包含头文件。

#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;
}

复制代码

注意：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 树将最近访问的节点移动到根，就是为了让下一次对它的访问变得极快（$O(1)$）。虽然单次操作的最坏情况复杂度可能是 $O(n)$（例如，访问一个深度最深的节点，然后把它旋转到根），但 Splay 树有一个非常强大的性质：均摊复杂度（Amortized Complexity）。

均摊复杂度：简单来说，虽然某一次操作可能很慢，但它会为后续的操作“铺路”，使得后续操作变快。将一系列操作的总时间除以操作次数，得到的平均时间复杂度是稳定的。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 循环自底向上进行旋转，这样更高效。

// 伪代码：滑动窗口最大值
// 数组 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

复制代码

注意：这里的 Splay 代码是一个更常见的竞赛模板写法。splay(p, goal) 的意思是将 p 旋转到 goal 的下方。当 goal 为 nullptr 时，就是将 p 旋转到根。这种写法在处理区间操作时非常有用。
2.7.3.5 Splay 的应用

Splay 树非常灵活，除了能完成普通平衡树的所有操作外，它的 splay 操作能方便地将任意节点置于根，这使得它在处理需要区间合并、分裂等操作的场景时特别强大。例如，文艺平衡树（洛谷 P3391）就是 Splay 的一个经典应用，通过 Splay 维护一个序列，可以实现区间翻转等复杂操作。
2.7.3.6 总结与对比

特性AVL 树TreapSplay 树平衡策略严格高度限制（平衡因子）随机优先级（堆性质）访问后伸展到根时间复杂度所有操作严格 $O(\log n)$所有操作期望 $O(\log n)$所有操作均摊 $O(\log n)$实现难度复杂，情况讨论多简单，代码短小中等，旋转逻辑需要清晰空间开销每个节点需存 height每个节点需存 priority每个节点需存 parent 指针常数较大（旋转频繁）较小较小（但splay操作长）适用场景查找密集，修改较少绝大多数平衡树场景有区间操作，或数据访问有局部性对于初学者和信息学竞赛选手来说，Treap 是最需要优先掌握的平衡树，因为它足够应对大多数模板题，且代码简单不易出错。Splay 树功能更强大，是进阶选手必须掌握的利器。而 AVL 树，则更多地作为理解平衡思想的经典案例出现在数据结构的教材中。
第三节$\ \ \ \ $哈希表

在信息学竞赛中，经常会遇到需要在庞大的数据集中快速查找、统计或判断某个元素是否存在的问题。如果数据范围非常大，例如，需要判断一个范围在 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） 是最常用也是最简单的一种。
它的思想非常直接：选择一个合适的正整数 $M$ ，对于任意的数值关键字 $key$ ，其哈希值 $H(key)$ 计算公式为：
$H(key) = key \pmod M$
这里的 $\pmod M$ 就是取 $key$ 除以 $M$ 的余数。例如，如果 $M=100$ ，那么学号 20240321 的哈希值就是 $20240321 \pmod {100} = 21$。这样，一个巨大的学号就被映射到了 0 到 99 的范围内。
如何选择 $M$ ？
$M$ 的选择至关重要，它直接影响到哈希冲突的概率。一个经验法则是：$M$ 应该选择一个不小于哈希表大小（即你需要的数组大小）的质数。
为什么是质数？举个例子，假设我们要存储的学号末尾数字都是偶数，如果我们选择 $M=10$ ，那么 $key \pmod {10}$ 的结果也都是偶数，哈希值 1, 3, 5, 7, 9 这些位置就永远不会被用到，而 0, 2, 4, 6, 8 这些位置的冲突概率就大大增加了。但如果我们选择一个质数，比如 $M=97$ ，那么即使是规律性很强的输入数据，计算出的哈希值也会在 0 到 96 之间分布得更加均匀，从而有效减少冲突。
3.1.3 伪代码与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;
}

复制代码

C++ 代码模板：

●
/ \
● ●
/ \ /
● ● ●

复制代码

2.3.4 C++ 代码模板

[code]#include #include #include using namespace std;const int MAXN = 5005;const int INF = 0x3f3f3f3f;struct Edge { int to, weight;};vector 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 dist2) { continue; } for (const auto& edge : graph) { 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.push_back({v, w}); graph[v].push_back({u, w}); // 假设是无向图 } find_second_shortest(1); // 从 1 号点开始 cout > q; // 1. 初始化距离矩阵 for (int i = 1; i u >> v >> w; // 对于有重边的情况，只保留权值最小的边 dist[v] = min(dist[v], w); // 如果是无向图，加上下面这句 // dist[v] = min(dist[v], w); } // 3. 执行 Floyd-Warshall 算法 floyd_warshall(); // 4. 回答查询 for (int i = 0; i < q; ++i) { int u, v; cin >> u >> v; if (dist[v] >= INF / 2) { // 用 INF/2 判断是为了避免一些微小的误差 cout

账号		自动登录	找回密码
密码			立即注册

CSP-S 复赛指南（2025年版）

相关帖子

浏览过的版块

签约作者

CSP-S 复赛指南（2025年版）

相关帖子

相关推荐

浏览过的版块

签约作者