OI/ACM 模板库

正在准备 CSP 认证，想重温一下模板题，刚好赶上了【不刷洛谷】一周年，于是想着把之前学过的算法全都敲一遍，给自己的信竞生涯画上圆满的句号（不存在的

零、初始化

#include <bits/stdc++.h>
#define cle(x) memset(x,0,sizeof(x))
#define ok cout<<'!'<<endl
#define inf 2147483647
#define ll long long
#define fir first
#define sec second
#define pr pair<int,int>
using namespace std;

int read()
{   int x=0,f=0; char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}

int main()
{
    
    return 0;
}

一、数学

线性筛：

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

const int N = 1e8+10;
int f[N], v[N], n, m;
int main()
{
    std::ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m; // 前 n 个数，m 次查询第 k 小
    v[1] = 1;
    for (int i=2; i<=n; i++) {
        if (!v[i]) f[++f[0]] = i;
        for (int j=1; j<=f[0] && f[j]*i<=n; j++) {
            v[f[j]*i] = 1; if (i%f[j]==0) break;
            // 线性筛算法中，每个数只被最小素因子筛去。
        }
    }
    for (int i=1; i<=m; i++) {
        int p; cin >> p;
        cout << f[p] << '\n';
    }
}

快速幂

// 用以在 log 时间复杂度求膜p意义下的幂
// 常用于求解费马小定理
ll qpow(ll x, ll k, ll p) {
    ll ans = 1;
    for (; k; x = (x*x)%p, k >>= 1) { if (k&1) ans = (ans*x)%p; }
    return ans;
}

乘法逆元

// 除以一个数，等于乘上该数的逆元
// 在膜p意义下，逆元一般可以用费马小定理求解
// 这里提供一个线性求逆元表的递推方法。
#include <iostream>
using namespace std;

const int N = 3e6+1;
ll inv[N], n, p;

int main()
{
    cin >> n >> p; inv[1] = 1;
    for (int i=2; i<=n; i++) 
        inv[i] = (p - (p/i) *inv[p%i] %p) %p;
}

ST 表（RMQ，静态区间查询问题）

// 这里的例子是静态查询区间最小值，O(1)
#include <iostream>
#include <cstring>
#define inf 2147483647
using namespace std;

const int N = 1e5+1;
int n, m, x, y, a[N], lg[N], f[N][20];

int main()
{
    std::ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m; lg[1] = 0;
    for (int i=1; i<=n; i++) cin >> f[i][0];
    for (int i=2; i<=n; i++) lg[i] = lg[i>>1] + 1;
    
    for (int j=1; j<=lg[n]; j++)
        for (int i=1; i<=n-(1<<j)+1; i++) {
            f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
        }
    for (int i=1; i<=m; i++) {
        cin >> x >> y; int l = lg[y-x+1];
        cout << max(f[x][l], f[y-(1<<l)+1][l]) << '\n';
    }
}

二、图论

最小生成树算法（Kruskal）

// 构造一个最小生成树，就是贪心+并查集
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 6e5;
struct ed {
    int x, y, w;
} e[N];
int n, m, k, sum, f[N];

bool cmp(ed a, ed b) { return (a.w < b.w); }
int get(int x) { return (f[x]!=x) ? f[x]=get(f[x]) : f[x]; }
void merge(int x,int y) { int f1=get(x), f2=get(y); f[f1]=f2; }

int main() {
    cin >> n >> m;
    for (int i=1; i<=n; i++) f[i] = i;
    for (int i=1; i<=m; i+) 
        cin >> e[i].x >> e[i].y >> e[i].w;
    
    sort(e+1, e+m+1, cmp);
    for (int i=1; i<=m; i++) {
        int f1 = get(e[i].x), f2 = get(e[i].y);
        if (f1 != f2) {
            k++, sum += e[i].w;
            merge(f1, f2);
        }
        if (k == n-1) break;
    }
    if (k < n-1) cout << "orz\n"; // 图不连通
    else cout << sum << '\n';
}

倍增求LCA（最近公共祖先）

#include <bits/stdc++.h>
using namespace std;
// 这里就会涉及一些存图的知识了
// 一般由两种存储方法，链式存储以及 STL+矩阵存储（本质是前者）
using namespace std;
#define pr pair<int, int>
#define mp make_pair

const int N = 5e5+10;
int n, m, s, f[N][21], d[N], maxd;
vector<int> g[N];

void add(int x,int y)
{  g[x].push_back(y), g[y].push_back(x);  }

