基础算法

高精度加法

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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(t);
    while (c.size() > 1 && !c.back()) c.pop_back();

    return c;
}

高精度减法

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

vector<int> sub(vector<int> a, vector<int> b)   
{
    vector<int> c;
    for (int i = 0, t = 0; i < a.size(); i++)
    {
        t = a[i] - (t < 0);
        if (i < b.size()) t -= b[i];
        c.push_back((t + 10) % 10);
    }
    while (c.size() > 1 && !c.back()) c.pop_back();

    return c;
}

高精度乘法

大乘小

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> mul(vector<int> &a, int b)  //倒进倒出
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || t; i++)
    {
        if (i < a.size()) t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();

    return c;
}
大乘大
cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> mul(vector<int> a, vector<int> b)  //倒进倒出
{
    vector<int> c(N * N);
    for (int i = 1; i < a.size(); i++)
    {
        for (int j = 1; j < b.size(); j++)
        {
            c[i + j - 1] += a[i] * b[j];
            c[i + j] += c[i + j - 1] / 10;
            c[i + j - 1] %= 10;
        }
    }
    while (c.size() > 1 && !c.back()) c.pop_back();

    return c;
}

高精度除法

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}

二维前缀和

cpp
1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    for (int i = 1; i <= n; i++)  //把s处理成前缀和矩阵
        for (int j = 1; j <= m; j++)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl;

    return 0;
}

二维差分

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    for (int i = 1; i <= n; i++)   //把a处理成差分矩阵
        for (int j = 1; j <= m; j++)
            insert(i, j, i, j, a[i][j]);

    int x1, y1, x2, y2, c;
    cin >> x1 >> y1 >> x2 >> y2 >> c;
    insert(x1, y1, x2, y2, c);     //把这个矩阵的所有元素+1

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++ ) cout << b[i][j] << ' '; 
        cout << endl;
    }

    return 0;
}

返回二进制最低位1

cpp
1
2
3
4
int lowbit(int x)
{
    return x & -x;
}

离散化

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
    for (int i = 1; i <= n; i++) b[i] = a[i];
    sort(b + 1, b + 1 + n);

    int bn = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; i++)
    {
        int l = 1, r = bn;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (b[mid] < a[i]) l = mid + 1;
            else r = mid;
        }
        a[i] = l;
    }
	
    return 0;
}

区间合并

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<PII> merge()
{
    sort(a, a + n);

    vector<PII> res;
    int st = -2e9, ed = -2e9;
    for (int i = 0; i < n; i++)
    {
        if (ed < a[i].x)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = a[i].x, ed = a[i].y;
        }
        else ed = max(ed, a[i].y);
    }
    if (st != -2e9) res.push_back({st, ed});

    return res;
}

st表

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> f[i][0];

    for (int j = 1; j <= 20; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);  //初始化

    while (m--)
    {
        int l, r;
        cin >> l >> r;
        int k = log2(r - l + 1);
        cout << max(f[l][k], f[r - (1 << k) + 1][k]) << endl;  //查询
    }
	
    return 0;
}

数据结构

kmp

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    ne[0] = -1;
    for (int i = 1, j = -1; i < n; i++)   //初始化
    {
        while (j != -1 && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }

    for (int i = 0, j = -1; i < m; i++)
    {
        while (j != -1 && s[i] != p[j + 1])  j = ne[j];
        if (s[i] == p[j + 1]) j++;
        if (j == n - 1)
        {
            cout << i - j << ' ';   //匹配位置的起点，从0开始
            j = ne[j];
        }
    }

    return 0;
}

单调队列

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
deque<int> q;

int main()
{
    for (int i = 0; i < n; i++)  //窗口最小值
    {
        while (q.size() && a[q.back()] >= a[i]) q.pop_back();
        while (q.size() && i - k + 1 > q.front()) q.pop_front();
        q.push_back(i);
        if (i >= k - 1) cout << a[q.front()] << ' ';
    }

    return 0;
}

