数据结构与算法

个人总结，欢迎纠错

基础算法

二分

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
//二分的前提是区间具有单调性
bool check(int x) {}
//左分界
int bsearchl(int a[], int l, int r)
{
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    //循环结束后l等于r
    return l;
}
//右分界
int bsearchr(int a[], int l, int r)
{
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//求解a的b次方
//将b拆解成二进制的形式，把a的b次方给拼出来
int qmi(int a, int b, int mod)
{
    int res = 1;
    while(b)
    {
        if(b & 1)
            res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

RMQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//解决区间最大最小值的利器，不支持修改
int a[n + 1];//所查询区间
int Log2[n + 1], st[n + 1][m + 1];//m为log2n, 假设所询问的是区间最小值
void init()
{
    Log2[1] = 0; 
    for(int i = 2; i <= n; i++)
        Log2[i] = Log2[i / 2] + 1;
    for(int i = 1; i <= n; i++)
        st[i][0] = a[i];
    for(int k = 1; k <= m; k++)
        for(int i = 1; i <= n; i++)
            st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]); 
}
int query(int l, int r)
{
    int k = Log2[r - l + 1];
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}

前缀和与差分

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 a2[n + 1];//一维
//一维前缀和
int pre[n + 1];
void get_pre1()
{
    pre[0] = 0;
    for(int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] + a[i];
}
//一维差分
int dif[n + 1];
void get_dif1()
{
    dif[0] = 0;
    for(int i = 1; i <= n; i++)
        dif[i] = a[i] - a[i - 1];
}
int a[n + 1][m + 1]//二维
//二维前缀和
int pre2[n + 1][m + 1];
void get_pre2()
{
    pre2[0][0] = 0;
    for(int i = 1; i <= n; i++)
        pre2[i][0] = 0;
    for(int i = 1; i <= m; i++)
        pre2[0][i] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            pre2[i][j] = a2[i][j] + pre2[i - 1][j] + pre2[i][j - 1] - pre2[i - 1][j - 1];
}
int dif2[n + 1][m + 1];
void get_dif2()
{
    dif2[0][0] = 0;
    for(int i = 1; i <= n; i++)
        dif2[i][0] = 0;
    for(int i = 1; i <= m; i++)
        dif2[0][i] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            dif2[i][j] = a2[i][j] - a2[i - 1][j] - a2[i][j - 1] + a2[i - 1][j - 1];
}

字符串

字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//通过哈希思想将字符串映射成一个整数
typedef unsigned long long ull;//通过无符号longlong省去了取模操作
const int base = 131;//base选取131和13331，冲突概率比较小可以近似看做无冲突
int p[n + 1];//存储p的0~n次方
int h[n + 1];//字符串前缀的哈希值
void init()
{
    p[0] = 1;
    for(int i = 1; i <= n; i++)
        p[i] = p[i - 1] * base;
}
//将字符串转换的哈希值
void geth(string str)
{
    h[i] = 0;
    for(int i = 0; i < str.size(); i++)
        h[i + 1] = h[i] * base + str[i];
}
//获取一段子串的哈希值
void getH(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

kmp

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 nxt[n + 1];
char str[n + 1], p[n + 1];
//获取最长公共前后缀
void get_nxt()
{
    int n = strlen(p);
    nxt[0] = nxt[1] = 0;
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j && p[i] != p[j + 1]) j = nxt[j];
        if(p[i] == p[j + 1]) j++;
        nxt[i] = j;
    }
}
int kmp()
{
    get_nxt();
    int n = strlen(str), m = strlen(p);
    for(int i = 1, j = 0; i < = n; i++)
    {
        while(j && str[i] != p[j + 1]) j = nxt[j];
        if(str[i] == p[j + 1]) j++;
        if(j == m)
            return i - m + 1;
    }
    return -1;
}

