レム・咲く夜

LemuSakuya的个人博客网站堂堂登场

这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！

標籤

レム・咲く夜

LemuSakuya的个人博客网站堂堂登场

这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！

標籤

レム・咲く夜

LemuSakuya的个人博客网站堂堂登场

这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！

標籤

🌸 咲夜の秘密メロディ

分類

站點統計

文章

79

分類

16

標籤

24

總字數

394,971

運行天數

0 天

最後活動

0 天前

12059 字

31 分鐘

基础数据结构与语言工具

2026-06-03

Algorithm

Study Notes

/

Algorithm

第 2 章基础数据结构与语言工具#

本章目标：理解常用数据结构的能力边界，知道什么时候该选数组、栈、队列、堆、哈希表或树。

2.1 学习目标#

掌握数组、链表、栈、队列、堆、哈希表的基本操作和复杂度。
能根据题目操作类型选择合适数据结构。
熟悉 C++ STL 或 Python 常用容器的复杂度。
理解“接口”和“实现”的区别。
避免因容器误用导致超时或错误。

2.2 数组与动态数组#

数组是一段连续内存。优点是随机访问快：

\text{access}(a_i)=O(1)

缺点是中间插入和删除需要移动元素：

\text{insert/delete in middle}=O(n)

动态数组如 C++ 的 vector、Python 的 list，会在容量不足时扩容。单次 append 可能是 $O(n)$ ，但均摊是 $O(1)$ 。

均摊直觉：扩容不是每次发生，总移动成本可以分摊到多次插入上。

2.3 链表#

链表节点保存值和指针：

1
[value | next] -> [value | next] -> ...

链表适合已经知道节点位置后的插入删除： $O(1)$ 。但查找第 k 个元素需要从头走： $O(n)$ 。

面试中的链表题常考：

快慢指针找环。
反转链表。
合并有序链表。
删除倒数第 k 个节点。

2.4 栈#

栈是后进先出结构：

1
push -> 栈顶
2
pop  <- 栈顶

典型用途：

括号匹配。
表达式求值。
单调栈。
DFS 的显式栈。
函数调用栈。

括号匹配伪代码：

1
for (char c : s) {
2
    if (c == '(') st.push(c);
3
    else {
4
        if (st.empty()) return false;
5
        st.pop();
6
    }
7
}
8
return st.empty();

2.5 队列与双端队列#

队列是先进先出，适合 BFS：

1
push back -> [old ... new] -> pop front

双端队列 deque 两端都能进出，常用于单调队列维护窗口最值。

滑动窗口最大值中，每个元素最多入队一次、出队一次，因此总复杂度是 $O(n)$ 。

2.6 堆与优先队列#

堆支持快速取最小或最大元素。

操作	复杂度
取堆顶	$O(1)$
插入	$O(\log n)$
删除堆顶	$O(\log n)$

典型用途：

Top K。
合并 k 个有序序列。
Dijkstra 最短路。
Huffman 编码。
动态中位数。

Dijkstra 中堆内可能存在过期状态，常用懒删除：

1
while (!pq.empty()) {
2
    auto [d, u] = pq.top(); pq.pop();
3
    if (d != dist[u]) continue;
4
    relax(u);
5
}

2.7 哈希表#

哈希表把键映射到桶，平均查找复杂度接近 $O(1)$ 。

index = hash(key) \bmod m

注意：

键必须能唯一表示状态。
哈希冲突不可避免。
自定义结构要提供哈希函数。
字符串哈希可能碰撞，重要场景要二次校验。

2.8 常用容器复杂度#

容器	查找	插入	删除	备注
vector/list	按下标 $O(1)$	尾部均摊 $O(1)$	中间 $O(n)$	连续内存
stack	栈顶 $O(1)$	$O(1)$	$O(1)$	LIFO
queue	队首 $O(1)$	$O(1)$	$O(1)$	FIFO
priority_queue	堆顶 $O(1)$	$O(\log n)$	$O(\log n)$	动态最值
unordered_map	平均 $O(1)$	平均 $O(1)$	平均 $O(1)$	哈希
map/set	$O(\log n)$	$O(\log n)$	$O(\log n)$	有序树

