目录

1. 快读与高精度
2. 离散化
3. 区间合并
4. 单双链表
5. KMP
6. Trie
7. 并查集
8. 堆
9. Hash
10. 拓扑排序
11. 最短路
12. 最小生成树
13. 二分图

1. 快读与高精度

快读快输

原理:字符读入速度远快于整数读入

//快读:
inline int read(int &x){
    int f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
//快输：
inline void write(int n){
    if(n<0){putchar('-');n=-n;} 
    if(n>9)write(n/10);
    putchar(char(n%10+'0'));
}
//用法:
read(n）；
write(n);
//快读也有不适用的时候，例如读入中包含大量无用空格

//取消cin cout 缓冲，可加速cin cout速度 但是不能再用scnaf printf
ios::sync_with_stdio(false);

高精度

原理:数字换成字符按照平常加减乘除计算即可

//输入
cin>>A>>B;//存储 A B 此时 a[1]存个位 a[2]存十位... a[0],b[0]可以存大小(A.size)
for(int i = 0; i < A.size(); i++) a[A.size() - i] = A[i] - '0';
for(int i = 0; i < B.size(); i++) b[B.size() - i] = B[i] - '0';

//高精度加法  a >= 0  b >= 0  
void add(int a[], int b[]){
    len = max(A.size(),B.size());
    for(int i = 1; i <= len; i++){
        c[i] += a[i] + b[i];
        c[i+1] += c[i] / 10;    //模拟进位 
        c[i] %= 10;
    }
    if(c[len + 1]) len++; //加法最多进一位 
}
//高精度减法  a >= b 且 a >= 0 b >= 0
void sub(int a[], int b[]){
    len = max(A.size(),B.size());
    for(int i = 1; i <= len; i++){
        c[i] += a[i] - b[i];
        if(c[i] < 0) c[i] += 10, c[i+1] -= 1;   //借位
    }
    while(len > 1 && !c[len]) len--; //删除前导 0  
}
//高精度乘高级精度 A >= 0, b > 0
void mul(int a[],int b[]){ // 每次产生的值都到了第 i+j-1 位上
    for(int i = 1,x = 0; i <= lena;i++){
        for(int j = 1; j <= lenb; j++){
            c[i+j-1] = a[i] * b[j] + x + c[i+j-1];
            x = c[i+j-1] / 10;
            c[i+j-1] %= 10;
        }
    }
    len = lena + lenb;
    while(!c[len] && len > 1) len--;
}
//高精度除低精度 a / b = C ... r, a >= 0, b > 0
void div(int a[], int x){
    int r = 0, len = A.size();// r --> 余数
    for(int i = len; i > 0; i--){   //除法是从高位开始除
         r = r * 10 + a[i];
         c[i] = r / x;
         r %= x; 
     }
     while(len > 1 && !c[len]) len--;
}
for(int i = len; i > 0; i--) cout<<c[i];cout<<endl;//输出

2. 离散化

应用:数据范围大且间隔大，一般的数组难以维持

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x){ // 找到第一个大于等于x的位置
    int l = 0, r = alls.size() - 1;
    while (l < r){
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

3. 区间合并

原理:区间排序左端点有交集的区间可以合并

struct OI{int l, r;}num[N];

inline int cmp(OI a, OI b){return a.l < b.l;}  //按照左端点排序

sort(num+1, num+1+n,cmp);

void combine(){
    int st = num[1].l, ed = num[1].r;res++; //起始作为一个区间， 所以res起始为 1 个区间
    for(int i = 2; i <= n; i++){
        if(num[i].l <= ed)       // 可以合并成一个区间
            ed = max(ed,num[i].r);
        else
            st = num[i].l, ed = num[i].r, res++;// 不能合并成一个区间
    }
}

4. 单双链表

单链表

int e[N], ne[N], h[N], w[N], idx;
// h[k] --> 存储这个单链表的头结点
// e[i] --> 表示节点 i 的值
// ne[i]--> 表示节点 i 的next指针
// w[i] --> 表示这条边的权值
// idx  --> 存储当前用到的地址,相当于指针，当前用到的点

//初始化
idx = 0;
memset(h, -1, sizeof h);

// 添加一条边x -> y，边权为c
void add(int x, int y, int c) {
    e[idx] = y, w[idx] = c, ne[idx] = h[x], h[x] = idx++;
}

// 添加一条边x -> y
void add(int x, int y){
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

//将 x 插入到下标是 k 的点后面
void add(int k,int x){
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}

//删除下标是 k 的点后面一个点删掉
void remove(int k){
    ne[k] = ne[ne[k]];
}

//遍历
for (int i = h[u]; i != -1; i = ne[i])

双链表

int list[N], l[N], r[N], idx;

void init(){
    r[0] = 1, l[1] = 0, idx = 2;   //初始化头结点(右边指向第一个节点)和第一个节点(左边指向头结点)
}

// x 插到 k 后面
void insert(int k, int x){
    list[idx] = x; l[idx] = k;
    r[idx] = r[k];               //右边连接到下一个节点的左边，左边连接到上一个节点的右边
    l[r[k]] = idx;               //将原来两个相连接打的节点打断，连到新节点上
    r[k] = idx++;                //右边的左指针连接到新节点的右指针上，左边同理
}

//删除第 x 个节点
void remove(int x){
    r[l[x]] = r[x], l[r[x]] = l[x];
}

5. KMP

应用:匹配两个字符串相同的部分

char p[N], s[M];
int n, m, ne[M];
// p --> 模板串  s --> 模式串 ，即 p 是 s 子串

    // next 匹配过程
    for(int i = 2, j = 0; i <= n; i++){
        while(j && p[i] != p[j+1]) j = ne[j];
        if(p[i] == p[j+1]) j ++;
        ne[i] = j;
    }

    //KMP匹配过程
    for(int i = 1, j = 0; i <= m; i++){
        while(j && s[i] != p[j+1]) j = ne[j];
        if(s[i] == p[j+1]) j++;
        if(j == n){
            printf("%d ", i - n);
            j = ne[j];
        }
    }

6. Trie字典树

应用:存储的数字(字符)

// trie --> 建立字典树存储字符串 cnt[i] --> 已 i 结尾的字符串总数 idx --> 当前的位置
int trie[N][26], cnt[N], idx;

//插入操作
void insert(char str[]){
    int p = 0;
    for(int i = 0; str[i]; i++){
        int u = str[i] - 'a';
        if(!trie[p][u]) trie[p][u] = ++idx; //没有这个单词,那么建立新节点
        p = trie[p][u];                     // 此时 tire[p][u] 一定建立了
    }
    cnt[p]++ ;                             //已 p 结尾的单词数目加一
}

// 查询字符串出现的次数
int query(char *str){
    int p = 0;
    for (int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';
        if (!tire[p][u]) return 0;
        p = tire[p][u];
    }
    return cnt[p];
}

7. 并查集

应用:反复查找一个元素在哪个集合中

//并查集:在一些有N个元素的集合应用问题中
//我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并

int f[N], m, n;
//查询是否属于同一个集合
int find(int x){
    if(x == f[x]) return x;
    return f[x] = find(f[x]);
}
//连接两个集合
void insert(int x,int y){
    int f1 = find(x), f2 = find(y);//查找两个数所在的集合
    if(f1 != f2) f[f1] = f2;
}

//返回 x 的祖宗节点(路径压缩版本)
int find(int x){
   return f[x] != x ? f[x] = find(f[x]) : f[x];
}

8. 堆

手写小根堆原理:完全二叉树,满足父节点小于等于子节点,大根堆相反

数组存储堆：
 1.父亲节点为 x, 则左右儿子节点分别为 2 * x, 2 * x + 1 
 2.插入一个数: head[++size] = x ; up(size);
 3.求集合中最小值: head[1];
 4.删除最小值: head[1] = head[size]; size--; down(1);
 5.删除任意一个元素: head[k] = head[size]; size--;down(k);up(k);
 6.修改任意一个元素: head[k] = x; down(k）；up（k）；

实现up和down操作

int h[N], sizee ;

// 插入 从上到下 
void down(int t){
    int u = t;
    if((t<<1) <= sizee && h[t<<1] < h[u]) u = (t<<1);          //左儿子存在并且小于根节点 
    if((t<<1)|1 <= sizee && h[(t<<1)|1] < h[u]) u = (t<<1)|1 ;
    //右儿子存在并且小于根节点 (t << 1)| 1 == t * 2 + 1
    if(t != u){ 
    //如果存在比根节点小的数,交换,因为交换后的数字可能还是比自己的子节点小,就要继续交换 
        swap(h[t],h[u]);
        down(u);
    }
}

//从下到上  //父节点 的值大于 子节点 
void up(int t){
    if(h[t >> 1] > h[t])
      swap(h[t >> 1], h[t]), up(t >> 1);
}

9. Hash表

拉链法

//空间(数组长度)最好是质数，离2的整数次幂尽可能的远（减少冲突）
const int N = 1e6 + 3;

int e[N], ne[N], h[N],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 ~ 3 倍
const int N = 2e6 + 3, null = 0x3f3f3f3f;

int h[N], n;

int find(int x){
    int k = (x % N + N) % N ;
    //占用了 并且 占用的数不是要添加的数，看下一个地址
    while(h[k] != null && h[k] != x){
         k++; if(k == N) k = 0;
    }
    return k;
}

字符串hash

原理:字符映射成 p 进制的数

const int N = 100010, P = 131;
typedef unsigned long long ull;

int n, m;
char str[N];
ull h[N], p[N];

//判断区间内的字符串是不是 相同
ull get(int l, int r){
    return h[r] - h[l-1] * p[r - l + 1];
}
int main(){
    cin>>n>>m>>str; p[0] = 1;
    for(int i = 1; i <= n; i++){
        p[i] = p[i-1] * P;
        h[i] = h[i-1] * P + str[i];
    }
    while(m--){
        int l1,l2,r1,r2;cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1) == get(l2, r2))puts("Yes"); //区间[l1,r1]和[l2,r2]相等
        else  puts("No");
    }
    return 0;
}

10. 拓扑排序

//判断是否有拓扑排序
bool topsort(){
    int hh = 0, tt = -1;
    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if ( !d[i] )
            q[ ++ tt] = i;

    while (hh <= tt){
        int t = q[hh++];

        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (--d[j] == 0)
                q[ ++ tt] = j;
        }
    }
    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

11. 最短路

朴素Dijkstra

原理:计算某个节点到其他节点的最短路径，不断转移最小路径

//Dijkstra算法，用于单源最短路边都为正数的情况，适用于稠密图 O(n^2)  
int n, m;
int dis[N], g[N][N]； //dis -> 最短距离 g[i][j] -> 图 i 到 j 距离
bool st[N];

int Dijkstra(){
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;

    for(int i = 0; i < n; i++){
        int t = - 1; 
        for(int j = 1; j <= n; j++)
           if(!st[j] && (t == -1 || dis[t] > dis[j]))
              t = j;
        st[t] = true;

        for(int j = 1; j <= n; j++)
           dis[j]= min(dis[j], dis[t] + g[t][j]);
    }
    if(dis[n] == 0x3f3f3f3f) return -1;
    return dis[n];
}

Dijkstra的堆优化

//适合稀疏图 O(mlogn)
typedef pair<int, int> PII;
int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;// 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size()){
        auto t = heap.top();heap.pop();

        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if (dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

Bellman-Ford

//Bellman-Ford算法，用于单源最短路存在负权边的情况 O(nm)
struct Node{
    int a, b, w;
}edge[M];

int bellman_ford(){
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;

    for(int i = 0; i < k; i++){
        memcpy(backup, dis, sizeof(dis));

        for(int j = 0; j < m; j++){
            int a = edge[j].a, b = edge[j].b, w = edge[j].w;
            dis[b] = min(dis[b], backup[a] + w); //备份，防止原来的数据被覆盖
        }
    }
    if(dis[n] > 0x3f3f3f3f / 2) return -1;    //要将无穷除以2（可能存在负边，但不是最短路）
    return dis[n];
}

SPFA 算法（队列优化的Bellman-Ford算法)

//可以处理存在负边权的最短路问题。
//时间复杂度 平均情况下 O(m)，最坏情况下 O(nm), n 表示点数，m 表示边数

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;  // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;q.push(1);
    st[1] = true;

    while (q.size()){
        auto t = q.front();
        q.pop(); st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                if (!st[j]){     // 如果队列中已存在j，则不需要将j重复插入
                    q.push(j);st[j] = true;
                }
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

Floyd

//多源最短路 O(n^3)
//需要注意循环顺序不能变：第一层枚举中间点，第二层和第三层枚举起点和终点。
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i != j)  d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd(){
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

12. 最小生成树

朴素 Prim

原理: 每次确定一个点

//时间复杂度是 O(n^2+m), n 表示点数，m 表示边数

int n;      // n表示点数
int g[N][N], dist[N];   // 邻接矩阵,存储其他点到当前最小生成树的距离
bool vis[N];     // 存储每个点是否已经在生成树中

// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim(){
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!vis[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];     //不是起点

        vis[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

Kruskal 算法

原理: 每次确定一条边

//时间复杂度是 O(mlogm), n 表示点数，m 表示边数

int n, m;   // n是点数，m是边数
int p[N];   // 并查集

struct Edge{
    int x, y, w;
    bool operator< (const Edge &W)const{return w < W.w;}
}edges[M];

int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal(){
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ){
        int x = edges[i].x, y = edges[i].y, w = edges[i].w;

        x = find(x), y = find(y);
        if (x != y){     // 如果两个连通块不连通，则将这两个连通块合并
            p[x] = y;
            res += w, cnt ++ ; //边数++
        }
    }

    if (cnt < n - 1) return INF; // 如果连接的边数小于 n - 1 说明图不连通
    return res;
}

13. 二分图

二分图: 所以的点都可以归为两个集合
二分图的性质: 一定不含奇数环

染色法判别二分图

//时间复杂度是 O(n+m)O(n+m), nn 表示点数，mm 表示边数

int n;      // n表示点数
int h[N], e[M], ne[M], idx; 
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c){
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if (color[j] == -1)
            if (!dfs(j, !c))
              return false;
        else if (color[j] == c) return false;
    }
    return true;
}

bool check(){
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0)){
                flag = false;break;
            }
    return flag;
}

匈牙利算法

//时间复杂度是 O(nm), n 表示点数，m 表示边数
int n1, n2;  // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; 
// 邻接表存储所有边，只会用到从第一个集合指向第二个集合的边,只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x){
    for (int i = h[x]; i != -1; i = ne[i]){
        int j = e[i];
        if (!st[j]){  //没有遍历1
            st[j] = true;
            if (!match[j] || find(match[j])){ 
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ ){
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}