manacher

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 d[n];
string change(string str)
{
    string res = "#";
    for(int i = 0; i < str.size(); i++)
        res += str[i], res += '#';
    return " "+res;
}
int manacher(string str)
{
    d[1] = 1;
    int res = 0;
    str = change(str);
    int n = strlen(str);
    for(int i = 1; l = 1, r = 1; i <= n; i++)
    {
        int j = l + r - i;
        d[i] = max(1, min(d[j], r - i + 1));
        if(i + d[i] > r)
        {
            while(i - d[i] >= 1 && i + d[i] <= n && str[i - d[i]] == str[i + d[i]]) d[i]++;
            l = i - d[i] + 1, r = i + d[i] - 1;
        }
        res = max(res, d[i] - 1);
    }
    return res;
}

数据结构

Trie

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
//假设字符集只有小写字母
//将输入的所以字符建立一颗字符前缀树
int trie[n + 1][26], cnt[n + 1], tot;
void insert(string str)
{
    int p = 0;
    for(int i = 0; i < str.size(); i++)
    {
        int j = str[i] - 'a';
        if(trie[p][j] == 0)
            trie[p][j] = ++tot;
        p = trie[p][j];
    }
    cnt[p]++;
}
bool query(string str)
{
    int p = 0;
    for(int i = 0; i < str.size(); i++)
    {
        int j = str[i] - 'a';
        if(trie[p][j] == 0) return false;
        p = trie[p][j];
    }
    return cnt[p];
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//用来维护朋友的朋友是朋友的关系
int fa[n + 1];
void init()
{
    for(int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    fa[x] = y;
}

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//动态维护前缀和的工具
int tree[n + 1];
void add(int x, int val)
{
    while(x <= n)
        tree[x] += val, x += x & -x;
}
int aks(int x)
{
    int res = 0;
    while(x)
        res += tree[x], x -= x & -x;
    return res;
}

堆

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
//以最小堆为例
int a[n + 1], heap[n + 1];
void up(int x)
{
    while(x / 2 > 0 && heap[x] < heap[x / 2])
        swap(heap[x], heap[x / 2]), u /= 2;
}
void down(x)
{
    int t = x;
    if(x * 2 <= n && heap[x * 2] < heap[t]) t = x * 2;
    if(x * 2 + 1 <= n && heap[x * 2 + 1] < heap[t]) t = x * 2 + 1;
    if(t != x)
    {
        swap(heap[x], heap[t]);
        down(t);
    }
}
void build()
{
    for(int i = 1; i <= n; i++)
        heap[i] = a[i];
    for(int i = n / 2; i > 0; i--)
        down(i);
}

AC自动机

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
//其实就是树上kmp
//假设字符集是小写字母
int trie[n + 1][26], tot;
int nxt[n + 1], cnt[n + 1];
void insert(string str)
{
    int p = 0;
    for(int i = 0; i < str.size(); i++)
    {
        int j = str[i] - 'a';
        if(trie[p][j] == 0)
            trie[p][j] = ++tot;
        p = trie[p][j];
    }
    cnt[p]++;
}
void get_nxt()
{
    queue<int> q;
    for(int i = 0; i < 26; i++)
        if(trie[0][i] != 0) q.push(trie[0][i]);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int k = 0; k < 26; k++)
        {
            if(trie[u][k] == 0) continue;
            int i = trie[u][k], j = nxt[u];
            while(j && trie[j][k] == 0) j = nxt[j];
            if(trie[j][k]) j = trie[j][k];
            nxt[i] = j;
            q.push(i);
        }
    }
}
void ac(string str)
{
    for(int i = 0; j = 0; i < str.size(); i++)
    {
        int v = str[i] - 'a';
        while(j && trie[j][v] == 0) j = nxt[j];
        if(trie[j][v] != 0) j = trie[j][v];
        int p = j;
        //次数是为了同时识别sher、he这类的单词
        while(p)
        {
            if(cnt[p])
                cout<<"输出识别到的字符串"<<endl;
            p = nxt[p];
        }
    }
}