单调栈

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
stack<int> s;

int main()
{
    for (int i = 0; i < n; i++)  //左边第一个比它小的值
    {
        while (s.size() && s.top() >= a[i]) s.pop();
        if (s.size()) cout << s.top() << ' ';
        else cout << "-1 ";
        s.push(a[i]);
    }

    return 0;	
}

并查集

cpp
1
2
3
4
5
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

字符串哈希

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int P = 13331;

ull p[N], h[N];

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

int main()
{
    p[0] = 1;
    for (int i = 1; i <= n; i++)   
    {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + s[i - 1];
    }

    return 0;
}

树状数组

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int lowbit(int x)  //返回二进制最低位1
{
    return x & -x
}

void modify(int x, int k)  //修改
{
    while (x <= n)
    {
        s[x] += k;
        x += lowbit(x);
    }
}

int query(int x)  //查询
{
    int res = 0;
    while (x)
    {
        res += s[x];
        x -= lowbit(x);
    }
    return res;
}

线段树

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#define ls u << 1
#define rs u << 1 | 1

typedef long long ll;

struct Node
{
    int l, r;
    ll sum, add;  //sum: 区间和, add: 懒标记
}tr[N * 4];

void pushup(int u)  //上传
{
    tr[u].sum = tr[ls].sum + tr[rs].sum;    
}

void pushdown(int u)  //懒标记下放
{
    if (!tr[u].add) return;
    tr[ls].sum += (tr[ls].r - tr[ls].l + 1) * tr[u].add;
    tr[rs].sum += (tr[rs].r - tr[rs].l + 1) * tr[u].add;
    tr[ls].add += tr[u].add;
    tr[rs].add += tr[u].add;
    tr[u].add = 0;
}

void build(int u, int l, int r)  //建树
{
    tr[u] = {l, r, w[l]};
    if (l != r)
    {
        int mid = l + r >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int x)  //修改
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += (tr[u].r - tr[u].l + 1) * x;
        tr[u].add += x; 
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(ls, l, r, x);
        if (r > mid) modify(rs, l, r, x);
        pushup(u);
    }
}

ll query(int u, int l, int r)  //查询
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        ll res = 0;
        if (l <= mid) res += query(ls, l, r);
        if (r > mid) res += query(rs, l, r);
        return res;
    }
}

可持久化线段树

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int root[N], tot;
int ls[N * 25], rs[N * 25], val[N * 25];

void build(int &u, int l, int r)  //建树
{
    u = ++tot;
    if (l == r) val[u] = a[l];
    else
    {
        int mid = l + r >> 1;
        build(ls[u], l, mid);
        build(rs[u], mid + 1, r);
    }
}

void modify(int &u, int v, int l, int r, int p, int x)  //把位置p的值修改为x
{
    u = ++tot;
    ls[u] = ls[v], rs[u] = rs[v], val[u] = val[v];
    if (l == r) val[u] = x;
    else
    {
        int mid = l + r >> 1;
        if (p <= mid) modify(ls[u], ls[v], l, mid, p, x);
        else modify(rs[u], rs[v], mid + 1, r, p, x);
    }
}

int query(int u, int l, int r, int p)  //查询
{
    if (l == r) return val[u];
    int mid = l + r >> 1;
    if (p <= mid) return query(ls[u], l, mid, p);
    else return query(rs[u], mid + 1, r, p);
}

静态区间第 kk 小数

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

int n, m;
int a[N], b[N];
int root[N], tot;
int ls[N * 25], rs[N * 25], sum[N * 25];

void modify(int &u, int v, int l, int r, int p)
{
    u = ++tot;
    ls[u] = ls[v], rs[u] = rs[v], sum[u] = sum[v] + 1;
    if (l == r) return;
    int mid = l + r >> 1;
    if (p <= mid) modify(ls[u], ls[v], l, mid, p);
    else modify(rs[u], rs[v], mid + 1, r, p);
}

