code-book

預設模板

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>

2D Prefix Sum

int row, col;
while (cin >> row >> col) {
    vector<vector<int>> v(row+1, vector<int>(col+1));
    for (int i = 1, tmp; i <= row; i++) for (int j = 1; j <= col; j++) {
        cin >> v[i][j];
        v[i][j] += v[i-1][j] - v[i-1][j-1] + v[i][j-1];
    }
    int sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;
    cout << v[ex][ey]-v[ex][sy-1]-v[sx-1][ey]+v[sx-1][sy-1] << '\n';
}

Union-Find

vector<int> par(N), sz(N, 1); // N 為節點總數
int Find(int x) { return par[x] == x ? x : par[x] = Find(par[x]); }
void Union(int x, int y) {
    x = Find(x); y = Find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    par[y] = x; sz[x] += sz[y]; sz[y] = 0;
}
int getSize(int x) { return sz[Find(x)]; }

// iota(all(par), 0);

BIT (Fenwick Tree)

vector<int> v, bit;
int n;
void add(int x, int val) { for (; x <= n; x += x&-x) bit[x] += val; }
int query(int x) { 
    int sum = 0;
    for (; x > 0; x -= x&-x) sum += bit[x];
    return sum;
}
int main() {
    int a, b; cin >> n >> a >> b;
    v.resize(n);
    for (auto &i : v) cin >> i;
    bit.assign(n+1, 0);
    for (int i = 0; i< n; i++) add(i+1, v[i]);
    cout << query(b) - query(a-1);
}

線段樹

struct SegmentTree {
    int n;
    vector<int> sumTree, mxTree, mnTree, lazy;
    // 初始化
    SegmentTree(int _n): n(_n) {
        sumTree.assign(4*n, 0);
        mxTree.assign(4*n, LLONG_MIN/2);
        mnTree.assign(4*n, LLONG_MAX/2);
        lazy.assign(4*n, 0);
    }
    // 建樹
    void build(int idx, int l, int r, const vector<int>& v) {
        if (l == r) {
            sumTree[idx] = mxTree[idx] = mnTree[idx] = v[l];
            return;
        }
        int m = (l + r) >> 1;
        build(idx<<1, l, m, v);
        build(idx<<1|1, m+1, r, v);
        pull(idx);
    }
    // 合併
    void pull(int idx) {
        sumTree[idx] = sumTree[idx<<1] + sumTree[idx<<1|1];
        mxTree[idx]  = max(mxTree[idx<<1], mxTree[idx<<1|1]);
        mnTree[idx]  = min(mnTree[idx<<1], mnTree[idx<<1|1]);
    }
    // 下傳懶標記
    void push(int idx, int l, int r) {
        if (!lazy[idx]) return;
        int m = (l + r) >> 1;
        apply(idx<<1,     l,   m, lazy[idx]);
        apply(idx<<1|1, m+1,   r, lazy[idx]);
        lazy[idx] = 0;
    }
    // 套用標記到節點
    void apply(int idx, int l, int r, int val) {
        sumTree[idx] += val * (r - l + 1);
        mxTree[idx]  += val;
        mnTree[idx]  += val;
        lazy[idx]    += val;
    }
    // 區間加值更新 [L, R]
    void update(int idx, int l, int r, int L, int R, int val) {
        if (L <= l && r <= R) {
            apply(idx, l, r, val);
            return;
        }
        push(idx, l, r);
        int m = (l + r) >> 1;
        if (L <= m) update(idx<<1, l, m, L, R, val);
        if (R >  m) update(idx<<1|1, m+1, r, L, R, val);
        pull(idx);
    }
    // 區間總和查詢 [L, R]
    int querySum(int idx, int l, int r, int L, int R) {
        if (L <= l && r <= R) return sumTree[idx];
        push(idx, l, r);
        int m = (l + r) >> 1;
        int res = 0;
        if (L <= m) res += querySum(idx<<1, l, m, L, R);
        if (R >  m) res += querySum(idx<<1|1, m+1, r, L, R);
        return res;
    }
    // 區間最大值查詢 [L, R]
    int queryMax(int idx, int l, int r, int L, int R) {
        if (L <= l && r <= R) return mxTree[idx];
        push(idx, l, r);
        int m = (l + r) >> 1;
        int res = LLONG_MIN/2;
        if (L <= m) res = max(res, queryMax(idx<<1, l, m, L, R));
        if (R >  m) res = max(res, queryMax(idx<<1|1, m+1, r, L, R));
        return res;
    }
    // 區間最小值查詢 [L, R]
    int queryMin(int idx, int l, int r, int L, int R) {
        if (L <= l && r <= R) return mnTree[idx];
        push(idx, l, r);
        int m = (l + r) >> 1;
        int res = LLONG_MAX/2;
        if (L <= m) res = min(res, queryMin(idx<<1, l, m, L, R));
        if (R >  m) res = min(res, queryMin(idx<<1|1, m+1, r, L, R));
        return res;
    }
};