线段树

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
//区间修改查询的利器
int a[n + 1];
int tree[n * 4 + 1];
int tag[n * 4 + 1];
void pushdown(int p, int l, int r)
{
    int mid = l + r >> 1;
    tag[p * 2] += tag[p];
    tag[p * 2 + 1] += tag[p];
    tree[p * 2] += tag[p] * (mid - l + 1);
    tree[p * 2 + 1] += tag[p] * (r - mid);
    tag[p] = 0;
}
void pushup(int p)
{
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
}
void build(int p, int l, int r)
{
    if(l == r)
    {
        tree[p] = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    pushup(p);
}
void update(int val, int ql, int qr, int p, int l, int r)
{
    if(ql <= l && r <= qr)
    {
        tag[p] += val;
        tree[p] += val * (r - l + 1);
        return;
    }
    int mid = l + r >> 1;
    pushdown(p, l, r);
    if(ql <= mid)
        update(val, ql, qr, p * 2, l, mid);
    if(mid < qr)
        update(val, qr, qr, p * 2 + 1, mid + 1, r);
    pushup(p);
}
int query(int ql, int qr, int p, int l, int r)
{
    if(ql <= l && r <= qr) return tree[p];
    int res = 0;
    int mid = l + r >> 1;
    pushdown(p);
    if(ql <= mid)
        res += query(ql, qr, p * 2, l, mid);
    if(mid < qr)
        res += query(ql, qr, p * 2 + 1, mid + 1, r);
    return res;
}

图论

建图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//用数组模拟邻接表，同样的方法可以模拟链表
//注意无向边的m的数量要乘2
int h[n + 1];
int e[m + 1], w[m + 1], nxt[m + 1], tot;
void init()
{
    memset(h, -1, sizeof h);
}
//从u到v添加一条权值为val的单向边
void add_edge(int u, int v, int val)
{
    e[tot] = v;
    w[tot] = val;
    nxt[tot] = h[u];
    h[u] = tot++;
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//有向无环图才可以使用
int h[n + 1], d[n + 1];
int e[m + 1], w[m + 1], nxt[m + 1], tot;
void top_sort()
{
    queue<int> q;
    for(int i = 1; i <= n; i++)
        if(d[i] == 0) q.push(i);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = h[u]; i != -1; i = nxt[i])
        {
            int v = e[i];
            if(--d[v] == 0) q.push(v);
        }
    }
}

单源最短路

spfa

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
bool vis[n + 1];
int h[n + 1], dist[n + 1], inv[n + 1];
int e[m + 1], w[m + 1], nxt[m + 1], tot;
void add(int u, int v, int val)
{
    e[tot] = v;
    w[tot] = val;
    nxt[tot] = h[u];
    h[u] = tot++;
}
void spfa(int s)
{
    memset(dist, 0x3f, sizeof dist);
    d[s] = 0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = h[u]; i != -1; i = nxt[i])
        {
            int v = e[i];
            if(dist[v] > dist[u] + w[i])
            {
                inv[v] = inv[u] + 1;
                if(inv[v] >= n) 
                {
                    cout<<"存在负环"<<endl;
                    return;
                }
                dist[v] = dist[u] + w[i];
                if(!vis[v]) q.push(v), vis[v] = true;
            }
        }
    }
}

dijkstra(朴素)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool vis[n + 1];
int dist[n + 1], G[n + 1][n + 1];
void dijkstra(int s)
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    for(int i = 1; i <= n; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; i++)
            if(vis[j] == false && (t == -1 || dist[j] < dist[t])) t = j;
        vis[t] = true;
        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + G[t][j]);
    }
}

dijkstra(堆优化)

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
typedef pair<int, int> pii;
bool vis[n + 1];
int h[n + 1], dist[n + 1];
int e[m + 1], w[m + 1], nxt[m + 1], tot;
void add(int u, int v, int val)
{
    e[tot] = v;
    w[tot] = val;
    nxt[tot] = h[u];
    h[u] = tot++;
}
void dijkstra(int s)
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    prioritty_queue<pii, vector<pii>, greater<pii>> q;
    q.push({dist[s], s});
    while(!q.empty())
    {
        int u = q.front().second;
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = h[u]; i != -1; i = nxt[i])
        {
            int v = e[i];
            if(dist[v] > dist[u] + w[i])
            {
                dist[v] = dist[u] + w[i];
                q.push({dist[v], v});
            }
        }
    }
}

