学习笔记
链表
单链表
|
|
双链表
|
|
堆栈
模拟栈
|
|
单调栈
|
|
队列
模拟队列
|
|
单调队列
|
|
KMP
|
|
Trie 树
AcWing 835. Trie字符串统计 AcWing 143. 最大异或对
|
|
并查集
朴素 dsu
|
|
维护 size 的 dsu
|
|
维护到祖先距离的 dsu
AcWing 240. 食物链 AcWing 238. 银河英雄传说
|
|
堆
朴素版堆(小根堆为例)
|
|
双向映射的堆
|
|
哈希表
哈希散列
|
|
字符串哈希
基本思想
- $ axc...kzz $ 看成是一个 $\mathrm{base}$ 进制的数字,将其转化成十进制再 $ \mathrm{mod} \ \mathrm{p} $ 得到哈希值。
- 映射 $ a→1$,$ b→2$,....$ z→26$(若 $ a $ 映射到 $0$ 则无法区分 $ b $ 与 $ ab $ )
- 经验值:质数 $ base $ 取 $ 131 $ 或 $ 13331 $, $ \mathrm{p} $ 取 $ 2^{64} $。
对于
unsigned
整型溢出,C的规范是有定义的——溢出后的数会以$ 2^{8*\mathrm{sizeof}(\mathrm{type})} $作模运算。因此定义成
unsigned long long
,溢出即对 $2^{64}$ 取模。
- $ O(1) $ 可得任意子串 $ [l, r] $ 的哈希值:
$\mathrm{hash}(l, r) = h[r] - h[l-1]*\mathrm{base}^{r-l+1} $
AcWing 841. 字符串哈希 AcWing 139. 回文子串的最大长度
|
|