算法模板

STL API

vector（变长数组），倍增的思想，支持比较运算（按字典序）
    定义：：
        vector <int> a; 定义：一个vector数组a
        vector <int> a(10); 定义：一个长度为10的vector数组a
        vector <int> a(10,3); 定义：一个长度为10的vector数组a，并且所有元素都为3
    常用函数：：
        size(); 返回元素个数
        empty(); 返回是否是空
        clear(); 清空
        front(); 返回vector的第一个数
        back(); 返回vector的最后一个数
        push_back(); 向vector的最后插入一个数
        pop_back(); 把vector的最后一个数删掉
        begin(); vector的第0个数
        end(); vector的最后一个的数的后面一个数
    倍增的思想：
        系统为某一程序分配空间是，所需时间，与空间大小无关，与申请次数有关
    遍历方法
        假设有个vector <int> a;
        第一种：
            for(int i = 0;i < a.size();i ++) cout<<a[i]<<" ";
        第二种：
            for(vector <int>::iterator i = a.begin();i != a.end();i ++) cout<<*i<<" ";  vector <int>::iterator可以写为auto
        第三种：
            for(auto  x : a) cout<<x<<" ";

pair，支持比较运算，以first为第一关键字，以second为第二关键字（按字典序）
    定义：：
        pair <类型,类型> 变量名;    两个类型可以不同
    初始化方式：
        假设有个pair <int,string> p;
        第一种：
            p = make_pair(10,"abc");
        第二种：
            p = {10,"abc");
    常用函数：：
        first(); 第一个元素
        second(); 第二个元素

string（字符串）
    常用函数：：
        substr(); 返回每一个子串
        c_str(); 返回这个string对应的字符数组的头指针
        size(); 返回字母个数
        length(); 返回字母个数
        empty(); 返回字符串是否为空
        clear(); 把字符串清空
queue（队列）
    定义：：
        queue <类型> 变量名;
    常用函数：：
        size(); 这个队列的长度
        empty(); 返回这个队列是否为空
        push(); 往队尾插入一个元素
        front(); 返回队头元素
        back(); 返回队尾元素
        pop(); 把队头弹出
        注意：队列没有clear函数！！！
    清空：
        变量名 = queue <int> ();
priority_queue（优先队列，堆）
    注意：默认是大根堆！！！
    定义：：
        大根堆：priority_queue <类型> 变量名;
        小根堆：priority_queue <类型,vecotr <类型>,greater <类型>> 变量名
    常用函数：
        size(); 这个堆的长度
        empty(); 返回这个堆是否为空
        push();往堆里插入一个元素
        top(); 返回堆顶元素
        pop(); 弹出堆顶元素
        注意：堆没有clear函数！！！

stack（栈）
    常用函数：
        size(); 这个栈的长度
        empty(); 返回这个栈是否为空
        push(); 向栈顶插入一个元素
        top(); 返回栈顶元素
        pop(); 弹出栈顶元素

deque（双端队列）
    常用函数：
        size(); 这个双端队列的长度
        empty(); 返回这个双端队列是否为空
        clear(); 清空这个双端队列
        front(); 返回第一个元素
        back(); 返回最后一个元素
        push_back(); 向最后插入一个元素
        pop_back(); 弹出最后一个元素
        push_front(); 向队首插入一个元素
        pop_front(); 弹出第一个元素
        begin(); 双端队列的第0个数
        end(); 双端队列的最后一个的数的后面一个数

set，map，multiset，multimap 基于平衡二叉树（红黑树），动态维护有序序列
    set/multiset
        注意：set不允许元素重复，如果有重复就会被忽略，但multiset允许！！！
        常用函数：
            size(); 返回元素个数
            empty(); 返回set是否是空的
            clear(); 清空
            begin(); 第0个数，支持++或--，返回前驱和后继
            end(); 最后一个的数的后面一个数，支持++或--，返回前驱和后继
            insert(); 插入一个数
            find(); 查找一个数
            count(); 返回某一个数的个数
            erase();
                （1）输入是一个数x，删除所有x    O(k + log n)
                （2）输入一个迭代器，删除这个迭代器
            lower_bound(x); 返回大于等于x的最小的数的迭代器
            upper_bound(x); 返回大于x的最小的数的迭代器
    map/multimap
        常用函数：
            insert(); 插入一个数，插入的数是一个pair
            erase(); 
                （1）输入是pair
                （2）输入一个迭代器，删除这个迭代器
            find(); 查找一个数
            lower_bound(x); 返回大于等于x的最小的数的迭代器
            upper_bound(x); 返回大于x的最小的数的迭代器

unordered_set，unordered_map，unordered_muliset,unordered_multimap 基于哈希表
    和上面类似，增删改查的时间复杂度是O(1)
    不支持lower_bound()和upper_bound()

bitset 压位
    定义：
        bitset <个数> 变量名;
    支持：
        ~，&，|，^
        >>，<<
        ==，!=
        []
    常用函数：
        count(); 返回某一个数的个数
        any(); 判断是否至少有一个1
        none(); 判断是否全为0
        set(); 把所有位置赋值为1
        set(k,v); 将第k位变成v
        reset(); 把所有位变成0
        flip(); 把所有位取反，等价于~
        flip(k); 把第k位取反

