来自算法基础课
单链表
const int N = 100005;
int head, e[N], ne[N], idx;
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
// 初始化
void init(){
head = -1;
idx = 0;
}
// 在链表头插入一个值为x的节点
void insert_to_head(int x){
e[idx] = x;
ne[idx] = head;
head = idx;
idx ++;
}
// 在第k个节点后面插入一个值为x的节点
void insert(int k, int x){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx ++;
}
// 删除第k个节点
void remove(int k){
ne[k] = ne[ne[k]];
}
双链表
const int N = 100005;
int e[N], l[N], r[N], idx;
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
// 初始化
void init(){
r[0] = 1, l[1] = 0; // 0号点为左端点， 1号点为右端点
idx = 2; // 从2号点开始分配
}
// 在第k个节点与第k+1个节点之间插入值为x的点
void insert(int k, int x){
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx ++;
}
// 删除第k个点
void remove(int k){
l[r[k]] = l[k];
r[l[k]] = r[k];
}
栈
const int N = 100005;
int stk[N], tt = 0;
// stk为栈，tt为栈顶
// 插入值为x的元素
void push(int x){
tt ++; // 开辟一个新的空间
stk[tt] = x; // 将x放入空间
}
// 弹出栈顶
void pop(){
if(tt >= 0) // 如果栈不空
tt --;
}
// 返回栈的大小
int size(){
return tt;
}
// 返回栈是否为空
bool empty(){
if(tt >= 1) // 栈不空
return false;
else
return true;
// 可以用"return tt < 1;"代替
}
// 求栈顶元素
int top(){
return stk[tt];
}
队列
const int N = 100005;
int q[N], hh = 0, tt = -1;
// q为队列，hh为队头，tt为队尾
// 在队尾插入值为x的元素
void push_back(int x){
tt ++; // 开辟出新的空间
q[tt] = x; // 将x放入空间
}
// 弹出队尾
void pop_front(){
if(hh <= tt) // 如果队列不空
hh ++;
}
// 返回队列的大小
int size(){
return tt - hh + 1;
}
// 返回队列的大小
bool empty(){
if(hh <= tt) // 如果队列不空
return false;
else
return true;
// 可以用"return hh > tt"代替
}
单调栈
常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ ){
while(tt && check(stk[tt], i)) // 如果栈非空并且是stk[tt]没有用就应该弹出
tt -- ;
stk[ ++ tt] = i; // 放入i
}
单调队列
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ ){
while (hh <= tt && check_out(q[hh])) // 判断队头是否滑出窗口
hh ++ ;
while (hh <= tt && check(q[tt], i)) // 如果队列非空并且是q[tt]没有用就应该弹出
tt -- ;
q[ ++ tt] = i; // 放入i
}
KMP
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度(s,p都从1开始)
// 求模式串的Next数组：
for(int i = 2, j = 0; i <= n; i ++){
while(j && p[i] != p[j + 1]) // 找到能和p[i]匹配的p[j + 1]
j = ne[j];
if(p[i] == p[j + 1]) // 如果匹配到了
j ++; // j向后走一位
ne[i] = j;
}
// 匹配
for(int i = 1, j = 0; i <= m; i ++){
while(j && s[i] != p[j + 1]) // 找到能和s[i]匹配的p[j + 1]
j = ne[j];
if(s[i] == p[j + 1]) // 如果匹配到了
j ++;
if(j == n){
// 匹配成功
}
}
Trie树
const int N = 100005;
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[i][j]存储树中i节点的子节点j
// cnt[i]存储以i节点结尾的单词数量
// 注意：str[i]在这里都是小写字母！！！
// 插入一个字符串
void insert(char str[]){
int p = 0; // p表示现在走到哪个点了
for(int i = 0; str[i]; i ++){
int u = str[i] - 'a'; // 算出str[i]对应的u
if(!son[p][u]) // 如果p没有子节点u
son[p][u] = ++ idx; // 就加上儿子节点u
p = son[p][u]; // p走到下一个位置
}
cnt[p] ++; // 以p结尾的单词数目+1
}
// 查询字符串出现的次数
int query(char str[]){
int p = 0; // p表示现在走到哪个点了
for(int i = 0; str[i]; i ++){
int u = str[i] - 'a'; // 算出str[i]对应的u
if(!son[p][u]) // 如果p没有子节点u
return 0; // 没有这个单词
p = son[p][u]; // p走到下一个位置
}
return cnt[p]; // 返回以p结尾的单词个数
}
并查集
(1)朴素并查集：
const int N = 100005;
int p[N];
// p[i]存储i的祖宗节点
// 返回x的祖宗节点，并将p[x]更新成x的祖宗节点
int find(int x){
if(p[x] != x)
p[x] = find(p[x]);
return p[x];
}
// 合并a和b所在的集合
p[find(a)] = find(b);
// 返回a与b是否在同一个集合里面
return find(a) == find(b)
// 初始化,假定元素从1~n编号
for(int i = 1; i <= n; i ++)
p[i] = i; // 初始时，每个元素的祖宗节点都是它本身
(2)维护size的并查集：
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
const int N = 100005;
int p[N];
// p[i]存储i的祖宗节点
// 返回x的祖宗节点，并将p[x]更新成x的祖宗节点
int find(int x){
if(p[x] != x)
p[x] = find(p[x]);
return p[x];
}
// 合并a和b所在的集合
if(find(a) == find(b))
return;
p[find(a)] = find(b);
Size[find(b)] += Size[find(a)];
// 返回a与b是否在同一个集合里面
return find(a) == find(b)
// 初始化,假定元素从1~n编号
for(int i = 1; i <= n; i ++){
p[i] = i; // 初始时，每个元素的祖宗节点都是它本身
Size[i] = 1; // 初始时，每个元素所在的集合都只有1个数
}
(3)维护到祖宗节点距离的并查集：
const int N = 500005;
int p[N], d[N];
//p[i]存储节点i的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点，并将p[x]更新成x的祖宗节点，d[x]更新成x到祖宗节点的距离
int find(int x){
if(p[x] != x){
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化，假定元素从1~n编号
for(int i = 1; i <= n; i ++){
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
堆
const int N = 100005;
int h[N], hp[N], ph[N], Size;
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
// 交换两个点，及其映射关系
void heap_swap(int a, int b){
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
// 向下调整
void down(int u){
int t = u;
if(u * 2 <= Size && h[u * 2] < h[t])
t = u * 2;
if(u * 2 + 1 <= Size && h[u * 2 + 1] < h[t])
t = u * 2 + 1;
if(t != u){
heap_swap(u, t);
down(t);
}
}
// 向上调整
void up(int u){
while(u / 2 && h[u] < h[u / 2]){
heap_swap(u, u / 2);
u = u / 2;
}
}
// O(n)建堆
for (int i = n / 2; i; i -- )
down(i);
一般哈希
(1) 拉链法
const int N = 100003; // 一般取大于maxN的最小质数
int h[N], e[N], ne[N], idx;
// 向哈希表中插入一个数
void insert(int x){
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查询某个数是否存在
bool find(int x){
int k = (x % N + N) % N;
for(int i = h[k]; i != -1; i = ne[i])
if(e[i] == x)
return true;
return false;
}
(2) 开放寻址法
const int N = 300007, null = 0x3f3f3f3f; // N一般取大于3 * maxN的最小质数，null表示这个位置没有用过
int h[N];
// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x){
int t = (x % N + N) % N;
while(h[t] != null && h[t] != x){
t ++;
if(t == N)
t = 0;
}
return t;
}
注意：hash时N一般要取质数，这样冲突的概率更低
字符串哈希
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL;
ULL h[N], p[N];
// h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for(int i = 1; i <= n; i ++ ){
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r){
return h[r] - h[l - 1] * p[r - l + 1];
}