2.9 选择数据结构的思路#

先问题目需要什么操作：

需求	常用结构
随机访问	数组、vector
最近未匹配元素	栈
层序扩展	队列
动态最大/最小	堆
快速存在性判断	哈希表
有序集合、前驱后继	平衡树、set
区间查询修改	树状数组、线段树

不要从“我会什么结构”出发，而要从“题目需要什么操作”出发。

2.10 易错点#

在 vector 中间频繁 erase 导致 $O(n^2)$ 。
用 set 但其实不需要有序，常数较大。
priority_queue 默认是大根堆。
unordered_map 的键设计不唯一。
Python list 头部 pop(0) 是 $O(n)$ ，队列应使用 deque。
使用递归 DFS 时忘记栈深度限制。

2.11 练习#

说明为什么动态数组 append 的均摊复杂度是 $O(1)$ 。
用栈判断括号序列是否合法。
用堆维护数据流中的前 k 大元素。
用哈希表统计数组中两数之和的方案。
写出 Python deque 维护滑动窗口最大值的伪代码。

ACM/OI 扩展：竞赛常用容器与手写结构#

本节补充 OIer 和 ACMer 常用的算法套路、模板、复杂度分析和易错点。写模板时默认使用 C++17，变量名尽量短，但注释要说明不变量和适用条件。

1. vector 邻接表#

大多数图论题用 vector 邻接表足够。若边数极大且需要极致性能，可用链式前向星。

1
vector<vector<pair<int,int>>> g(n + 1);
2
for (int i = 0; i < m; ++i) {
3
    int u, v, w;
4
    cin >> u >> v >> w;
5
    g[u].push_back({v, w});
6
    // g[v].push_back({u, w}); // 无向图打开
7
}

要点：

写无向图时加双向边。
需要清空时 g.assign(n + 1, {})。
若递归 DFS 爆栈，改成迭代或提高栈限制。

2. 链式前向星#

OI 传统写法，适合边数上限固定、需要频繁清空或性能敏感的图。

1
const int N = 200000 + 5;
2
const int M = 400000 + 5;
3
int head[N], to[M], nxt[M], w[M], ecnt;
4
void init(int n) {
5
    fill(head, head + n + 1, -1);
6
    ecnt = 0;
7
}
8
void addEdge(int u, int v, int c) {
9
    to[ecnt] = v; w[ecnt] = c; nxt[ecnt] = head[u]; head[u] = ecnt++;
10
}
11
for (int e = head[u]; e != -1; e = nxt[e]) {
12
    int v = to[e], c = w[e];
13
}

要点：

无向图需要调用两次 addEdge。
数组 M 要按边数乘 2。
遍历时 e 是边编号，不是点编号。

常见坑：

忘记 init head 为 -1。
M 开小导致越界。

3. 手写队列#

BFS 中 std::queue 通常够用；极限性能可用数组队列。

1
int q[N], hh = 0, tt = 0;
2
q[tt++] = s;
3
while (hh < tt) {
4
    int u = q[hh++];
5
    for (int v : g[u]) {
6
        if (!vis[v]) {
7
            vis[v] = 1;
8
            q[tt++] = v;
9
        }
10
    }
11
}

要点：

数组队列不支持自动扩容。
BFS 入队时标记，避免重复入队。

4. policy based data structure#

GCC 扩展 tree 可维护有序集合并查询排名，部分 OJ 支持，部分不支持。

1
#include <ext/pb_ds/assoc_container.hpp>
2
#include <ext/pb_ds/tree_policy.hpp>
3
using namespace __gnu_pbds;
4
template<class T>
5
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
6

7
ordered_set<pair<int,int>> os;
8
// os.order_of_key(x): 小于 x 的数量
9
// *os.find_by_order(k): 第 k 小，0-index

要点：

处理重复元素时存 pair(value, id)。
不是标准 C++，比赛前确认评测环境。

5. 坐标压缩模板#

值域很大但只关心相对大小时使用离散化。

