共计 4386 个字符，预计需要花费 11 分钟才能阅读完成。
内容目录
链表
单链表
// e[]存储的是节点的值
// ne[]存储节点的next指针
// idx表示当前用到哪个节点
// head存储链表头
int e[N],ne[N],head,idx,m;
// 链表初始化
void init(){
head = -1;
idx = 0;
}
// 向头节点插入元素x
void add_to_head(int x){
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
// 删除第k个节点后的节点
void removeofK(int k){
ne[k] = ne[ne[k]];
}
// 在第k个节点之后添加元素x
void add(int k,int x){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx ++;
}
// 删除头节点
void removeHead(){
head = ne[head];
}
// 遍历链表
void display(){
for(int i=head;i!=-1;i = ne[i]){
printf("%d ",e[i]);
}
printf("\n");
}双链表
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N],l[N],r[N],idx;
// 初始化
void init(){
//0是左端点，1是右端点
r[0] = 1,l[1] = 0;
idx = 2;
}
// 在下标是k的点的右边插入元素k
void add_to_right(int k,int x){
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx++;
}
// 删除第k个点
void remove(int k){
l[r[k]] = l[k];
r[l[k]] = r[k];
}
// 遍历
void display(){
for(int i=r[0];i!=1;i=r[i]){
printf("%d ",e[i]);
}
printf("\n");
}栈
模拟栈
// tt栈顶指针
int a[N],tt;
// 初始化
void init(){
tt = 0;
}
// 入栈
void push(int x){
a[++tt] = x;
}
// 出栈
void pop(){
tt--;
}
// 栈顶元素
int top(){
return a[tt];
}
// 判空
bool isEmpty(){
if(tt > 0) return false;
else return true;
}单调栈
常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}队列
模拟队列
// hh：队头 tt：队尾
int a[N],hh,tt;
// 队列初始化
void init(){
hh = 0;
tt = -1;
}
// 入队
void push(int x){
a[++tt] = x;
}
// 出队
void pop(){
hh++;
}
// 取队头元素
int front(){
return a[hh];
}
// 判空
bool isEmpty(){
if(hh <= tt) return false;
return true;
}单调队列
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)) tt -- ;
q[ ++ tt] = i;
}KMP算法
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}trie树(字典树)
int son[N][26],cnt[N],idx;
char str[N];
// 插入字符串
void insert(char str[]){
int p = 0;
for(int i=0;str[i];i++){
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++;
}
// 查询字符串的个数
int query(char str[]){
int p = 0;
for(int i=0;str[i];i++){
int u = str[i] - 'a';
if(!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}并查集
// p[x]：x的祖先
int p[N];
int n,m;
// find
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
// unionn
void unionn(int x, int y){
p[find(x)] = find(y);
}堆
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;
// 交换两个点，及其映射关系
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 (u != t)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}
// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
哈希表
int h[N],e[N],ne[N],idx;
// insert 插入元素
void insert(int x){
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++;
}
// find 查找元素是否在集合中
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;
}字符串哈希
核心思想：将字符串看成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];
}STL简介
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
正文完
