快速排序

1. 找到分界点x = q[(l + r) / 2]
2. 左边所有数Left <= x，右边所有数Right >= x
3. 递归排序Left，递归排序Right

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

快速选择排序

int quick_select_sort(int l, int r, int k)
{
    if (l == r) return q[l];

    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    while (i < j)
    {
        while (q[ ++ i ] < x);
        while (q[ -- j ] > x);
        if (i < j) swap(q[i], q[j]);
    }
    int sl = j - l + 1;
    if (sl >= k) return quick_select_sort(l, j, k);
    return quick_select_sort(j + 1, r, k - sl);
}

归并排序

1. 将区间一分为二$[L, R] => [L, mid], [mid + 1, R]$
2. 递归排序$[L, mid]$和$[mid + 1, R]$
3. 归并，将左右两个有序序列合并成一个有序序列

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    }
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; 
}

正数二分

//  第一种形式
int l = 0, r = n - 1;
while (l < r)
{
    int mid = l + r >> 1;
    if (check()) l = mid + 1;
    else r = mid;
}

// 第二种形式
int l = 0, r = n - 1;
while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (check()) r = mid - 1;
    else l = mid;
}

浮点数二分

// 浮点数二分相对于整数二分，不需要处理边界问题
// 以一个数开方为例
double l = 0, r = x;
while (r - l > 1e-8)  // 或者直接循环100次：for (int i = 0; i < 100; i ++ )
{
    double mid = (l + r) / 2;
    if (mid * mid <= x) l = mid;
    else r = mid
}

高精度加法

// 将数字的个位数存在数组下标0的位置
#include <bits/stdc++.h>

using namespace std;

vector<int> add(vector<int> & A, vector<int> & B)
{
    vector<int> C;
    int t = 0;  // 进位
    for (int i = 0; i < A.size() || i < B.size(); i ++ )
    {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(1);
    return C;
}

int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
    auto C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    return 0;
}

高精度减法

#include <bits/stdc++.h>

using namespace std;

// 判断是否有 A >= B
bool cmp(vector<int> & A, vector<int> & B)
{
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i -- )
        if (A[i] != B[i])
            return A[i] > B[i];
    return true;
}

// C = A - B
vector<int> sub(vector<int> & A, vector<int> & B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )  // t 是借位
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);  // 解决 t >= 0 和 t < 0 两种情况
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();  // 删除前导零
    return C;
}

int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');

    if (cmp(A, B))
    {
        auto C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    }
    else
    {
        auto C = sub(B, A);
        printf("-");
        for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    }
    return 0;
}

高精度乘法

// C = A * b
vector<int> mul(vector<int> & A, int b)
{
    vector<int> C;
    int t = 0;  // t 是进位
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    if (t != 0) C.push_back(t);
    while (C.size() > 1 && C.back() == 0) C.pop_back();  // 去掉前导零
    return C;
}

高精度除法

vector<int> div(vector<int> & A, int b, int & r)  // 利用 引用 返回余数
{
    vector<int> C;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();  // 去掉前导零
    return C;
}

前缀和

原数组：{$a_1, a_2, a_3, …, a_n$} \
前缀和：$S_i = a_1 + a_2 + … + a_i $，$S_0 = 0$
如何求$S_i$ : for (int i = 1; i <= n; i ++ ) S[i] = S[i - 1] + a[i]
作用：$[l, r]$区间的和就是$a_l + a_{l + 1} + … + a_r$，时间复杂度为$O(n)$，而通过前缀和可以这样计算：$S_r - S_{l - 1}$，时间复杂度为$O(1)$
* 注意$S_0 = 0$这样可以有效处理边界问题，同时将$[1, x]$这种区间的前缀和统一转化为$S_x - S_0$这样类似$S_r - S_{l - 1}$的形式

    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) S[i] = S[i - 1] + a[i];
    while (m -- )
    {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", S[r] - S[l - 1]);
    }

二维前缀和

    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    while (q -- )
    {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
    }

差分