1
vector<int> xs = a;
2
sort(xs.begin(), xs.end());
3
xs.erase(unique(xs.begin(), xs.end()), xs.end());
4
a[i] = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin() + 1;

要点：

树状数组通常压缩到 1-index。
若需要原始距离，不能只保留排名。

训练题型：

用离散化 + 树状数组求逆序对。
用离散化处理区间覆盖长度。

本章模板背诵清单#

能在 5 分钟内写出本章第一个核心模板。
能说出每个模板的时间复杂度和空间复杂度。
能说明模板不适用的反例。
能为模板构造 3 个边界样例。
能把模板改成 0-index 或 1-index 版本。

STL 与手写结构补充#

multiset 的删除#

erase(value) 会删除所有等于 value 的元素；只删一个要用迭代器。

1
auto it = ms.find(x);
2
if (it != ms.end()) ms.erase(it);

滑动窗口中位数常用 multiset。
有重复值时必须小心 erase。

map / unordered_map 选择#

如果需要顺序、前驱后继，使用 map/set；只需要计数和存在性，使用 unordered_map。

map 是红黑树， $O(\log n)$ 。
unordered_map 平均 $O(1)$ ，但可能被卡。
键是 pair 时需要自定义 hash。

bitset 优化#

当布尔状态很多，bitset 可以用位运算一次处理 64 位或更多。

1
bitset<MAXN> reach;
2
reach[0] = 1;
3
for (int w : weights) reach |= (reach << w);

01 背包可用 bitset 优化可达性。
传递闭包可用 bitset 优化 Floyd。

pair / tuple 排序#

C++ pair 默认先按 first，再按 second 字典序排序。

1
vector<pair<int,int>> a;
2
sort(a.begin(), a.end());

区间按左端点排序可直接用 pair。
需要降序时写自定义比较器。

数组初始化技巧#

全局数组默认初始化为 0，局部大数组可能爆栈。

1
memset(dist, 0x3f, sizeof dist); // int INF
2
fill(vec.begin(), vec.end(), LINF);

memset 只适合 0、-1、0x3f 这类字节模式。
long long 数组用 fill 更稳。

高频模板训练卡#

这一组训练卡用于把“02_基础数据结构与语言工具”转化为赛场识别能力。每张卡都包含题目信号、模板选择、复杂度、反例和实现检查。

卡 1：vector 邻接表#

题目信号：需要 vector 邻接表支持高频操作。
优先模板：使用 vector 邻接表的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用 vector 邻接表写一个最小 demo 并压测 1e5 次操作。

卡 2：链式前向星#

题目信号：需要链式前向星支持高频操作。
优先模板：使用链式前向星的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用链式前向星写一个最小 demo 并压测 1e5 次操作。

卡 3：栈模拟递归#

题目信号：需要栈模拟递归支持高频操作。
优先模板：使用栈模拟递归的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用栈模拟递归写一个最小 demo 并压测 1e5 次操作。

卡 4：数组队列 BFS#

题目信号：需要数组队列 BFS 支持高频操作。
优先模板：使用数组队列 BFS 的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用数组队列 BFS 写一个最小 demo 并压测 1e5 次操作。

卡 5：priority_queue#

题目信号：需要 priority_queue 支持高频操作。
优先模板：使用 priority_queue 的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用 priority_queue 写一个最小 demo 并压测 1e5 次操作。

卡 6：set/multiset#

题目信号：需要 set/multiset 支持高频操作。
优先模板：使用 set/multiset 的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用 set/multiset 写一个最小 demo 并压测 1e5 次操作。

卡 7：unordered_map 防卡#

题目信号：需要 unordered_map 防卡支持高频操作。
优先模板：使用 unordered_map 防卡的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用 unordered_map 防卡写一个最小 demo 并压测 1e5 次操作。

卡 8：bitset 优化#

题目信号：需要 bitset 优化支持高频操作。
优先模板：使用 bitset 优化的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用 bitset 优化写一个最小 demo 并压测 1e5 次操作。

卡 9：坐标压缩#

题目信号：需要坐标压缩支持高频操作。
优先模板：使用坐标压缩的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用坐标压缩写一个最小 demo 并压测 1e5 次操作。