void dfs(int u, int fa)
{
    d[u] = d[fa] + 1, f[u][0] = fa;
    maxd = max(maxd, d[u]);
    for (int i=1; (1<<i) <= d[u]; i++) 
        f[u][i] = f[f[u][i-1]][i-1];
    for (int v: g[u]) if (v != fa) dfs(v, u);
}

int lca(int x,int y)
{
    if (d[x] > d[y]) swap(x, y);
    int ln_d = log2(maxd) + 1;
	
	for (int i=ln_d; i>=0; i--) 
		if (d[y]-(1<<i) >= d[x]) y = f[y][i];
	if (x == y) return x;

    for (int i=ln_d; i>=0; i--) 
		if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}

int main()
{
    std::ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> s; 
    for (int i=1,x,y; i<n; i++) cin >> x >> y, add(x,y);
    
    dfs(s, 0);
    for (int i=0,a,b; i<m; i++) 
        cin >> a >> b, cout << lca(a, b) << '\n';
    
}

树剖求LCA（求轻重边）

const int N = 5e5+10;
vector<int> G[N];
int n, m, S, st, d[N], s[N], tp[N], f[N], son[N];
// tp -> 维护重链的顶部
// son -> 维护每个节点的重儿子

void add_edge(int x,int y)
{  G[x].push_back(y), G[y].push_back(x);  }

// dfs1 的目的是求重儿子
void dfs1(int u,int fa)
{
    f[u] = fa, d[u] = d[fa]+1, s[u] = 1;
    for (int v: G[u]) {
        if (v == fa) continue;
        dfs1(v, u); s[u] += s[v];
        if (s[v] > s[son[u]]) son[u] = v;
    }
}

// dfs2 的目的是求 tp 数组
void dfs2(int u, int top)
{
    tp[u] = top;
    for (int v: G[u]) {
        if (v == f[u] || v == son[u]) continue;
        dfs2(v, v);
    }
    // 一般最后处理重儿子，在启发式合并中可以合并到父亲节点
    if (son[u]) dfs2(son[u], top);
}

int main()
{
    cin >> n >> m >> S;
    for (int i=1,x,y; i<n; i++) {
        cin >> x >> y, add_edge(x, y);
    }
    dfs1(S, 0), dfs2(S, S);

    // 让 x 和 y 轮流跳重链，跳 log 次可以跳到一条链上。
    while (m--) {
        int x, y; cin >> x >> y;
        while (tp[x] != tp[y]) {
            if (d[tp[x]] < d[tp[y]]) swap(x, y);
            x = f[tp[x]];
        }
        if (d[x] > d[y]) swap(x, y);
        cout << x << '\n';
    }
    return 0;
}

单源最短路（Dijkstra）

const int N = 2e5+10;
int n, m, s, d[N], vis[N];
vector< pr > g[N];

void dij(int s) {
    memset(d, 0x3f, sizeof(d)); // 初始化最大值
    priority_queue<pr, vector<pr>, greater<pr> > q;
    q.push( mp(0, s) ), d[s] = 0;
    while (!q.empty()) {
        int k = q.top().sec; q.pop();
        if (vis[k]) continue; vis[k] = 1;
        for (auto &i: g[k]) {
            int u = i.fir, w = i.sec;
            if (d[u] > d[k] + w) {
                d[u] = d[k] + w;
                if (!vis[u]) q.push( mp(d[u],u) );
    }   }   }
}

int main() 
{
	cin >> n >> m >> s;
    for (int i=0,u,v,w; i<m; i++) {
        cin >> u >> v >> w;
        g[u].push_back( mp(v,w) ); // 有向图
    }   dij(s);
    for (int i=1; i<=n; i++) cout << d[i] << " ";
    return 0;
}

判负环（SPFA）

// 加一维存储经过次数，超过 n 次则认为有负环
const int N = 3e4;
ll n, m, T, d[N], v[N], s[N];
vector< pr > G[N];

void add_edge(int x,int y,int w) {
    G[x].push_back( mp(y, w) );
    if (w >= 0) G[y].push_back( mp(x, w) );
}