原数组：{$a_1, a_2, a_3, …, a_n$} \
差分数组：{$b_1, b_2, b_3, …, b_n$} \
数组$A$是数组$B$的前缀和，则数组$B$是数组$A$的差分数组，即$a_i = b_1 + b_2 + b_3 + … + b_i$，那么构造数组$B$的方式就是{$b_1 = a_1, b_2 = a_2 - a_1, b_3 = a_3 - a_2, …, b_n = a_n - a_{n - 1}$}，但是构造方式不重要。 \
应用： \
若对数组$A$的区间$[l, r]$加上$c$，对数组$A$操作时间复杂度为$O(n)$，对差分数组$B$操作时间复杂度只需要$O(1)$。即令$b_l + c$，则区间$[a_l, a_n]$加上$c$，此时令$b_{r + 1} - c$，则区间$[a_{r + 1}, a_n]$减去$c$，从而实现只有区间$[a_l, a_r]$加上$c$。 \
我们可以假设数组$A$全为$0$，则数组$B$全为零即为数组$A$的差分数组，在读入数组$A$的值时，把它看作是插入操作，即对区间$[i, i]$加上$a_i$，则数组$B$就同时构造出来了。也将数组$B$的构造操作和插入操作进行了统一。数组的下标从$1$开始。

#include <iostream>

using namespace std;

const int N = 100010;
int a[N], b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ )
        insert(i, i, a[i]);
    while (m -- )
    {
        int l, r, c;
        scanf("%d %d %d", &l, &r, &c);
        insert(l, r, c);
    }
    for (int i = 1; i <= n; i ++ ) a[i] = a[i - 1] + b[i];
    for (int i = 1; i <= n; i ++ ) printf("%d ", a[i]);

    return 0;
}

二维差分

#include <iostream>

using namespace std;

const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);
    while (q -- )
    {
        int x1, y1, x2, y2, c;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            a[i][j] = a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1] + b[i][j];
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
            printf("%d ", a[i][j]);
        puts("");
    }

    return 0;
}

双指针算法

• 技巧：先把暴力算法写出来，然后根据单调性优化算法

核心思想：将朴素暴力双重循环时间复杂度为$O(N^2)$优化到$O(N)$。

for (int i = 0; i < n; i ++ )
    for (int j = 0; j < n; j ++ )
    {
        // O(n^2)  
    }

将上面的朴素算法优化到$O(N)$。 \
模板：

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 每道题目的具体逻辑
}

常见问题分类: \
（1）对于一个序列，用两个指针维护一段区间； \
（2）对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

位运算

• 求数字$n$的第$k$位数字：n >> k & 1
• 返回数字$n$的最后一位1及后面的0组成的二进制：lowbit(n) = n & -n

离散化

将数组a[]: {1, 3, 100, 2000, 500000}映射到{0, 1, 2, 3, 4}
1. 数组a[]中可能有重复元素 => 去重
2. 如何算出 x 离散化后的值 => 二分

这里特指整数的离散化

vector<int> alls;  // 存储所有待离散化的值
sort(alls.begin(), alls.end());  // 将所有值排序
alls.erase(unique(alls.begin(), all.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, 3, ..., n（不加1就映射到0,1,2,...,n - 1）
}

区间合并

// 将所有存在交集的区间合并
void merge(vector<PII> & segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});  // 判断不是初始化的区间
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});  // 将最后一个区间加入

    segs = res;
}

单链表

• 用数组实现单链表，主要优势就是快
• 最多用法是实现邻接表，邻接表其实是多个链表，主要用来存储图和树。

// head 
cosnt int N = 100010;
// head 表示头节点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// ids 表示当前已经用到了哪个点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 将x插到头节点
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx ++ ;
}

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

// 将下标是k的点后面的点删掉，就是将下标是k的点的指针直接指到后面的点的后面
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

双链表

• 一个节点有左右两个指针

const int N = 100010;
int head, tail, e[N], ne[N], idx;

// 初始化
void init()
{
    head = 0, tail = 1;
    r[head] = 1, l[tail] = 0;
    idx = 2;  // 因为头指针和尾指针占据了两个位置
}

// 在下标为k的节点的右侧，插入x
void add(int k, int x)
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx ++ ;
}
// 在下标为k的节点的左侧，插入x，可以重新实现，也可以通过调用add(l[k])来实现
// 即在下标为k的节点的左侧节点的右侧，插入x

// 删除下标为k的节点
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

栈

• 先进后出
• 只对数组的一端进行操作，下标从0或者1开始都可以，看个人习惯

const int N = 100010;
int stk[N], tt;  // stk 表示栈，tt 表示栈顶

// 插入
stk[ ++ tt] = x;