卡 10：pair 排序#

题目信号：需要 pair 排序支持高频操作。
优先模板：使用 pair 排序的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用 pair 排序写一个最小 demo 并压测 1e5 次操作。

卡 11：tuple 状态#

题目信号：需要 tuple 状态支持高频操作。
优先模板：使用 tuple 状态的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用 tuple 状态写一个最小 demo 并压测 1e5 次操作。

卡 12：手写小根堆#

题目信号：需要手写小根堆支持高频操作。
优先模板：使用手写小根堆的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用手写小根堆写一个最小 demo 并压测 1e5 次操作。

卡 13：双端队列#

题目信号：需要双端队列支持高频操作。
优先模板：使用双端队列的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用双端队列写一个最小 demo 并压测 1e5 次操作。

卡 14：环形队列#

题目信号：需要环形队列支持高频操作。
优先模板：使用环形队列的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用环形队列写一个最小 demo 并压测 1e5 次操作。

卡 15：内存池#

题目信号：需要内存池支持高频操作。
优先模板：使用内存池的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用内存池写一个最小 demo 并压测 1e5 次操作。

卡 16：结构体排序#

题目信号：需要结构体排序支持高频操作。
优先模板：使用结构体排序的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用结构体排序写一个最小 demo 并压测 1e5 次操作。

卡 17：全局数组初始化#

题目信号：需要全局数组初始化支持高频操作。
优先模板：使用全局数组初始化的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用全局数组初始化写一个最小 demo 并压测 1e5 次操作。

卡 18：PBDS 有序集合#

题目信号：需要 PBDS 有序集合支持高频操作。
优先模板：使用 PBDS 有序集合的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用 PBDS 有序集合写一个最小 demo 并压测 1e5 次操作。

卡 19：自定义 hash#

题目信号：需要自定义 hash 支持高频操作。
优先模板：使用自定义 hash 的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用自定义 hash 写一个最小 demo 并压测 1e5 次操作。

卡 20：离散化映射#

题目信号：需要离散化映射支持高频操作。
优先模板：使用离散化映射的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用离散化映射写一个最小 demo 并压测 1e5 次操作。

卡 21：桶计数#

题目信号：需要桶计数支持高频操作。
优先模板：使用桶计数的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用桶计数写一个最小 demo 并压测 1e5 次操作。

卡 22：压位存储#

题目信号：需要压位存储支持高频操作。
优先模板：使用压位存储的标准 C++17 写法或手写结构。
核心不变量：每次操作后结构内部顺序和计数保持合法。
复杂度目标：通常为 O(1)、O(log n) 或 O(n/word)。
不适用场景：操作需要顺序但使用哈希，或需要删除任意元素但使用堆。
实现检查：检查容器清空、重复元素、迭代器失效、下标起点。
边界样例：空容器、单元素、重复值、删除不存在元素。
训练题型：用压位存储写一个最小 demo 并压测 1e5 次操作。

本章赛前默写任务#

02_基础数据结构与语言工具：详细训练清单#

本清单用于把章节知识拆成可执行的小任务，偏 OI/ACM 赛场使用。

训练点 1：vector#

识别信号：题面出现与“vector”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“vector”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 2：array#

识别信号：题面出现与“array”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“array”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 3：deque#

识别信号：题面出现与“deque”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“deque”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 4：stack#

识别信号：题面出现与“stack”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“stack”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 5：queue#

识别信号：题面出现与“queue”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“queue”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 6：priority_queue#

识别信号：题面出现与“priority_queue”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“priority_queue”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 7：set#

识别信号：题面出现与“set”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“set”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 8：multiset#

识别信号：题面出现与“multiset”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“multiset”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 9：map#

识别信号：题面出现与“map”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“map”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 10：unordered_map#

识别信号：题面出现与“unordered_map”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“unordered_map”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 11：bitset#

识别信号：题面出现与“bitset”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“bitset”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 12：PBDS#

识别信号：题面出现与“PBDS”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“PBDS”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 13：链式前向星#

识别信号：题面出现与“链式前向星”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“链式前向星”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 14：坐标压缩#