多源最短路

1
2
3
4
5
6
7
8
int dist[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++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

最小生成树

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
struct Edge
{
    int u, v, w;
    bool operator < (const Edge & x) const
    {
        return w < x.w;
    }
}edges[m + 1];
int fa[n + 1];
void init()
{
    for(int i = 1; i <= n; i++) fa[i] = i;
}
int find(x)
{
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
void merge(int u, int v)
{
    u = find(u);
    v = find(v);
    fa[x] = v;
}
int kruskal()
{
    int res = 0;
    init();
    sort(edges + 1, edges + m + 1);
    for(int i = 1; i <= m; i++)
    {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        if(find(u) != find(v))
        {
            merge(u, v);
            res += w;
        }
    }
    return res;
}

最近公共祖先

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
int h[n + 1];
int e[m + 1], w[m + 1], nxt[m + 1], tot;
int dep[n + 1], f[n + 1][k];//k = log2n
void add_edge(int u, int v, int val)
{
    e[tot] = v;
    w[tot] = val;
    nxt[tot] = h[u];
    h[u] = tot++;
}
//dep[root] = 0;
void dfs(int u, int fa)
{
    f[u][0] = fa;
    for(int k = 1; k <= 30; k++)
        f[u][k] = f[f[u][k - 1]][k - 1];
    for(int i = h[u]; i != -1; i = nxt[i])
    {
        int v = e[i];
        if(v == fa) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}
int lca(int u, int v)
{
    if(dep[u] > dep[v])
        swap(u, v);
    int d = dep[v] - dep[u];
    for(int k = 0; k <= 30; k++)
        if(d >> k & 1) v = f[v][k];
    if(u == v) return u;
    for(int k = 30; k >= 0; k--)
    {
        if(f[u][k] != f[v][k])
            u = f[u][k], v = f[v][k];
    }
    return f[u][0];
}

二分图

染色法判定二分图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int h[n + 1], col[n + 1];
int e[m + 1], nxt[m + 1], tot;
void add_edge(int u, int v, int val)
{
    e[tot] = v;
    w[tot] = val;
    nxt[tot] = h[u];
    h[u] = tot++;
}
bool check(int u, int color)
{
    if(col[u] != 0) 
        return col[u] == color;
    col[u] = color;
    for(int i = h[u]; i != -1; i = nxt[i])
    {
        int v = e[i];
        if(!check(v, 3 - color))
            return false;
    }
    return true;
}

二分图匹配

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
bool vis[n + 1]
int h[n + 1], match[n + 1];
int e[m + 1], nxt[m + 1], tot;
void add_edge(int u, int v, int val)
{
    e[tot] = v;
    w[tot] = val;
    nxt[tot] = h[u];
    h[u] = tot++;
}
bool find(int u)
{
    for(int i = h[u]; i != -1; i = nxt[i])
    {
        int v = e[i];
        if(vis[v]) continue;
        vis[v] = true;
        if(match[v] == 0 || find(match[v]))
        {
            match[v] = u;
            return true;
        }
    }
    return false;
}
int Hungarian()
{
    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof vis);
        if(find(i)) res++;
    }
    return res;
}

二分图的最小点覆盖

定义：找到数量最小的点集，使得每一条边都至少有一个边包含在点集中

二分图的最大匹配数 = 二分图的最小点覆盖数

二分图的最大独立集

定义：找到数量最多的点集，使得点集中的任意连点之间没有边相连

二分图的最大独立集 = 二分图的顶点数 - 二分图的最小点覆盖

tarjan

有向图的联通分量

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
int h[n + 1];
int e[m + 1], nxt[m + 1], tot;
int dfn[n + 1], low[n + 1], dfn_cnt;
int stk[n + 1], top;
bool in_stk[n + 1];
int idx[n + 1], scc_cnt;
void add_edge(int u, int v)
{
    e[tot] = v;
    nxt[tot] = h[u];
    h[u] = tot++;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++dfn_cnt;
    stk[++top] = u, in_stk[u] = true;
    for(int i = h[u]; i != -1; i = nxt[i])
    {
        int v = e[i];
        if(dfn[v] == 0) 
        {
            tarjan(v);
            low[u] = min(low[u], low[v]); 
        }
        else if(in_stk[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        int x;
        scc_cnt++;
        do
        {
            x = stk[top--];
            dix[x] = scc_cnt;
            in_stk[x] = false;
        }
        while(x != u);
    }
}

无向图

割点

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 h[n + 1];
int e[m + 1], nxt[m + 1], tot;
int dfn[n + 1], low[n + 1], dfn_cnt;
bool cut[n + 1]; 
int root;
void add_edge(int u, int v)
{
    e[tot] = v;
    nxt[tot] = h[u];
    h[u] = tot++;
}
void tarjan(int u)
{
    int cnt = 0;
    dfn[u] = low[u] = ++dfn_cnt;
    for(int i = h[u]; i != -1; i = nxt[i])
    {
        int v = e[i];
        if(dfn[v] == 0)
        {
            cnt++;
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(dfn[u] <= low[v] && (u != root || cnt > 1)) cut[u] = true;
        }
        else
            low[u] = min(low[u], dfn[v]);
    }
}

桥

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 h[n + 1];
int e[m + 1], nxt[m + 1], tot;
int dfn[n + 1], low[n + 1], dfn_cnt;
bool cut[m + 1];
void add_edge(int u, int v)
{
    e[tot] = v;
    nxt[tot] = h[u];
    h[u] = tot++;
}
void tarjan(int u, int from)
{
    dfn[u] = low[u] = ++dfn_cnt;
    for(int i = h[u]; i != -1; i = nxt[i])
    {
        int v = e[i];
        if(dfn[v] == 0)
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(dfn[u] < low[v])
                cut[i] = true, cut[i ^ 1] = true;
        }
        else if(i ^ 1 != from)
            low[u] = min(low[u], dfn[v]);
    }
}

数学

质数

质数判定

1
2
3
4
5
6
bool check(int n)
{
    for(int i = 2; i <= n / i; i++)
        if(n % i == 0) return false;
    return true;
}

分解质因数

1
2
3
4
5
6
7
8
9
10
11
void div(int n)
{
    for(int i = 2; i <= n / i; i++)
    {
        int s = 0;
        while(n % i == 0) s++, n /= i;
        if(s) cout<<i<<" "s<<endl;
    }
    if(n > 1)
        cout<<n<<" "<<1<<endl;
}

质数筛

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
//埃氏筛
bool vis[n + 1];
int primes[n + 1], cnt;
void get_primes1(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i])
        {
            primes[cnt++] = i;
            for(long long j = i * i; j <= n; j += i)
            {
                vis[j] = true;
            }
        }
    }
}
//欧拉筛
bool vis[n + 1];
int primes[n + 1], cnt;
void get_primes2(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i]) 
            primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++)
        {
            vis[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

约数

求约数

1
2
3
4
5
6
7
8
9
10
11
12
void div(int n)
{
    for(int i = 2; i <= n / i; i++)
    {
        if(n % i == 0)
        {
            cout<<i<<" ";
            if(i != n / i)
                cout<<n / i<<" ";
        }
    }
}

约数个数

1
2
3
4
5
6
7
8
9
10
11
12
13
//枚举每种质因子的个数，然后用乘法原理计算
int get_div_nums(int n)
{
    int res = 1;
    for(int i = 2; i <= n / i; i++)
    {
        int s = 0;
        while(n % i == 0) s++, n /= i;
        if(s) res *= (s + 1);
    }
    if(n > 1) res *= 2;
    return res;
}

约数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//将各个约数拆成质因子相乘的形式，再整理得到
int get_div_sum(int n)
{
    int res = 1;
    map<int, int> cnt;
    for(int i = 2; i <= n / i; i++)
    {
        int s = 0;
        while(n % i == 0) s++, n /= i;
        if(s) cnt[i] = s;
    }
    if(n > 1) cnt[n] = 1;
    for(auto i : cnt)
    {
        int t = 1;
        while(i.second--)
            t = t * i.first + 1;
        res *= t;
    }
    return res;
}

gcd与exgcd

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 gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
/*
a * x + b * y = d
b * x1 + a % b * y1 = d
b * x1 + (a - a / b * b) * y1 = d
b * x1 + a * y1 - a / b * b * y1 = d
a * y1 + b * (x1 - a / b * y1) = d
x = y1, y = x1 - a / b * y1
*/
int exgcd(int a, int &x, int b, int &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgce(b, y, a % b, x);
    y -= a / b * x;
    return d;
}
//设最后得到解是x0，y0
/*
通解为
x = x0 + k * b / d
y = y0 - k * a / d
*/

同余与逆元

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
//若模数为质数, 则a的p - 2次方是a模p情况下的逆元
//a在模p情况下的逆元为ksm(a, p - 2, p)
int ksm(int a, int b, int mod)
{
    int res = 1;
    while(b)
    {
        if(b & 1)
            res = 1ll * res * a;
        a = 1ll * a * a;
        b >>= 1;
    }
    return res;
}
//若模数不为质数，则a必须与模数互质否则没有逆元
//可将其写成a * x + m * y = 1
//a在模p情况下的逆元为x
int exgcd(int a, int &x, int b, int y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, y, a % b, x);
    y -= a / b * x;
    return d;
}

欧拉函数

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 fh(int n)
{
    int res = n;
    for(int i = 2; i <= n / i; i++)
    {
        int s = 0;
        while(n % i == 0) n /= i, s++;
        if(s) res = res / i * (i - 1);
    }
    if(n > 1) res = res / n * (n - 1);
    return res;
}
//求1~n所有数的欧拉函数
int fh[n + 1];
bool vis[n + 1];
int primes[n + 1], cnt++;
void get_fhs(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i])
        {
            fh[i] = i - 1;
            primes[cnt++] = i;
        }
        for(int j = 0; primes[j] <= n / i; j++)
        {
            vis[i * primes[j]] = true;
            if(i % primes[j] == 0)
            {
                fh[i * primes[j]] = fh[i] * primes[j];
                break;
            }
            fh[i * primes[j]] = fh[i] * (primes[j] - 1);
        }
    }
}