// 弹出
tt -- ;

// 判断栈是否为空
if (tt > 0) not empty
else empty

// 栈顶
stk[tt];

队列

• 先进先出，在队列尾部插入元素，在队列头部弹出元素

// hh 表示队头，tt 表示队尾
int q[N], hh, tt = -1;

// 向队尾插入一个元素
q[ ++ tt] = x;

// 从对头弹出一个元素
hh ++ ;

// 判断队列是否为空
if (hh <= tt) not empty
else empty

// 取出队头元素
q[hh];

单调栈

• 常见模型：找出每个数左边离它最近的比它大/小的数

int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(q[tt], i)) tt -- ;
    stk[ ++ tt] = 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)) tt -- ;
    q[ ++ tt] = i;
}

KMP

• 字符串匹配，要点在于next[j]数组的建立和使用
• $ne[j] < j$

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;
int n, m;
char p[N], s[M];
int ne[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;  // 下标从1开始

    // 建立ne[]数组
    for (int i = 2, j = 0; i <= n; i ++ )  // i从下标2开始，是因为ne[1] = 0
    {
        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 <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            // 匹配成功

        }
    }

    return 0;
}

Trie树

• 又称为字典树
• 是一种用来高效地存储和查询字符串集合的数据结构

#include <iostream>

using namespace std;

const int N = 100010;
int son[N][26], cnt[N], idx;  // son[x][26]表示节点x的子节点；
                              // cnt[x]表示以节点x为结尾的字符串的数量
                              // 下标是0的节点既是根节点，又是空节点
char str[N];

void insert(char str[])
{
    int p = 0;  // 从根节点开始插入
    for (int i = 0; str[i]; i ++)  // c++中字符串数组结尾为'\0'，即空
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;  // 如果节点不存在，则将该节点创建出来
        p = son[p][u];  // 然后走到该节点
    }
    cnt[p] ++ ;  // 以节点p为结尾的字符串数量加1
}

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];
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
        scanf("%s%s", op, str);
        if (op[0] == 'I')
        {
            insert(str);
        }
        else
            printf("%d\n", query(str));
    }

    return 0;
}

并查集

使用场景：
1. 将两个集合合并
2. 询问两个元素是否在一个集合当中

基本原理：每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点。

问题1：如何判断树根：if (p[x] != x)

问题2：如何求x的集合编号：while(p[x] != x) x = p[x];

问题3：如何合并两个集合：p[x]是x的集合编号，p[y]是y的集合编号。p[x] = y;

优化：对问题2的查询操作，可以使用路径压缩进行优化，即查找到祖宗节点后，直接将x指向它的祖宗节点

#include <iostream>

using namespace std;

const int N = 100010;
int p[N];