快速排序

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

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

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

快速选择

// 找第k个最小数
int quick_select(int lo, int hi) {
    if (lo >= hi) return a[k];
    int i = lo - 1, j = hi + 1, x = a[lo + hi >> 1];
    while (true) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i >= j) break;
        swap(a[i], a[j]);
    }
    if (k <= j) return quick_select(lo, j);
    else return quick_select(j + 1, hi);
}

归并排序

const int N = 1e5 + 2;
int a[N], tmp[N];

void merge_sort(int q[], int lo, int hi) {
    if (lo >= hi) return;
  
    int mid = lo + hi >> 1;
    merge_sort(q, lo, mid);
    merge_sort(q, mid + 1, hi);
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= hi) tmp[k++] = q[j++];
    for (i = lo, j = 0; i <= hi; j++, i++) {
        q[i] = tmp[j];
    }
}

二分法

整数二分

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点二分

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度四则运算

这些模板均只考虑为正数的情况，其他的可以分类讨论。

vector采用低位存储的方式。

高精度加法

vector<int> add(vector<int>& a, vector<int>& b) {
    vector<int> c;
    int carry = 0;
    for (int i = 0; i < a.size(); i++) {
        carry += a[i];
        if (i < b.size()) carry += b[i];
        c.push_back(carry % 10);
        carry /= 10;
    }
    if (carry) c.push_back(carry);
    return c;
}

高精度减法

// a >= b
// a < b 可以转为-(b - a)
vector<int> sub(vector<int> &a, vector<int> &b) {
    vector<int> c;
    for (int i = 0, carry = 0; i < a.size(); i++) {
        carry = a[i] - carry;
        if (i < b.size()) carry -= b[i];
        c.push_back((carry + 10 ) % 10);
        if (carry < 0) carry = 1;
        else carry = 0;
    }
  
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

高精度-低精度乘法

//适用于b是小整数的情况
vector<int> mul(vector<int>& a, int b) {
    vector<int> c;
    int carry = 0;
    for (int i = 0; i < a.size() || carry; i++) {
        if (i < a.size()) carry += a[i] * b;
        c.push_back(carry % 10);
        carry /= 10;
    }
    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;
    r = 0;
    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;
}

前缀和

适用于求区间 [l, r]和的情况

一维

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

二维

S[i, j] = 第i行j列格子左上部分所有元素的和
前缀和公式：
S[i, j] = S[i - 1, j] + S[i, j - 1] - S[i - 1, j - 1] + a[i, j]

以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

如何通过两重for循环求解S[i][j]
S[i][j] = S[i-1][j] + S[i][j-1] - S[i][j] + a[i][j]

差分

适用于对区间 [l, r]进行加常数c的操作

一维

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

二维

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

KMP算法

int ne[N];
// 求next数组
// a为匹配模式字符串p
for (int i = 2, j = 0; i < n; i++) {
    while (j && a[i - 1] != a[j]) j = ne[j];
    if (a[i - 1] == a[j]) j++;
    ne[i] = j;
}

// 匹配过程
// b为文本字符串
void kmp() {
    for (int i = 0, j = 0; i < m; i++) {
        while (j && b[i] != a[j]) j = ne[j];
        if (b[i] == a[j]) j++;
        if (j == n) {
            printf("%d ", i - j + 1);
            i -= 1;
            j = ne[j - 1];
        }
    }
}

堆

int a[N], n;

void down(int u) {
    int v = u;
    if (2 * u <= n && a[v] > a[2 * u]) {
        v = 2 * u;
    }
    if (2 * u + 1 <= n && a[v] > a[2 * u + 1]) {
        v = 2 * u + 1;
    }
    if (u != v) {
        swap(a[u], a[v]);
        down(v);
    }
}

void up(int u) {
    while (u / 2 != 0 && h[u] < h[u / 2]) {
        swap(a[u], a[u / 2]);
        u /= 2;
    }
}

图论

邻接表

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

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

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

拓扑排序

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

朴素Dijkstra算法

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

堆优化Dijstra算法

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算法

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

int dist[N], backup[N];

void bellman_ford() 
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    // 限定i条边的情况下，最短距离
    for (int i = 0; i < n; i++) 
    {
        memcpy(backup, dist, sizeof dist);
        for (int j = 0; j < m; j++) 
        {
            auto e = edge[j];
            int a = e.a, b = e.b, w = e.w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    
    if (dist[n] > 0x3f3f3f3f / 2) printf("impossible");
    else printf("%d", dist[n]);
}

spfa算法

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

spfa算法判断负环

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

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = 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];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

Floyd算法

// 初始化：
    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;

// 算法结束后，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]);
}

Prim算法

int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[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 (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

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

        if (i) res += dist[t];
        st[t] = true;

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

    return res;
}

Kruskal算法

int n, m;       // 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()
{
    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 a = edges[i].a, b = edges[i].b, w = edges[i].w;

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

    if (cnt < n - 1) return INF;
    return res;
}

染色法判断二分图

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

// 参数：u表示当前节点，c表示当前点的颜***ool 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;
}

匈牙利算法

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])
        {
            st[j] = true;
            if (match[j] == 0 || 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 ++ ;
}