int query(int u, int v, int l, int r, int k)   //查询区间第k小
{
    if (l == r) return l;
    int s = sum[ls[u]] - sum[ls[v]];
    int mid = l + r >> 1;
    if (k <= s) return query(ls[u], ls[v], l, mid, k);
    else return query(rs[u], rs[v], mid + 1, r, k - s);
}

int query(int u, int v, int l, int r, int k)   //查询区间比k小的个数
{
    if (l == r) return sum[u] - sum[v];
    int mid = l + r >> 1;
    int res = 0;
    if (k <= mid) res += query(ls[u], ls[v], l, mid, k);
    else
    {
        res += sum[ls[u]] - sum[ls[v]];
        res += query(rs[u], rs[v], mid + 1, r, k);
    }
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) b[i] = a[i];
    sort(b + 1, b + 1 + n);

    int bn = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; i++)
    {
        int l = 1, r = bn;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (b[mid] < a[i]) l = mid + 1;
            else r = mid;
        }
        modify(root[i], root[i - 1], 1, bn, l);
    }

    while (m--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        int p = query(root[r], root[l - 1], 1, bn, k);
        cout << b[p] << endl;
    }

    return 0;
}

莫队

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct Q
{
    int id, l, r;
}q[N];
int n, m, k;
int b, sum;
int a[N], c[N];

bool cmp(Q A, Q B)
{
    if (A.l / b != B.l / b) return A.l < B.l;
    if (A.l / b & 1) return A.r < B.r;
    return A.r > B.r;
}

void add(int x)  //添加
{
    c[x]++;
}

void del(int x)  //删除
{
    c[x]--;
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= m; i++)  //离线查询
    {
        int l, r;
        cin >> l >> r;
        q[i] = {i, l, r};
    }

    b = sqrt(n);
    sort(q + 1, q + 1 + m, cmp);

    for (int i = 1, l = 1, r = 0; i <= m; i++)  //查询区间每个数的出现次数
    {
        while (l > q[i].l) add(a[--l]);
        while (r < q[i].r) add(a[++r]);
        while (l < q[i].l) del(a[l++]);
        while (r > q[i].r) del(a[r--]);
    }
    return 0;
}

图论

堆优化dijkstra

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    d[1] = 0;

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

        int ver = t.y;
        if (st[ver]) continue;
        st[ver] = true;

        for (int i = 0; i < h[ver].size(); i++)
        {
            int j = h[ver][i].x, w = h[ver][i].y;
            if (d[j] > d[ver] + w)
            {
                d[j] = d[ver] + w;
                heap.push({d[j], j});
            }
        }
    }

    return (d[n] == 0x3f3f3f3f)? -1 : d[n];
}

bellman-ford

有边数限制的最短路

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int N = 510, M = 10010;

int n, m, k;
int dist[N], last[N];
struct Edge
{
    int a, b, c;
}edge[M];

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    for (int i = 0; i < k; i++)
    {
        memcpy(last, dist, sizeof dist);
        for (int j = 0; j < m; j++)
        {
            auto e = edge[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
}

int main()
{
    cin >> n >> m >> k;

    for (int i = 0; i < m; i++)
        cin >> edge[i].a >> edge[i].b >> edge[i].c;
        
    bellman_ford();
        
    if (dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << dist[n] << endl;

    return 0;
}

spfa

判断负环

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
bool spfa()
{
	queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        st[i] = true;
        q.push(i);
    }

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

        for (int i = 0; i < h[t].size(); i++)
        {
            int j = h[t][i].x, w = h[t][i].y;
            if (dist[j] > dist[t] + w)
            {
                dist[j] = dist[t] + w;
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n) return true;

                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    return false;
}

floyd

cpp
1
2
3
4
5
6
7
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

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    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 (dist[t] == INF) return INF;

        st[t] = true;
        res += dist[t];

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

    return res;
}

int main()
{
    memset(g, 0x3f, sizeof g);

    cin >> n >> m;
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();
    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}

kruskal

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    for (int i = 1; i <= n; i++) p[i] = i;

    int cnt = 0, res = 0;
    for (int i = 0; i < m; i++)
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;

        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            res += w;
            cnt++;
        }
    }

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

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> edge[i].a >> edge[i].b >> edge[i].w;

    sort(edge, edge + m);

    int t = kruskal();
    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}