int find(int x)  // 返回x的祖宗节点 + 路径压缩
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    char op[2];
    int a, b;
    while (m -- )
    {
        scanf("%s%d%d", op, &a, &b);  // 用字符串读入可以解决掉一些奇怪的空格、换行等问题
        if (op[0] == 'M') p[find(a)] = find(b);  // 合并，让b的祖宗节点成为a的祖宗节点的父节点
        else
        {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

堆

如何手写一个堆？（假设是小根堆）
1. 插入一个数 heap[ ++ size] = x; up(size);
2. 求集合当中的最小值 heap[1];
3. 删除最小值 heap[1] = heap[size]; size -- ; down(1);
4. 删除任意一个元素（手写堆特有） heap[k] = heap[size]; size -- ; down(k); up(k);
5. 修改任意一个元素（手写堆特有） heap[k] = x; down(k); up(k);

堆是一棵二叉树，是一棵完全二叉树。 \
小根堆：根节点存储的是集合的最小值，父节点的值要小于等于左右子儿子的值 \
大根堆：根节点存储的是集合的最大值，父节点的值要大于等于左右儿子的值

存储：用一维数组存储，下标从 1 开始，x的左儿子：2x；x的右儿子：2x + 1。
* 堆排序

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int h[N], siz;
int n, m;

void down(int u)  // u 表示下标
{
    int t = u;  // 用 t 表示父节点、左儿子和右儿子中的最小值的下标
    if (u * 2 <= siz && h[u * 2] < h[t]) t = u * 2;  // 判断左儿子是否存在并比较大小
    if (u * 2 + 1 <= siz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;  // 判断右儿子是否存在并比较大小
    if (u != t)  // 如果下标 u 不是父节点、左儿子和右儿子中的最小值，则交换，并递归做down操作
    {
        swap(h[u], h[t]);
        down(t);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);  // 下标从1开始
    siz = n;
    for (int i = n / 2; i; i -- ) down(i);  // 建堆的方式可以是一个一个插入，也可以对每一层做down操作
                                            // 一个一个插入的方式时间复杂度为O(nlogn)
                                            // 对每一层做down操作的方式时间复杂度为O(n)
    while (m -- )
    {
        printf("%d ", h[1]);
        h[1] = h[siz];
        siz -- ;
        down(1);
    }

    return 0;
}

• 模拟堆
  > 因为需要对第 k 个插入堆的数进行操作，所以需要建立输入顺序和堆中下标的映射关系 \
  > x 表示堆中的下标 \
  > h[x] 表示堆中位置 x 的元素 \
  > ph[k] = x 表示第 k 个插入的元素在堆中存放的下标为 x \
  > 此时，如果要交换堆中下标为 a 和 b 的两个元素，那么为了维护ph数组，需要知道堆中下标为 a 和 b 的两个元素是第几个被插入的，于是便引入了数组hp\
  > hp[x] = k表示堆中下标为 x 的位置存放的是第 k 个插入的元素

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;
int h[N], siz, ph[N], hp[N];  // ph中存储第k个插入的数在堆数组中的下标 idx，
                              // hp中存储堆数组中下标为idx的数对应的k

void heap_swap(int a, int b)  // a, b 为堆中的下标，三个交换次序可以变换，但是这样写比较美观
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)  // u 为堆中的下标
{
    int t = u;
    if (u * 2 <= siz && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= siz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)  // u 为堆中的下标
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u /= 2;
    }
}

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n -- )
    {
        char op[10];
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            int x;
            scanf("%d", &x);
            siz ++ ;
            m ++ ;
            ph[m] = siz, hp[siz] = m;
            h[siz] = x;
            up(siz);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, siz);
            siz -- ;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            int k;
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, siz);
            siz -- ;
            down(k), up(k);
        }
        else if (!strcmp(op, "C"))
        {
            int k, x;
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}

哈希表

哈希表的作用是将一些大范围的数据通过哈希函数映射到小范围，和离散化的区别，在于离散化是保序的。当发生冲突时，解决办法： 开放寻址法 和 拉链法
* 开放寻址法

只需要使用一维数组，需要将数组的范围开到数据范围的2~3倍，这样冲突会比较少

#include <iostream>
#include <cstring>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;
int h[N];

int find(int x)  // 如果x存在，则返回x的位置；如果x不存在，则返回x应该存储的位置
{
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x)
    {
        k ++ ;
        if (k == N) k = 0;  // 找到末尾，从头开始找
    }
    return k;
}

int main()
{
    int n;
    scanf("%d", &n);
    memset(h, 0x3f, sizeof h);
    char op[2];
    int x;
    while (n -- )
    {
        scanf("%s%d", op, &x);
        int k = find(x);
        if (*op == 'I') h[k] = x;  // 插入
        else
        {
            if (h[k] != null) puts("Yes");  // 查找
            else puts("No");
        }
    }

    return 0;
}

• 拉链法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100003;
int h[N], e[N], ne[N], idx;

void insert(int x)
{
    int k = (x % N + N) % N;  // 如果x为负数，取模的余数也为负数，这样做可以将余数变为正数
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx;
    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;
}