signed main() { WA();
    int n, q; cin >> n >> q;
    vector<int> v(n+1);
    for (int i = 1; i <= n; i++) cin >> v[i];
    SegmentTree st(n);
    st.build(1, 1, n, v);
    while (q--) {
        int type, a, b, k;
        cin >> type >> a >> b;
        if (type == 1) { // 區間加值
            cin >> k;
            st.update(1, 1, n, a, b, k);
        }
        else if (type == 2) cout << st.querySum(1, 1, n, a, b) << '\n';
        else if (type == 3) cout << st.queryMax(1, 1, n, a, b) << '\n';
        else if (type == 4) cout << st.queryMin(1, 1, n, a, b) << '\n';
    }
}

String

KMP

vector<int> build_lps(const string &s) {
    int n = s.size();
    vector<int> lps(n);
    lps[0] = 0;
    for (int i = 1, len = 0; i < n; ) {
        if (s[i] == s[len]) lps[i++] = ++len;
        else if (len) len = lps[len-1];
        else lps[i++] = 0;
    }
    return lps;
}
int kmp_search(string &text, string &pattern) {
    auto lps = build_lps(pattern);
    int i = 0, j = 0;
    while (i < text.size()) {
        if (text[i] == pattern[j]) {
            i++; j++;
            if (j == pattern.size()) return i - j; // match at i-j
        }
        else if (j) j = lps[j-1];
        else i++;
    }
    return -1; // not found
}

Trie

struct Node {
    unordered_map<char, Node*> child;
    bool isWord = false;
};

void insert(Node *p, string s) {
    for (auto c : s) {
        if (!p -> child[c]) p -> child[c] = new Node;
        p = p -> child[c];
    }
    p -> isWord = true;
}

bool search(Node *p, string s) {
    for (auto c : s) {
        if (p -> child[c]) p = p -> child[c];
        else return false;
    }
    return p -> isWord;
}

Node *remove(Node *root, string s, int depth = 0) {
    if (!root) return nullptr;
    if (depth == s.size()) {
        if (root -> isWord) root -> isWord = false;
        if (root -> child.empty()) {
            delete root;
            root = nullptr;
        }
        return root;
    }

    char c = s[depth];
    if (root -> child[c]) {
        root -> child[c] = remove(root -> child[c], s, depth + 1);
        if (root -> child.empty() && !root -> isWord) {
            delete root;
            root = nullptr;
        }
        return root;
    }
    return root;
}

int main() { WA();
    int t;
    for (cin >> t; t; t--) {
        int n;
        Node *root = new Node;
        cin >> n;
        vector<string> v(n);
        for (auto &i : v) cin >> i;
        for (auto i : v) insert(root, i);
    }
}

Graph

Dijkstra

int main() {
    int n, m; cin >> n >> m; // 節點數、邊數
    vector<int> v(n), dis(n, INF);
    vector<vector<PII>> g(n);
    for (auto &i : v) cin >> i;
    while (m--) {
        int a, b, w;
        cin >> a >> b >> w;
        a--; b--;
        g[a].pb({b, w}); g[b].pb({a, w});
    }
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    dis[0] = v[0]; pq.push({v[0], 0}); // 0 為起點
    while (!pq.empty()) {
        auto [d, node] = pq.top(); pq.pop();
        if (d > dis[node]) continue;
        for (auto &[to_idx, to_dis] : g[node])
            if (dis[node] + to_dis < dis[to_idx]) {
                dis[to_idx] = dis[node] + to_dis;
                pq.push({dis[to_idx], to_idx});
            }
    }
    for (int i = 1; i < n; i++) {
        if (dis[i] == INF) cout << "-1 ";
        else cout << dis[i] << ' ';
    }
}

Kruskal

vector<int> anc;
int Find(int x) { return (anc[x] == x ? x : anc[x] = Find(anc[x])); }
bool Union(int a, int b) {
    int fa = Find(a), fb = Find(b);
    if (fa > fb) swap(fa, fb);
    if (fa == fb) return false;
    return anc[fb] = fa, true;
}
anc.resize(n);
iota(all(anc), 0);
g.pb({w, a, b});
sort(all(g));
for (auto &[w, a, b] : g) if (Union(a, b)) ans += w;

Topological-Sorting

int main() {
    int n, m, a, b;
    while (cin >> n >> m) {
        vector<vector<int>> v(n);
        vector<int> w(n), ans;
        while (m--) {
            cin >> a >> b;
            v[--a].pb(--b); w[b]++;
        }
        queue<int> q;
        for (int i = 0; i < n; i++) if (!w[i]) q.push(i);
        while (q.size()) {
            cout << q.front()+1 << ' ';
            for (auto i : v[q.front()]) if (!(--w[i])) q.push(i);
            q.pop();
        }
        cout << '\n';
    }
}