染色法判断二分图

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = 0; i < h[u].size(); i++)
    {
        int j = h[u][i];
        if (!color[j])
        {
            if (!dfs(j, 3 - c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

int main()
{
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        h[a].push_back(b), h[b].push_back(a);
    }

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

    if (flag == true) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

二分图的最大匹配

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
bool find(int x)
{
    for (int i = 0; i < h[x].size(); i++)
    {
        int j = h[x][i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

int main()
{
    cin >> n1 >> n2 >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        h[a].push_back(b);
    }

    int res = 0;
    for (int i = 1; i <= n1; i++)
    {
        memset(st, false, sizeof st);
        if (find(i)) res++;
    }

    cout << res << endl;

    return 0;
}

lca

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void dfs(int u, int father)
{
    dep[u] = dep[father] + 1;
    f[u][0] = father;

    for (int i = 1; i <= 15; i++) 
        f[u][i] = f[f[u][i - 1]][i - 1];

    for (int i = 0; i < s[u].size(); i++)
        if (s[u][i] != father)
            dfs(s[u][i], u);
}

int lca(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);

    for (int i = 15; i >= 0; i--)
        if (dep[f[u][i]] >= dep[v])
            u = f[u][i];

    if (u == v) return u;

    for(int i = 15; i >= 0; i--)
        if (f[u][i] != f[v][i])
            u = f[u][i], v = f[v][i];

    return f[u][0];
}

tarjan SCC缩点

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void tarjan(int u)
{
    dfn[u] = low[u] = ++tot;
    stk[++top] = u, instk[u] = 1;
    for (int i = 0; i < h[u].size(); i++)
    {
        int v = h[u][i];
        if (!dfn[v]) 
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (instk[v]) low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u])
    {
        cnt++;
        int v;
        do 
        {
            v = stk[top--];
            instk[v] = 0;
            scc[v] = cnt;
            sz[cnt] += w[v];
        } while (u != v);
    }
}

拓扑排序

基环树找环

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void topsort()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        d[i] = h[i].size();
        if (d[i] == 1) q.push(i);
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < h[t].size(); i++)
        {
            int j = h[t][i];
            d[j]--;
            if (d[j] == 1) q.push(j);
        }
    }
}

2—SAT

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	cin >> n >> m;
	while (m--)
	{
		int u, a, v, b;
		cin >> u >> a >> v >> b;
		h[u + !a * n].push_back(v + b * n);
		h[v + !b * n].push_back(u + a * n);
	}
	
	for (int i = 1; i <= n * 2; i++)
		if (!dfn[i])
			tarjan(i);
	
	bool flag = false;
	for (int i = 1; i <= n; i++)
		if (scc[i] == scc[i + n])
		{
			flag = true;
			break;
		}
		
	if (flag) cout << "IMPOSSIBLE" << endl;
	else 
	{
		cout << "POSSIBLE" << endl;
		for (int i = 1; i <= n; i++) cout << (scc[i] > scc[i + n]) << ' ';
	}
	
	return 0;
}

数学

线性筛质数

cpp
1
2
3
4
5
6
7
8
9
10
11
12
void get_prime(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if(!st[i]) prime[cnt++] = i;
        for (int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

筛法求欧拉函数

欧拉函数，即 ϕ(n)\phi(n)，表示的是小于等于 nn 和 nn 互质的数的个数。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void get_eulers(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }

        for (int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0)
            {
                phi[prime[j] * i] = prime[j] * phi[i];
                break;
            }
            phi[prime[j] * i] = (prime[j] - 1) * phi[i];
        }
    }
}