int main()
{
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    char op[2];
    int x;
    while (n -- )
    {
        scanf("%s%d", op, &x);
        if (*op == 'I') insert(x);
        else
        {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

• 字符串哈希方式
  • 可以用于快速判断两个字符串是否相等，将$O(N)$时间转换为$O(1)$时间
  • 字符串前缀哈希法：将一个字符串看成是一个P进制的数，比如$(ABCD)P=(AP^3+BP^2+CP^1+DP^0)$，但这样可能得到的数比较大，会溢出，所以需要$modQ$，这样就可以将数字映射到$0$-$Q-1$之间。注意，不能将某个字符映射为0，比如A为0，则AA、AAA都为0；不同于数字哈希，对于字符串哈希，假定不存在冲突，取P=131或13331，Q=2^64，基本不会出现冲突。由于Q=2^64，所以数据类型可以直接用unsigned long long，这样溢出时就相当于$modQ$。
  • 计算$[L, R]$区间的字串的哈希的方法就是$h[R] - h[L - 1]*P^{R - L + 1}$

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;
char str[N];
ULL h[N], p[N];  // h数组存放字符串前缀哈希值，p数组存放P的多少次方

ULL get(int l, int r)
{
   return h[r] - h[l - 1] * p[r - l + 1]; 
}

int main()
{
    int n, m;
    scanf("%d%d%s", &n, &m, str + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = p[i - 1] * P;  // 预处理P的多少次方
        h[i] = h[i - 1] * P + str[i];  // 字符串前缀哈希值，str[i] 是多少都无所谓，只要不是零
    }
    while (m -- )
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}

STL容器

/*
vector，边长数组，倍增思想
    size() 返回元素个数
    empty() 返回是否为空
    clear() 清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, string>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
    p = make_pair(10, "yxc");/p = {20, "abc"};
    pair<int, pair<int, int>> p;  // 可以用来存储三个不同的东西

string，字符串，substr()，c_str()：返回字符串对应的字符数组的头指针
    size()/length()  返回字符串长度
    empty()
    clear()

queue, 队列，push(), front(), pop()
    size()
    empty()
    push() 向队尾插入一个元素
    front() 返回队头元素
    back() 返回队尾元素
    pop() 弹出队头元素
    queue, priority_queue, stack 没有clear()函数，但是可以这么清空一个queue：q = queue<int>();

priority_queue，优先队列，默认是大根堆，push(), top(), pop()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    小根堆：1.插入负数（黑科技）; 2.priority_queue<int, vector<int>, greater<int>> heap;

stack，栈，push(), top(), pop()
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque，双端队列，加强版vector
    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()
        []  时间复杂度是 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位取反

*/

深度优先搜索 和 广度优先搜索

• 深度优先搜索 DFS
• 广度优先搜索 BFS

	数据结构	空间	优势
DFS	stack	$O(h)$	不具最短性
BFS	queue	$O(2^h)$	“最短路”

• DFS 中包含回溯、剪枝，比较难以理解，可以从搜索树的角度考虑，会简单

• DFS俗称“暴搜”，考虑时最重要的是“顺序”，回溯时要记得恢复现场

• BFS也称“宽搜”，对于权重都为1的图，先搜到的点符合“最短路”

• 宽搜框架

// queue <- 初始状态
// while queue不空
// {
//      t <- 队头
//      拓展 t  
// }

• 宽搜中从一个点向上下左右遍历的技巧

// 定义两个数组，将四行判断代码转换到一个循环中，起到少写代码的作用
// 按照上、右、下、左的顺序
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for (int i = 0; i < 4; i ++ )
{
    // 新点的坐标
    int x = t.first + dx[i], y = t.second + dy[i];
    // 判断是否可以走到新点，以及是否第一次走到新点
    if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
    {
        d[x][y] = d[t.first][t.second] + 1; // 更新距离
        q[ ++ tt] = {x, y}; // 扩展 t
    }
}

树和图的遍历

• 树是一种特殊的图，是无环、连通图。
• 图分为有向图和无向图，无向图是特殊的有向图，所以考虑有向图就可以了
• 有向图的存储有两种方式：邻接矩阵和邻接表。邻接矩阵就是开一个二维数组g[a][b]存储a到b的信息，但是空间复杂度是$O(n^2)$的，适合存储稠密图。邻接表是开了$n$个链表，每个链表存储每个节点可以到达的点，适合存储稀疏图，是最常用的一种图存储方式。

最短路

• 单源最短路：问某一个点到终点的最短距离
• 多源汇最短路：源点和汇点不定，询问任意两个点之间的最短距离

场景	算法	时间复杂度
单源最短路 & 所有边权都是正数	朴素Dijkstra算法	$O(n^2)$，适合稠密图（边多，$m$和$n^2$一个级别）
单源最短路 & 所有边权都是正数	堆优化版的Dijkstra算法	$O(mlogn)$，适合稀疏图（边少，$m$和$n$一个级别） n为节点的数量，m为边的数量
单源最短路 & 存在负权边	Bellman-Ford	$O(nm)$ 不超过k条边的最短路只能选用此方法
单源最短路 & 存在负权边	SPFA	一般$O(m)$，最坏$O(nm)$
多源汇最短路	Floyd算法	$O(n^3)$

---

• 朴素Dijkstra算法

s: 当前已确定最短距离的点的集合
1. dist[1] = 0, dist[i] = +∞
2. for i : 1~n
        t <- 不在s中的，距离最近的点
        s <- t
        用t更新其他点的距离

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;
int n, m;
int g[N][N];
int dist[N];  // 存储每个点现在的最短距离
bool st[N];  // 标记节点是否已经确定最短距离

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;  // 起点到自身的距离为0
    // st[1] = true;  错误，如果加入这句话，节点1就不会进行松弛操作，结果出错
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )  // 寻找没有加入集合s的最短距离的点
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true;  // 标记节点加入集合s
        for (int j = 1; j <= n; j ++ )  // 用这个节点的距离更新其他节点的最短距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);  // 由于不存在负权边，所以当t等于j时，dist[t] <= dist[t] + g[t][t]，所以不用管g[i][i]的值
    }
    if (dist[n] == 0x3f3f3f3f) return -1;  // 如果不能走到终点，返回-1
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);  // 处理重边，只保留最短的一条边
                                    // 不用管g[i][i]的值，是因为不存在负权边，所以当t等于j时，dist[t] <= dist[t] + g[t][t]，所以不用管g[i][i]的值
    }
    cout << dijkstra() << endl;

    return 0;
}