动态规划

对于动态规划，介绍一点以下类型中的经典题目

线性dp

子序列

上升与下降同理，这里只介绍上升

最长上升子序列

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
//第一种做法
int a[n + 1];
int f[n + 1];//f[i]表示以i为结尾的最长上升子序列长度
for(int i = 1; i <= n; i++)
{
    f[i] = 1;
    for(int j = 1; j < i; j++)
        if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
}
//第二种做法
int a[n + 1];
int f[n + 1];//f[i]表示长度为i的上升子序列最后一个元素的值
memset(f, 0x3f, sizeof f);
for(int i = 1; i <= n; i++)
{
    int l = 1, r = n;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(f[mid] >= mid) r = mid;
        else l = mid + 1;
    }
    f[l] = a[i];
}

最长公共子序列

1
2
3
4
5
6
7
8
9
int a[n + 1];
int b[m + 1];
int f[n + 1][m + 1];//f[i][j]表示a前i个数与b前j个数构成的最长公共子序列长度
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
    {
        f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
    }

最长公共上升子序列

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 a[n + 1];
int b[m + 1];
int f[n + 1][m + 1];
//f[i][j]表示a前i个数与b前j个数，且以b[j]为结尾的最长公共上升子序列长度
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
    {
        f[i][j] = f[i - 1][j];
        if(a[i] == b[j])
        {
            f[i][j] = max(f[i][j], 1);
            for(int k = 1; k < j; k++)
                if(b[k] < b[j])
                    f[i][j] = max(f[i][j], f[i - 1][k] + 1);
        }
    }