筛法求莫比乌斯函数

μ为莫比乌斯函数，定义为μ(n)={1n=10n 含有平方因子(−1)kk为n的本质不同质因子个数\mu \text{为莫比乌斯函数，定义为} \\ \mu(n) = \begin{cases} 1 & n = 1 \\0 & n \text{ 含有平方因子} \\(-1)^k & k \text{为} n \text{的本质不同质因子个数}\end{cases}

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void get_mobius(int n)
{
    mobius[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            prime[cnt++] = i;
            mobius[i] = -1;
        }
        for (int j = 0; prime[j] <= n / i; j++)
        {
            int m = prime[j] * i;
            st[m] = true;
            if (i % prime[j] == 0)
            {
                mobius[m] = 0;
                break;
            }
            else mobius[m] = -mobius[i];
        }
    }
}

快速幂

cpp
1
2
3
4
5
6
7
8
9
10
11
int qmi(int a, int b, int p)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

龟速乘

cpp
1
2
3
4
5
6
7
8
9
10
11
int qmul(int a, int b, int p)
{
    int res = 0;
    while (b)
    {
        if (b & 1) res = (LL)(res + a) % p;
        a = (LL)(a + a) % p;
        b >>= 1;
    }
    return res;
}

扩展欧几里得

给定 nn 对正整数 ai,bia_i,b_i，对于每对数，求出一组 xi,yix_i,y_i，使其满足 ai×xi+bi×yi=gcd(ai,bi)a_i \times x_i+b_i \times y_i=gcd(a_i,b_i)。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    else
    {
        int x1 = 0, y1 = 0;
        int d = exgcd(b, a % b, x1, y1);
        x = y1, y = x1 - a / b * y1;
        return d;
    }
}

扩展中国剩余定理

求解线性同余方程组{x≡r1 (mod m1)x≡r2 (mod m2) ⋮ x≡rn (mod mn)\text{求解线性同余方程组} \begin{cases}x \equiv r_1 \ (\text{mod} \ m_1) \\x \equiv r_2 \ (\text{mod} \ m_2) \\\vdots \\x \equiv r_n \ (\text{mod} \ m_n)\end{cases} 求 xx 的最小非负整数解

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int excrt(int a[], int m[])
{
    int m1, m2, a1, a2, x, y;
    m1 = m[0], a1 = a[0];
    for (int i = 1; i < n; i++)
    {
        m2 = m[i], a2 = a[i];
        int d = exgcd(m1, m2, x, y);
        if ((a2 - a1) % d) return -1;
        x = x * (a2 - a1) / d;
        x = (x % (m2 / d) + m2 / d) % (m2 / d);
        a1 = m1 * x + a1;
        m1 = m1 * m2 / d;
    }
    
    return (a1 % m1 + m1) % m1;
}

signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> m[i] >> a[i];
    
    cout << excrt(a, m) << endl;
    
    return 0;
}

高斯消元

线性方程组

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int gauss()
{
    int r = 0;
    for (int i = 0; i < n; i++)
    {
        int t = r;
        for (int j = r; j < n; j++)
           if (fabs(a[j][i]) > fabs(a[t][i]))
            t = j;

        if (fabs(a[t][i]) < eps) continue;

        if (t != r) swap(a[t], a[r]);

        for (int j = n; j >= i; j--) 
            a[r][j] /= a[r][i];

        for (int j = r + 1; j < n; j++)
            if (fabs(a[j][i]) > eps)
                for (int k = n; k >= i; k--)
                    a[j][k] -= a[r][k] * a[j][i];
        r++;
    }

    if (r < n)
    {
        for (int i = r; i < n; i++)
            if (fabs(a[i][n]) > eps) 
                return 0;  //无解
        return 2;   //无数解
    }

    for (int i = n - 2; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            a[i][n] -= a[i][j] * a[j][n];

    return 1; //唯一解
}

异或线性方程组

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int gauss()
{
    int r = 0;
    for (int i = 0; i < n; i++)
    {
        int t = r;
        for (int j = r; j < n; j++)
            if (a[j][i] > a[t][i])
                t = j;

        if (!a[t][i]) continue;

        if (t != r) swap(a[t], a[r]);

        for (int j = r + 1; j < n; j++)
            if (a[j][i])
                for (int k = n; k >= i; k--)
                    a[j][k] ^= a[r][k];

        r++;
    }

    if (r < n)
    {
        for (int i = r; i < n; i++)
            if (a[i][n])
                return 0;
        return 2;
    }

    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j <= n; j++)
            a[i][n] ^= a[i][j] * a[j][n];

    return 1;
}