• 堆优化版的Dijkstra算法

// 朴素Dijkstra算法时间复杂度最多的地方在于遍历寻找距离最短的点
// 这一点可以通过小根堆的堆顶找到，所以可以进行优化

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1.6e5;
int n, m;
int h[N], e[N], w[N], ne[N], idx;  // 邻接表存储稀疏图，w数组用于存储边的权重
int dist[N];
bool st[N];  // st数组用于标记节点是否被处理过，解决存在重边的情况，因为堆修改边是重新插入一条边，st数组就是为了解决这种冗余的情况

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;  // w数组用于存储边的权重
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}

int Dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;  // 以距离为第一关键字，节点值为第二关键字建立小根堆
    heap.push({0, 1});  // 将起点加入堆
    while (heap.size())
    {
        auto t = heap.top();  // 堆顶就是距离最短的点
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;  // 如果已经处理过这个节点，存在重边，就continue
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])  // 用节点ver的距离更新其相邻节点的距离
        {
            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];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    cout << Dijkstra() << endl;

    return 0;
}

• Bellman-Ford算法

for n 次  // 这里的循环次数是有实际意义的，比如循环进行了k次，这意味着从节点1出发，经过不超过k条边的最短路径
    for 所有边 a, b, w  // 边的存储可以使用结构体
        dist[b] = min(dist[b], dist[a] + w);  // 松弛操作

// 循环n次后，满足dist[b] <= dist[a] + w 三角不等式

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010;
int n, m, k;
int dist[N], backup[N];

struct Edge
{
    int a, b, w;
}edges[M];

int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i ++ )  // 最多经过k条边的最短距离，循环k次
    {
        memcpy(backup, dist, sizeof dist);  // backup数组是上一次迭代后dist数组的备份，
                                            // 由于是每个点同时向外出发，因此需要对dist数组进行备份，
                                            // 若不进行备份，会发生串联效应，影响下一个点
        for (int j = 0; j < m; j ++ )  // 遍历m条边
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }
    bellman_ford();
    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);

    return 0;
}

• SPFA
  • spaf算法不能用于存在负环的图
  • spfa是对bellman_ford的优化，bellman_ford是对每条边进行更新，而spfa是只对已经更新的节点更新邻边的距离，因为只有当前节点的距离更新了，它的后继节点的距离才有可能被更新

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;
int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];  // st数组用于标记节点是否已经在队列中，不重复入队

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);  // 将节点1放入队列
    st[1] = true;  // 标记节点1已经在队列中
    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;  // 节点出队后，修改st数组的标记
        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])
                {
                    q.push(j);  // 节点j被更新，并且节点j不在队列中，将节点j加入队列
                    st[j] = true;  // 标记节点j已经在队列中
                }
            }
        }
    }
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    int t = spfa();
    if (t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

• Floyd算法

// 用d[N][N]存储所有的边
for (k = 1; k <= n; k ++ )  // 先循环k，然后i和j的顺序可以颠倒
    for (i = 1; i <= n; i ++ )
        for (j = 1; j <= n; j ++ )
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
// 这时d[i][j]存的就是从i到j的最短路的长度

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N];

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]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &Q);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }
    floyd();
    while (Q -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (d[a][b] > INF / 2) puts("impossible");
        else printf("%d\n", d[a][b]);
    }

    return 0;
}