LCA

vector<vector<int>> v, par;
vector<int> dep;
void dfs(int x, int u) {
    par[0][x] = u;
    for (auto &i : v[x]) {
        if (i == u) continue;
        dep[i] = dep[x]+1; dfs(i, x);
    }
}
int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = 19; i >= 0; i--) if (dep[par[i][a]] >= dep[b]) a = par[i][a];
    if (a == b) return a;
    for (int i = 19; i >= 0; i--) if (par[i][a] != par[i][b])
        a = par[i][a], b = par[i][b];
    return par[0][a];
}
signed main() { WA();
    int n, q; cin >> n >> q;
    v.resize(n+1);
    for (int i = 2; i <= n; i++) {
        int k; cin >> k;
        v[i].pb(k); v[k].pb(i);
    }
    par.resize(20, vector<int>(n+1));
    dep.resize(n+1);
    dfs(1, 1); // 從根結點開始建深度表
    for (int i = 1; i < 20; i++) for (int j = 1; j <= n; j++)
        par[i][j] = par[i-1][par[i-1][j]];
    while (q--) {
        int a, b; cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
}

Maximum Flow (Edmonds-Karp)

int n, s, e, t, a, b, w;
vector<vector<int>> g;
vector<int> vis, par;
bool BFS() {
    queue<int> q;
    vis.assign(n+1, 0); par.assign(n+1, 0);
    q.push(s); vis[s] = 1;
    while (q.size()) {
        int now = q.front(); q.pop();
        if (now == e) return true;
        for (int i = 1; i <= n; i++) if (g[now][i] && !vis[i]) {
            vis[i] = 1; par[i] = now; q.push(i);
        }
    } return false;
}
signed main() { WA();
    int c = 0;
    while (cin >> n, n) {
        g.assign(n+1, vector<int>(n+1, 0));
        cin >> s >> e >> t;
        while (t--) {
            cin >> a >> b >> w;
            g[a][b] += w; g[b][a] += w;
        }
        int ans = 0;
        while (BFS()) {
            int now = e, mnF = INF;
            while (now != s) {
                mnF = min(mnF, g[par[now]][now]);
                now = par[now];
            }
            now = e;
            while (now != s) {
                g[par[now]][now] -= mnF;
                g[now][par[now]] += mnF;
                now = par[now];
            }
            ans += mnF;
        }
        cout << ans;
    }
}

Number

ext_euc

void ext_euc(int a, int b, int &x, int &y) {
    if (!b) return void(x = 1, y = 0);
    ext_euc(b, a%b, y, x);
    y -= a/b*x;
}

binpow

#define int long long
int f(int x, int y) {
    int sum = 1;
    for (; y; y >>= 1) {
        if (y&1) sum *= x;
        x *= x;
    }
    return sum;
}

矩陣乘法

#define vvi vector<vector<int>>
vvi MaT(vvi a, vvi b) {
    vvi c(a.size(), vector<int>(b[0].size()));
    for (int i = 0; i < a.size(); i++)
        for (int j = 0; j < b[0].size(); j++)
            for (int k = 0; k < b.size(); k++)
                c[i][j] += a[i][k] * b[k][j] % p;
    return c;
}

Prime Sieve

#define MAXN 1000000
int main() {
    vector<int> p(MAXN, 1), ps;
    p[0] = p[1] = 0;
    for (int i = 2; i < MAXN; i++) {
        if (p[i]) ps.pb(i);
        for (auto j : ps) {
            if (i*j >= p.size()) break;
            p[i*j] = 0;
            if (!(i%j)) break;
        }
    }
}

DP

01/Unbounded knapsack

int N, W;
vector<int> wt(N), val(N);
vector<int> dp(W+1, 0);
for (int i = 0; i < N; i++) {
    for (int w = W; w >= wt[i]; w--) // 01，每種物品只能拿一次
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
    for (int w = wt[i]; w <= W; w++) // Unbounded，每種物品可重複拿任意多次
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
}
cout << dp[W];

多重背包

int N, W; // 每種物品最多 cnt[i] 件
vector<int> wt(N), val(N), cnt(N);
vector<int> dp(W+1, 0);

for (int i = 0; i < N; i++) { // 將每個物品拆成若干件 1,2,4,..., 剩餘
    int k = 1, c = cnt[i];
    while (k < c) { // 處理 k 件
        for (int w = W; w >= k * wt[i]; w--)
            dp[w] = max(dp[w], dp[w - k * wt[i]] + k * val[i]);
        c -= k; k <<= 1;
    }
    if (c > 0) for (int w = W; w >= c * wt[i]; w--) // 處理剩餘 c 件
        dp[w] = max(dp[w], dp[w - c * wt[i]] + c * val[i]);
}
cout << dp[W];

稀疏圖：邊較少
稠密圖：邊較多