组合数I

cpp
1
2
3
4
5
6
7
8
9
void init()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= i; j++)
        {
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
}

组合数II

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int qmi(int a, int b, int p)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        b >>= 1;
    }
    return res;
}

void init()
{
    f[0] = g[0] = 1;
    for (int i = 1; i <= 100000; i++)
    {
        f[i] = (ll)f[i - 1] * i % mod;
        g[i] = (ll)g[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

int main()
{
    init();
    
    cin >> t;
    while (t--)
    {
        cin >> a >> b;
        int res = f[a] * ((ll)g[b] * g[a - b] % mod) % mod;
        cout << res << endl;
    }

    return 0;
}

组合数III

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int qmi(int a, int k)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }

    return res;
}

int C(int a, int b)
{
    if (b > a) return 0;

    int res = 1;
    for (int i = 1, j = a; i <= b; i++, j--)
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2) % p;
    }

    return res;
}

int lucas(LL a, LL b)
{
    if (a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

组合数IV

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int get_num(int a, int b)
{
    int res = 0;
    while (a)
    {
        res += a / b;
        a /= b;
    }

    return res;
}

int main()
{
    cin >> n >> m;

    get_primes(n);
    for (int i = 0; i < cnt; i++) 
        num[i] = get_num(n, p[i]) - get_num(m, p[i]) - get_num(n - m, p[i]);

    vector<int> res;
    res.push_back(1);

    for (int i = 0; i < cnt; i++)
        for (int j = 0; j < num[i]; j++)
            res = mul(res, p[i]);

    for (int i = res.size() - 1; i >= 0; i--) cout << res[i];

    return 0;
}

Nim博弈论

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
    cin >> n;

    while (n--)
    {
        int x;
        cin >> x;
        res ^= x;
    }

    if (res == 0) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}

Sg函数

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int sg(int x)
{
    if (f[x] != -1) return f[x];

    unordered_set<int> S;
    for (int i = 0; i < x; i ++ )
        for (int j = 0; j <= i; j ++ )
            S.insert(sg(i) ^ sg(j));

    for (int i = 0;; i ++ )
        if (!S.count(i))
            return f[x] = i;
}


int main()
{
    cin >> n;

    memset(f, -1, sizeof f);

    int res = 0;
    while (n -- )
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }

    if (res) puts("Yes");
    else puts("No");

    return 0;
}

异或线性基

对于一个数组 aa，若 pp 是它的一组异或线性基，则

  • pp 中任意非空子集异或和不为 00
  • pp 中每个数的最高位 11 唯一
  • aa 中任意元素都可以通过 pp 的子集异或出来
cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void gauss()
{
    cnt = 0;
    for (int i = 63; i >= 0; i--)
    {
        for (int j = cnt; j < n; j++)
            if (p[j] >> i & 1) 
                swap(p[j], p[cnt]);
        
        if (!(p[cnt] >> i & 1)) continue;
        
        for (int j = 0; j < n; j++)
            if (j != cnt && p[j] >> i & 1)
                p[j] ^= p[cnt];
                
        cnt++;
        if (cnt == n) break;
    }
}

凸包

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
struct point
{
    double x, y;
};

int n;
point a[N], s[N];
int tt;

bool cmp(point A, point B)
{
    if (A.x != B.x) return A.x < B.x;
    return A.y < B.y;
}