最小生成树

• 给定一张边带权的无向图$G=(V, E)$，其中$V$表示图中点的集合，$E$表示图中边的集合，$n=|V|$，$m=|E|$。由$V$中的全部$n$个顶点和$E$中$n - 1$条边构成的无向连通子图被称为$G$的一棵生成树，其中边的权值之和最小的生成树被称为无向图$G$的最小生成树。
• 最小生成树中不含有自环

算法	时间复杂度
朴素版Prim	$O(n^2)$
堆优化版Prim	$O(mlogn)$
Kruskal	$O(mlogm)$
***
* 朴素版Prim

// 算法流程
dist[i] <- +∞
for (i = 0; i < n; i ++ )
    t <- 找到集合外距离最近的点  // 集合s指连通块
    用t更新其他点到集合的距离
    st[t] = true;  // 将t加入到集合中去

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];  // 标记第i个节点相对连通块的距离
bool st[N];  // 标记第i个节点是否在连通块中

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 (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        if (i && dist[t] == INF) return INF;  // 如果不是第一次，并且点的距离为INF，则构不成一个连通块，即不存在最小生成树
        st[t] = true;  // 标记节点t已经加入连通块
        if (i) res += dist[t];  // 第一次不算入最小生成树的权值
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);  // 用节点t更新其他点和连通块的距离
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

• Kruskal算法

1. 将所有边按权重从小到大排序
2. 枚举每条边a, b，权重c
    if a, b不连通
        将这条边加入集合中

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 2 * N, INF = 0x3f3f3f3f;
int n, m;
int p[N];

struct Edge
{
    int a, b, 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()
{
    for (int i = 1; i <= n; i ++ ) p[i] = i;  // 初始化并查集
    sort(edges, edges + m);  // 对所有边按照边权从小到大排序
    int res = 0, cnt = 0;  // res记录最小生成树中的边的权重之和，cnt记录加入连通块中的边的数量
    for (int i = 0; i < m; i ++ )  // 枚举每条边
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);
        if (a != b)  // 如果点a和点b不在同一个连通块中
        {
            p[a] = b;  // 把这条边加入连通块
            res += w;
            cnt ++ ;
        }
    }
    if (cnt < n - 1) return INF;
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }
    int t = kruskal();
    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

二分图

算法	时间复杂度	用途
染色法	$O(n + m)$	用于二分图判定
匈牙利算法	$O(mn)$，实际运行时间一般远小于$O(mn)$	用于求得二分图中的最大匹配
* 二分图指可以将所有点分为左右两个集合，所有边都在集合之间，集合内没有边
* 二分图当且仅当图中不含边数为奇数的环

• 染色法

for (i = 1; i <= n; i ++ )
    if i 未染色
        dfs(i, 1)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}

bool dfs(int u, int c)
{
    color[u] = c;  // 将节点u染色成c
    for (int i = h[u]; i != -1; i = ne[i])  // 将这个点的邻边都染色
    {
        int j = e[i];
        if (!color[j])
        {
            if (!dfs(j, 3 - c)) return false;
        }
        else if (color[j] == c) return false;
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    bool flag = true;
    for (int i = 1; i <= n; i ++ )  // 遍历每个节点
    {
        if (!color[i])  // 如果这个节点没有被染色
        {
            if (!dfs(i, 1))  // 如果染色过程中出现矛盾
            {
                flag = false;
                break;
            }
        }
    }
    if (flag) puts("Yes");
    else puts("No");
}

• 匈牙利算法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];  // match数组用于标记每个女生喜欢的男生
bool st[N];  // st数组用于标记女生是否被考虑过

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}

bool find(int x)  // 给男生寻找匹配的女生
{
    for (int i = h[x]; i != -1; i = ne[i])  // 遍历男生有意的每一个女生
    {
        int j = e[i];
        if (!st[j])  // 如果女生没有被考虑过
        {
            st[j] = true;  // 那么就考虑该女生
            if (!match[j] || find(match[j]))  // 如果该妹子没有匹配或者妹子现在匹配的对象可以找到另一个匹配
            {
                match[j] = x;  // 妹子和男生匹配成功
                return true;
            }
        }
    }
    return false;  // 男生匹配失败
}