//对代码进行等价变形优化
//注意到第三层循环处，f[i][j]的结果只与i-1有关，且b[k] < b[j] == a[i]
for(int i = 1; i <= n; i++)
{
    int maxv = 0;
    for(int j = 1; j <= m; j++)
    {
        f[i][j] = f[i - 1][j];
        if(a[i] == b[j]) f[i][j] = max(f[i][j], maxv + 1);
        if(b[j] < a[i]) maxv = max(maxv, f[i - 1][j]);
    }
}

背包

01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//v表示体积，w表示重量
int v[n + 1], w[n + 1];
int f[n + 1][m + 1];//f[i][j]表示用前i件物品用j大小空间来装进的最大重量
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] >= 0)
            f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }
//将第二层代码逆序，等价变形优化
int f[m + 1];
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]);

完全背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//v表示体积，w表示重量
int v[n + 1], w[n + 1];
int f[n + 1][m + 1];//f[i][j]表示用前i件物品用j大小空间来装进的最大重量
for(int i = 1; i <= n; i++)
    for(int j = 0; j <= m; j++)
    {
        f[i][j] = f[i - 1][j];
        for(int k = 1; j - k * v[i] >= 0; k++)
            f[i][j] = min(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    }
//等价变形优化
// f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i], f[i - 1][j - 2 * v[i]] + 2 * w[i], ..., f[i][j % v[i]] + (j / v[i]) * w[i]);
//f[i][j - v[i]] + w[i] = max(f[i - 1][j - v[i]] + w[i], f[i - 1][j - 2 * v[i]] + 2 * w[i], ..., f[i][j % v[i]] + (j / v[i]) * w[i]);
for(int i = 1; i <= n; i++)
    for(int j = v[i]; j <= m; j++)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

多重背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int f[n + 1][m + 1];//f[i][j]表示用前i件物品用j大小空间来装进的最大重量
int v[n + 1], w[n + 1], cnt[n + 1];
for(int i = 1; i <= n; i++)
    for(int j = 0; j <= m; j++)
    {
        f[i][j] = f[i - 1][j];
        for(int k = 1; k <= cnt[i]; k++)
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    }
//因为数量有限制没法保证一定会考虑到j % v[i]的情况所以无法使用完全背包的优化方式
//可以将一个整数进行二进制拆分，比如11拆分成1 2 4 3就可以用这四种数来拼凑成0~11所以的数
int f[m + 1];
for(int i = 1; i <= n; i++)
    for(int k = 1; cnt[i] > 0; k <<= 1)
    {
        cnt[i] -= min(cnt[i], k);
        for(int j = m; j >= k * v[i]; j--)
            f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
    }

分组背包

1
2
3
4
5
6
7
8
int cnt[n + 1];
int v[n + 1][n + 1],  w[n + 1][n + 1];
int f[m + 1];
for(int i = 1; i <= n; i++)//枚举物品组
    for(int j = m; j >= 0; j--)
        for(int k = 0; k < cnt[i]; k++)
            if(j - v[i][k] >= 0)
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

用背包来求解方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//情况1
//给定一堆不同的数字(每种可以取一次)，求组成目标数字的方案
int v[n + 1];
int f[m + 1];
f[0] = 1;
for(int i = 1; i <= n; i++)
    for(int j = m; j >= v[i]; j--)
        f[j] += f[j - v[i]];
//情况2
//给定一堆不同的数字(每种可以取无数次)，求组成目标数字的方案
int v[n + 1];
int f[m + 1];
f[0] = 1;
for(int i = 1; i <= n; i++)
    for(int j = v[i]; j <= m; j++)
        f[j] += f[j - v[i]];

划分数

1
2
3
4
5
6
//将n分解成m组，求不同的分解方案(该解法与背包无关)
int f[n + 1][m + 1];
f[0][0] = 1;
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= i; j++)
        f[i][j] = f[i - 1][j - 1] + f[i - j][j];