double cross(point A, point B, point C)
{
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

double dist(point A, point B)
{
    return sqrt((B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y));
}

double andrew()
{
    sort(a + 1, a + n + 1, cmp);

    for (int i = 1; i <= n; i++)
    {
        while (tt > 1 && cross(s[tt - 1], s[tt], a[i]) <= 0) tt--;
        s[++tt] = a[i];
    }

    int t = tt;
    for (int i = n - 1; i > 0; i--)
    {
        while (tt > t && cross(s[tt - 1], s[tt], a[i]) <= 0) tt--;
        s[++tt] = a[i];
    } 

    double res = 0;
    for (int i = 1; i < tt; i++) res += dist(s[i], s[i + 1]);
        
    return res;
}

裴蜀定理

设 a,b 是不全为零的整数，对任意整数 x, y,满足 gcd⁡(a,b)∣ax+by,且存在整数 x, y,使得 ax+by=gcd⁡(a,b).设\ a, b\ 是不全为零的整数， 对任意整数\ x,\ y, 满足\ \gcd(a, b) \mid ax + by, 且存在整数\ x,\ y, 使得\ ax + by = \gcd(a, b).

费马小定理

若 p 为素数，gcd(a,p)=1，则 ap−1≡1(mod p)若\ p\ 为 素数，gcd(a,p)=1，则\ a^{p-1} \equiv 1(mod\ p)

另一个形式：对于任意整数 a，有 ap≡a(mod p)另一个形式：对于任意整数\ a，有\ a^p \equiv a(mod\ p)

欧拉定理

 若gcd(a,m)=1，则 aphi(m)≡1(mod m)\ 若 gcd(a,m)=1，则\ a^{phi(m)} \equiv 1(mod\ m)

威尔逊定理

对于素数 p 有(p−1)!≡−1(mod p)对于素数\ p\ 有 (p-1)! \equiv -1(mod\ p)

动态规划

二进制优化多重背包

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int main()
{
    cin >> n >> m;

    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int a, b, s;
        cin >> a >> b >> s;

        int k = 1;
        while (k <= s)
        {
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }

        if (s > 0)
        {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;
    for (int i = 1; i <= n; i++)
        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;
}

单调队列优化多重背包

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;

        memcpy(g, f, sizeof f);

        for (int j = 0; j < v; j++)
        {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v)
            {
                if (hh <= tt && q[hh] < k - s * v) hh++;
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt--;
                q[++tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}

最长上升子序列

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int len = 0;
    for(int i = 0; i < n; i++)  //严格单调递增
    {
        int l = 0, r = len;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }

    cout << len << endl;

    return 0;
}

最长公共子序列

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int main()
{
    cin >> n >> m;
    cin >> k;
    s = ' ' + k;
    cin >> k;
    p = ' ' + k;
    
    for (int i = m; i; i--) c[p[i] - 'a'].push_back(i);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < c[s[i] - 'a'].size(); j++)
            w.push_back(c[s[i] - 'a'][j]);
    
    for (int i = 0; i < w.size(); i++)
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < w[i]) l = mid;
            else r = mid - 1;
        }
        q[r + 1] = w[i];
        len = max(len, r + 1);
    }
    
    cout << len << endl;
    
    return 0;
}

数位dp

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int dp(int u, int cnt, int op)  
{
    if (u == -1) return cnt == k;
    if (!op && ~f[u][cnt]) return f[u][cnt];

    int res = 0, maxv = op? min(1, num[u]) : 1;
    for (int i = 0; i <= maxv; i++)
    {
        if (cnt + i > k) continue;
        res += dp(u - 1, cnt + i, op && i == num[u]);
    }

    return op? res : f[u][cnt] = res;
}

int cal(int n)
{
    num.clear();
    memset(f, -1, sizeof f);

    while (n)
    {
        num.push_back(n % b);
        n /= b;
    }

    return dp(num.size() - 1, 0, 1);
}