9 篇
记录 ACM 竞赛模式下常用数据结构的原理、模板与题型整理。
字符串哈希 字符串哈希可以把一个字符串映射成一个整数。预处理出所有前缀的哈希值后，就能在 $O(1)$ 时间内求出任意子串的哈希值，从而快速判断两个子串是否相同。 它和 KMP 都能解决字符串匹配问题，但擅长的场景不同： KMP 适合在线性时间内寻找一个固定模式串在文本中的所有出现位置； 字符串哈希适合预处理一个字符
哈希表 哈希表用于维护“键”与存储位置之间的映射。它通过哈希函数把范围很大的键映射到一个有限的下标范围，从而快速完成插入、查询等操作。 例如，要判断整数 x 是否已经出现，可以使用取模构造哈希函数： int k = (x % N + N) % N; 其中，k 是 x 对应的桶编号，范围为 $[0,N-1]$。 在 C
Trie 树 Trie 树也叫字典树，是一种按照“前缀”组织数据的树形结构。普通 Trie 常用于存储字符串：从根节点开始，每条边代表一个字符，从根到某个节点的路径就表示一个字符串前缀。 当数据是非负整数时，也可以把每个整数写成固定长度的二进制串，再存入 Trie。此时： 每个节点最多有两个子节点，分别表示下一位是
题目 AcWing 839. 模拟堆 #include <iostream> #include <string> #include <utility> using namespace std; const int N = 100010; // h[i]：堆中第 i 个位置存储的值 int h[N]; // hp
并查集 并查集（Disjoint Set Union，DSU）用于维护若干个互不相交的集合。它主要支持两类操作： 查询：判断两个元素是否属于同一个集合； 合并：把两个元素所在的集合合并成一个集合。 例如，在维护无向图的连通性时，可以把同一个连通块中的所有点看作一个集合。每加入一条连接两个点的边，就合并这两个点所在的
KMP 算法 字符串匹配问题中，给定一个长文本 s 和一个模式串 p，需要找出 p 在 s 中出现的所有位置。 朴素做法会从长文本的每个位置重新开始比较。当已经匹配了很多字符却在后面失配时，前面的比较结果就被全部丢弃，最坏时间复杂度为 $O(nm)$。 KMP 的核心思想是：长文本指针不回退，失配时利用已经匹配的内容，
栈和队列 栈和队列都是只能在特定位置插入、删除元素的线性数据结构： | 数据结构 | 插入位置 | 删除位置 | 访问顺序 | | --- | --- | --- | --- | | 栈 | 栈顶 | 栈顶 | 后进先出（LIFO） | | 队列 | 队尾 | 队头 | 先进先出（FIFO） | 在 ACM 模式中，如
#include <cstdio> #include <iostream> using namespace std; const int N = 100010; int head, M, ne[N], e[N], idex; void init() { head = -1; idex = 0; } v
双链表 双链表中的每个节点除了保存数据，还会同时保存前驱节点和后继节点的位置。因此，与单链表相比，双链表可以在 $O(1)$ 时间内完成以下操作： 在已知节点的左侧或右侧插入新节点； 删除一个已知节点； 从任意节点向左或向右移动。 在 ACM 模式中，如果操作次数已经确定，常用三个数组模拟双链表： int e[N]