区间dp

例题：
282. 石子合并 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 305;
int n, a[maxn], f[maxn][maxn];
int main()
{   
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int i = 1; i <= n; i++) a[i] += a[i - 1];
    memset(f, 0x3f, sizeof f);
    for(int i = 1; i <= n; i++) f[i][i] = 0;
    for(int len = 2; len <= n; len++)
        for(int l = 1; l + len - 1 <= n; l++)
            for(int k = l; k <= l + len - 1; k++)
                f[l][l + len - 1] = min(f[l][l + len - 1], f[l][k] + f[k + 1][l + len - 1] + a[l + len - 1] - a[l - 1]);
    cout<<f[1][n]<<endl;
    return 0;
}

状态压缩dp

例题：
91. 最短Hamilton路径 - AcWing题库

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
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 20;
int n, w[maxn][maxn], f[1 << maxn][maxn];
int main()
{
    cin>>n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin>>w[i][j];
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for(int i = 0; i < 1 << n; i++)
        for(int j = 0; j < n; j++)
            if(i >> j & 1)
            {
                for(int k = 0; k < n; k++)
                    if(i >> k & 1)
                    {
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                    }
            }
    cout<<f[(1 << n) - 1][n - 1]<<endl;
    return 0;
}

树形dp

例题：
AcWing 285. 没有上司的舞会 - AcWing

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
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 6005;
bool vis[maxn];
int n, w[maxn], f[maxn][2];
int h[maxn], e[maxn], nxt[maxn], tot;
void addE(int u, int v)
{
    ++tot;
    e[tot] = v;
    nxt[tot] = h[u];
    h[u] = tot;
}
void dfs(int u)
{
    f[u][1] = w[u];
    for(int i = h[u]; i; i = nxt[i])
    {
        int j = e[i];
        dfs(j);
        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
}
int main()
{
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>w[i];
    for(int i = 1; i < n; i++)
    {
        int l, k;
        cin>>l>>k;
        addE(k, l);
        vis[l] = true;
    }
    int root = 0;
    while(vis[++root]);
    // cout<<root<<endl;
    dfs(root);
    cout<<max(f[root][0], f[root][1])<<endl;
    return 0;
}

数位dp

例题：
[P2657 SCOI2009] windy 数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
#include<vector>
#include<iostream>
using namespace std;
int l, r, f[35][10];
void init()
{
    for(int i = 0; i <= 9; i++) f[1][i] = 1;
    for(int i = 2; i < 35; i++)
        for(int j = 0; j <= 9; j++)
            for(int k = 0; k <= 9; k++)
                if(abs(j - k) >= 2)
                    f[i][j] += f[i - 1][k];
}
int dp(int n)
{
    if(!n) return 0;
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;
    int res = 0;
    int last = -2;
    for(int i = nums.size() - 1; i >= 0; i--)
    {
        int x = nums[i];
        if(x)
        {
            //最高位不能填0，枚举这一位填什么
            for(int j = i == nums.size() - 1; j < x; j++) 
                if(abs(last - j) >= 2) res += f[i + 1][j];
        }
        if(abs(last - x) < 2) break;
        last = x;
        if(!i) res++;
    }
    //特殊处理最高位之后的带前导零的情况
    for(int i = nums.size() - 2; i >= 0; i--)
        for(int j = 1; j <= 9; j++)
            res += f[i + 1][j];
    return res;
}
int main()
{
    init();
    cin>>l>>r;
    cout<<dp(r) - dp(l - 1)<<endl;
    return 0;
}
#Data structures and algorithms
数据结构与算法
http://example.com/2022/07/03/数据结构与算法/
作者
Eotdawn
发布于
2022年7月3日
许可协议