int main()
{
    scanf("%d%d%d", &n1, &n2, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    int res = 0;
    for (int i = 1; i <= n1; i ++ )
    {
        memset(st, false, sizeof st);  // 每次都需要将st数组全部置为未考虑，这样循环到的男生才会考虑该女生
        if (find(i)) res ++ ; // 如果找到匹配的女生，则匹配数加1
    }
    printf("%d\n", res);

    return 0;
}

动态规划

$DP$问题可以从两个角度考虑：状态表示和状态计算。所谓的状态就是一个未知数，状态表示就是我们思考一下整个问题，需要用几维的状态来表示。状态计算就是指如何一步一步把状态算出来。状态表示可以从两个角度考虑：集合和属性（Max、Min、数量）。即状态表示表示的是哪一个集合，存的是集合的什么属性。状态计算对应集合的划分，即如何把当前的集合划分成更小的子集，使得我们每一个子集都可以算出来，即都可以用前面更小的状态表示出来。集合划分遵循两个原则：不重（某一个元素不可以属于两个集合）、不漏（不能出现某个元素不属于任何集合的情况）。不重不一定什么时候都需要满足，例如求最大值时重复没有影响，但是求个数时就需要满足不重复。

$DP$优化一般来说都是对动态规划的代码或者是动态规划的方程作一个等价变形。

背包问题

背包问题指有$N$件物品，每件物品有两个属性{$v_i, w_i$}，有一个背包，可容纳体积为$V$，如何选择物品，使得在物品体积之和$ \le V$的情况下，物品的价值之和最大。
1. 01背包 （每件物品最多只用一次）
2. 完全背包 （每件物品有无限个）
3. 多重背包 （每件物品最多有$S_i$个）
4. 分组背包 （物品分为不同的组，每组有若干件物品，每组最多只能选择一件物品）

---

1. 01背包

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i ++ )  // f[0][0~m]选取0件物品，应该初始化为0，全局数组，已经为0，所以i从1开始
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];  // 不包含第i件物品的最大价值
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i-1][j - v[i]] + w[i]);  // 包含第i件物品时的最大价值
        }
    cout << f[n][m] << endl;

    return 0;
}

1. 完全背包

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            {
                f[i][j] = f[i - 1][j];
                if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);  // 将关于k的循环优化
            }
    cout << f[n][m] << endl;

    return 0;
}

1. 多重背包

// 朴素版
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k * v[i] <= j && k <= s[i]; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    cout << f[n][m] << endl;

    return 0;
}

// 二进制优化
// 将一种物品的件数s，拆分成二进制整数次幂的组合，每组最多只能选一次
// 从而将多重背包问题转化为01背包问题，时间复杂度由O(NVS)优化为O(nvlogs)
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 25000, M = 2010;  // N = n * logs
int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    int cnt = 0;  // 用cnt当作数组下标
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;  // 2^0
        while (k <= s)
        {
            cnt ++ ;
            v[cnt] = k * a;
            w[cnt] = k * b;
            s -= k;
            k *= 2;
        }
        if (s > 0)  // 剩下的部分 < 2^(k + 1)
        {
            cnt ++ ;
            v[cnt] = s * a;
            w[cnt] = s * b;
        }
    }
    n = cnt;  // 更新n
    for (int i = 1; i <= n; i ++ )  // 01背包优化写法
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;

    return 0;
}

1. 分组背包

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= n; i ++ )  // 优化为一维写法
        for (int j = m; j >= 0; j --)
            for (int k = 0; k < s[i]; k ++ )
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m] << endl;

    return 0;
}

线性DP

递推方程有一个明显的线性的关系。

区间DP

计数类DP

数位统计DP

状态压缩DP

用一个整数的二进制表示，表示不同的状态

树形DP

记忆化搜索

是动态规划的一种写法，使用递归写动态规划，代码会更容易理解。状态计算过了就返回，没有计算过，就计算该状态并返回。

贪心

区间问题

可以尝试按照左端点排序或者右端点排序

Huffman树

用小根堆

排序不等式

绝对值不等式

推公式