c++算法竞赛常用板子集合(持续更新)

前言

本文主要包含算法竞赛一些常用的板子,码风可能不是太好,还请见谅。

后续会继续补充没有的板子。当然我太菜了有些可能写不出来T^T

稍微有些分类但不多,原谅我QwQ

建议 Ctrl + F 以快速查找板子。

常用板子

树状数组

此处为查询区间和的树状数组。

int bit[500010];
void add(int k, int x) {
    while (k 

线段树

此处为区间修改区间查询区间和的线段树。

struct SegmentTree {
    ll sum[N > 1;
        build(rt 

不是吧真有人手写堆吗

ll q[N], cnt;
void pushup(int id) {
    while (id > 1) {
        if (q[id] >= q[id >> 1]) break;
        swap(q[id], q[id >> 1]);
        id >>= 1;
    }
}
void movedown() {
    int id = 1;
    while (id  q[id 

并查集

struct Disjoint_Set {
    int p[N], size[N];
    void build() {
        for (int i = 1; i  size[y]) swap(x, y);
        p[x] = y;
        size[y] += size[x];
    }
    bool check(int x, int y) {
        x = root(x), y = root(y);
        return x == y;
    }
} a;

ST表

代码实现查询区间 ([l, r]) 的区间最大值

for (int i = 1; i 

边链表

const int N = 100010;
int last[N], cnt;
struct edge {
    int to, next, w;
} e[N 

LCA

此处贴的是 Tarjan法 求LCA。更多方法

struct Disjoint_Set {
    int p[N], size[N];
    void build() {
        for (int i = 1; i  size[y]) swap(x, y);
        p[x] = y;
        size[y] += size[x];
    }
    bool check(int x, int y) {
        x = root(x), y = root(y);
        return x == y;
    }
} a;
int last[N], cnt;
struct edge {
    int to, next;
} e[N  g[N];
int p[N];
bool vis[N];
int r[N];
void dfs(int x, int f) {
    p[x] = f;
    for (int i = last[x]; i; i = e[i].next) {
        int v = e[i].to;
        if (v == f) continue;
        vis[v] = 1;
        for (int j : g[v]) {
            int o = ask[j].x;
            if (o == v) o = ask[j].y;
            if (!vis[o]) continue;
            ask[j].ans = r[a.root(o)]; 
        }
        dfs(v, x);
        a.merge(x, v);
        r[a.root(x)] = x;
    }
}

单源最短路(Dijkstra)

这里是堆优化版呢。笑了有些时候堆优化还没不优化好

void dij(int s) {
    priority_queue , greater > q; 
    memset(dis, 0x7f7f7f7f, sizeof(dis));
    q.push({0, s});
    dis[s] = 0;
    while (!q.empty()) {
        pii u = q.top(); q.pop();
        int pos = u.second;
        if (vis[pos]) continue;
        vis[pos] = 1;
        for (int j = last[pos]; j; j = e[j].next) {
            int v = e[j].to;
            if (vis[v]) continue;
            if (dis[pos] + e[j].w 

缩点

其中 (p) 为缩点后的新点。

int dfn[N], low[N], dcnt;
bool instack[N];
stack  s;
int p[N], h[N];
void dfs(int x, int f) {
    instack[x] = 1;
    s.push(x);
    dfn[x] = low[x] = ++dcnt;
    for (int i = last[0][x]; i; i = e[0][i].next) {
        int v = e[0][i].to;
        if (dfn[v]) {
            if (instack[v]) low[x] = min(low[x], dfn[v]);
            continue;
        }
        dfs(v, x);
        low[x] = min(low[x], low[v]);
    }
    if (low[x] >= dfn[x]) {
        p[x] = x, h[x] = a[x], instack[x] = 0;
        while (s.top() != x) {
            p[s.top()] = x;
            h[x] += a[s.top()];
            instack[s.top()] = 0;
            s.pop();
        }
        s.pop();
    }
}

欧拉路径

int st[N], ed[N];
struct edge {
    int u, v;
} e[N 

乘法逆元

fac[0] = fac[1] = 1;
for (int i = 2; i 

快速幂

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

矩阵快速幂

不是我说这写的是真的丑,凑活着看吧QAQ

struct sq {
    ll x[110][110];
    void build() {
        for (int i = 1; i >= 1;
    }
}

线性基

(p) 数组表示基底,(x) 为添加进的数字。

int p[N];
void add(ll x) {
    for (int i = N; i >= 0; i--) {
        if (!(x & (1ll 

线性筛

int prime[6000010], cnt;
bool isprime[N + 10];
void prim() {
    isprime[0] = isprime[1] = 1;
    for (int i = 2; i 

字符串哈希

int Char(char c) {
    if (c >= '0' && c = 'a' && c = 'A' && c  mp;

cin >> s;
ll x = 0;
for (int i = 0; i 

KMP

(s)(t) 为需要匹配的两个 char 类型数组。

(border_i) 表示 (t) 长度为 (i) 的前缀最长的 (border) 长度。

完了border是啥来着?

ls = strlen(s + 1), lt = strlen(t + 1);
int j = 0;
for (int i = 2; i = 1 && t[j + 1] != t[i]) j = border[j];
    if (t[j + 1] == t[i]) j++;
    border[i] = j;
}
int sx = 1, tx = 0;
while (sx = 1 && s[sx] != t[tx + 1]) tx = border[tx];
    if (t[tx + 1] == s[sx]) tx++;
    if (tx == lt) printf("%dn", sx - lt + 1);
    sx++;
}

AC自动机

struct Trie {
    int id[27], cnt, fail;
} t[N];
void Build(string &s) {
    int now = 0;
    for (int i = 0; i  q;
    for (int i = 0; i 

文章来源于互联网:c++算法竞赛常用板子集合(持续更新)

THE END
分享
二维码