bool spfa(int st) 
{
    // init
    cle(d, 0x3f), cle(v, 0), cle(s, 0);
    d[st] = 0, v[st] = 1, s[st] = 1;
    queue<ll> q; q.push(st);

    while (!q.empty()) {
        ll k = q.front(); q.pop(); v[k] = 0;
        if (s[k] >= n) return 1;
        for (auto &i: G[k]) {
            int u = i.first; ll w = i.second;
            if (d[u] > d[k] + w) {
                d[u] = d[k] + w;
                if (!v[u]) v[u]=1, q.push(u), s[u]++;
            }
        }
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> T; 
while (T--) {
    cin >> n >> m;
    for (int i=1; i<=n; i++) G[i].clear();
    for (int i=0; i<m;  i++) {
        int x, y, w; cin >> x >> y >> w;
        add_edge(x, y, w);
    }
    cout << (spfa(1) ? "YES\n" : "NO\n");
}	return 0;
}

缩点：Kosaraju

const int maxn = 20001, maxm = 100100;
int n, m, a[maxn], u[maxm], v[maxm]; //初始信息
int A[maxn], s[maxn], id[maxn], in[maxn], f[maxn], cnt; 
//s[i] 用栈来模拟倒序, id[i]新图节点编号, in[i]新图的入度;
bool vis[maxn];
vector<int> g[maxn], g1[maxn], G[maxn];

void dfs1(int x) {
    vis[x] = 1;
    for (auto u:g[x]) if (!vis[u]) dfs1(u);
    s[++s[0]] = x; return;
}

void dfs2(int x) {
    id[x] = cnt, A[cnt] += a[x];
    for (auto u:g1[x]) if (!id[u]) dfs2(u);
    return;
}

int topo() {
    queue<int> q; int ans = 0;
    for (int i=1;i<=cnt;i++) if (!in[i]) f[i]=A[i], q.push(i);
    while (!q.empty()) {
        int k = q.front(); q.pop();
        for (auto u:G[k]) {
            f[u] = max(f[u], f[k]+A[u]), in[u]--;
            if (!in[u]) q.push(u);
        }
    }
    for (int i=1;i<=cnt;i++) ans = max(ans, f[i]);
    return ans;
}

int main()
{
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> a[i];
    
    // 缩点
    for (int i=1;i<=m;i++) 
        cin >> u[i] >> v[i], 
        g[ u[i] ].push_back( v[i] ), g1[ v[i] ].push_back( u[i] );
    for (int i=1;i<=n;i++) if (!vis[i]) dfs1(i); 
    for (int i=s[0];i>=1;i--) if (!id[s[i]]) cnt++, dfs2(s[i]);
    
    // 整合成新图 G
    for (int i=1;i<=m;i++) {
         int x = id[u[i]], y = id[v[i]];
         if (x != y) in[y]++, G[x].push_back(y);
    }
    cout << topo() << '\n';
    return 0;
}

最大网络流（Dinic）

#define A_LARGE_NUM inf

const int N = 1e6;
// s, t 代表超源/超汇
int n, m, s, t, st = 1, fir[N], c[N], d[N];
struct ed{ int u, nex, w; } e[N<<1];
bool v[N]; queue<int> q;

void add(int u,int v,int w) 
{
    e[++st].u = v; e[st].nex = fir[u]; e[fir[u]=st].w = w;
    e[++st].u = u; e[st].nex = fir[v]; e[fir[v]=st].w = w;
}

bool bfs() {
    cle(v, 0), memcpy(c, fir, sizeof(c));
    for (int i=0; i<=t; i++) d[i] = inf/2;
    q.push(s), v[s] = 1, d[s] = 0;
    while (!q.empty()) {
        int k = q.front(); q.pop();
        for (int i=fir[k]; i; i=e[i].nex) {
            int u = e[i].u, w = e[i].w;
            if (d[u]>d[k]+1 && w) {
                d[u] = d[k] + 1;
                if (!v[u]) v[u] = 1, q.push(u);
    }  }    }
    return (d[t] < inf/2);
}

ll dfs(int v, ll f) {
    if (v == t) return f;
    ll mw = 0, used = 0;
    for (int i=c[v]; i; i=e[i].nex) {
        c[v] = i; int u = e[i].u, w = e[i].w;
        if (w && d[u]==d[v]+1) {
            if (mw = dfs(u,min((ll)w, f-used))) {
                e[i].w -= mw, e[i^1].w += mw, used += mw;
                if (used == f) break;
    }   }   }
    return used;
}

ll dinic() {
    ll ans = 0;
    while (bfs()) ans += dfs(s, inf);
    return ans;
}

int main()
{
    cin >> n >> m;
    // 紧张激烈的构造过程
    s = 0, t = A_LARGE_NUM;
    // 最后就一行
    cout << dinic() << '\n';
    return 0;
}

三、数据结构

单调队列（滑动窗口）

struct node { int v, n; }; 
int n, m, a[2000000], ans[2000000][2];
deque<node> q, q1; //双向队列，可以从两头增加删除

int main()
{
    scanf("%d%d",&n, &m);
    for (int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        while (!q.empty() && q.front().n <= i-m) q.pop_front();
        while (!q.empty() && q.back().v  > a[i]) q.pop_back(); 
        q.push_back((node){a[i], i});
        while (!q1.empty() && q1.front().n <= i-m) q1.pop_front();
        while (!q1.empty() && q1.back().v  < a[i]) q1.pop_back(); 
        q1.push_back((node){a[i], i});
    }
    return 0;
}

树状数组（单点修改，区间查询）

#define lowbit(x) (x & (-x))
const int N = 5e5+1;
ll tr[N<<2], a[N], p, x, y, n, m;

void build(int x, int s)
{ for (int i=x; i<=n; i+=lowbit(i)) tr[i]+=s; }

ll ask(ll s) { 
    ll ans=0; 
    for (int i=s;i>=1;i-=lowbit(i)) ans+=tr[i]; 
    return ans;
}

int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i], build(i,a[i]);
    for (int i=1;i<=m;i++) {
        cin>>p>>x>>y; 
        if (p==1) build(x,y); 
        else cout<< ask(y) - ask(x-1) << endl; 
    }
    return 0;
}