识别信号：题面出现与“坐标压缩”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“坐标压缩”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 15：结构体排序#

识别信号：题面出现与“结构体排序”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“结构体排序”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 16：自定义 hash#

识别信号：题面出现与“自定义 hash”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“自定义 hash”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 17：内存池#

识别信号：题面出现与“内存池”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“内存池”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 18：手写队列#

识别信号：题面出现与“手写队列”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“手写队列”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 19：vector#

识别信号：题面出现与“vector”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“vector”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 20：array#

识别信号：题面出现与“array”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“array”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 21：deque#

识别信号：题面出现与“deque”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“deque”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

如果這篇文章對你有幫助，歡迎分享給更多人！

基础数据结构与语言工具

https://lemusakuya.com/posts/study-notes/algorithm/02_基础数据结构与语言工具/

作者

レム・咲く夜

發布於

2026-06-03

許可協議

部分資訊可能已經過時

相關文章智能推薦

Algorithm 《算法》学习笔记：11_高级数据结构与图论

2

树与图论基础

Algorithm 《算法》学习笔记：07_树与图论基础

3

数学算法与组合计数

Algorithm 《算法》学习笔记：10_数学算法与组合计数

4

算法学习总览与复杂度分析

Algorithm 《算法》学习笔记：01_算法学习总览与复杂度分析

5

算法设计与分析完全学习手册

Algorithm 《算法》学习总览与学习路线

隨機文章隨機推薦

1

Chapt2

Digital Image Processing 2026-06-03

2

数字图像处理（Digital Image Processing）完全学习手册

Digital Image Processing 2026-06-03

3

漏洞评估与扫描

Cybersecurity 2026-04-27

4

前置知识线性代数微积分概率统计

Neural Networks 2026-06-03

5

综合实验与调试方法

MCU Development 2026-04-27

ぬくぬくうちにゃ💤

第 2 章 基础数据结构与语言工具#

2.1 学习目标#

2.2 数组与动态数组#

2.3 链表#

2.4 栈#

2.5 队列与双端队列#

2.6 堆与优先队列#

2.7 哈希表#

2.8 常用容器复杂度#

2.9 选择数据结构的思路#

2.10 易错点#

2.11 练习#

ACM/OI 扩展：竞赛常用容器与手写结构#

1. vector 邻接表#

2. 链式前向星#

3. 手写队列#

4. policy based data structure#

5. 坐标压缩模板#

本章模板背诵清单#

STL 与手写结构补充#

multiset 的删除#

map / unordered_map 选择#

bitset 优化#

pair / tuple 排序#

数组初始化技巧#

高频模板训练卡#

卡 1：vector 邻接表#

卡 2：链式前向星#

卡 3：栈模拟递归#

卡 4：数组队列 BFS#

卡 5：priority_queue#

卡 6：set/multiset#

卡 7：unordered_map 防卡#

卡 8：bitset 优化#

卡 9：坐标压缩#

卡 10：pair 排序#

卡 11：tuple 状态#

卡 12：手写小根堆#

卡 13：双端队列#

卡 14：环形队列#

卡 15：内存池#

卡 16：结构体排序#

卡 17：全局数组初始化#

卡 18：PBDS 有序集合#

卡 19：自定义 hash#

卡 20：离散化映射#

卡 21：桶计数#

卡 22：压位存储#

本章赛前默写任务#

02_基础数据结构与语言工具：详细训练清单#

训练点 1：vector#

训练点 2：array#

训练点 3：deque#

训练点 4：stack#

训练点 5：queue#

训练点 6：priority_queue#

训练点 7：set#

训练点 8：multiset#

训练点 9：map#

训练点 10：unordered_map#

训练点 11：bitset#

训练点 12：PBDS#

训练点 13：链式前向星#

训练点 14：坐标压缩#

训练点 15：结构体排序#

训练点 16：自定义 hash#

训练点 17：内存池#

训练点 18：手写队列#

训练点 19：vector#

训练点 20：array#

训练点 21：deque#

目錄

第 2 章基础数据结构与语言工具#