线段树（区间修改，区间查询）

#define mid ((l+r)>>1)
#define pushup(o) tr[o] = tr[o<<1] + tr[o<<1|1]

const int N = 1e6+1;
ll n, m, a[N], tr[N<<2], tg[N<<2];

void pd(int o,int l,int r)
{
    ll k = tg[o];
    tr[o<<1] += (mid-l+1)*k, tr[o<<1|1] += (r-mid)*k;
    tg[o<<1] += k, tg[o<<1|1] += k, tg[o] = 0;
}

void build(int o,int l,int r)
{
    if (l==r) { tr[o] = a[l]; return; }
    build(o<<1, l, mid), build(o<<1|1,mid+1,r);
    pushup(o);
}

void modify(int o,int l,int r,int x,int y,int k)
{
    if (l>=x && r<=y) {
    	tr[o]+=(r-l+1)*k, tg[o]+=k; return;
    }
    if (y<l || x>r) return;  
    if (tg[o]) pd(o,l,r); 
    modify(o<<1,   l,   mid, x, y, k); 
    modify(o<<1|1, mid+1, r, x, y, k);
    pushup(o);
}

ll find(int o,int l,int r,int x,int y) 
{
    if (x<=l && r<=y) return tr[o];
    if (y<l || r<x) return 0;
    if (tg[o]) pd(o, l, r);
    return find(o<<1,l,mid,x,y) + find(o<<1|1,mid+1,r,x,y);
}

int main() {
    cin >> n >> m;
    for (int i=1; i<=n; i++) cin>>a[i];
    
    build(1, 1, n);
    while (m--) {
        int p, x, y; cin >> p >> x >> y;
        if (p==1) cin >> k, modify(1,1,n,x,y,k);
        else cout << find(1,1,n,x,y) << '\n';
    }
}

四、字符串

KMP 字符串匹配

string s,a;
vector<int> nex,pos; 

vector<int> check(string a)
{
    int n=a.size(),p=0; vector<int> pr(n);
    for (int i=1;i<n;i++) {
        while (p && a[p]!=a[i]) p=pr[p-1];
        if (a[p] == a[i]) ++p; pr[i]=p; 
    }
    return pr;
}

vector<int> kmp(string a,string s)
{
    nex = check(a); int n=a.size(),p=0;
    vector<int> pr;
    for (int i=0;i<s.size();i++) {
        while (p && a[p]!=s[i]) p=nex[p-1];
        if (a[p] == s[i]) ++p; 
        if (p == n) pr.push_back(i-n+1);
    }
    return pr;
}
int main()
{
    cin>>s>>a;  pos = kmp(a,s);
    for (int i=0;i<pos.size();i++) cout<<pos[i]+1<<endl;
    for (int i=0;i<nex.size();i++) cout<<nex[i]<<" ";
}

字符串哈希

int count_unique_substrings(string const& s) {
    int n = s.size();
    const int b = 31;
    const int m = 1e9 + 9;
    
    vector<long long> b_pow(n);
    b_pow[0] = 1;
    for (int i = 1; i < n; i++) 
        b_pow[i] = (b_pow[i - 1] * b) % m;
    
    vector<long long> h(n + 1, 0);
    for (int i = 0; i < n; i++)
    	h[i + 1] = (h[i] + (s[i] - 'a' + 1) * b_pow[i]) % m;
    // 构造哈希值
    
    int cnt = 0;
    for (int l = 1; l <= n; l++) {
        set<long long> hs;
        for (int i = 0; i <= n - l; i++) {
            long long cur_h = 0;
            cur_h = (h[i + l] + m - h[i-1]* b_pow[l]) % m;
            hs.insert(cur_h); // 记录不同子串个数
        }
        cnt += hs.size();
    }
    return cnt;
}