这是用来存模板的地方，不断更新。
基础
输入优化（整数）
inline int read(){ int num = 0, b = 1; char c = getchar(); while(c < '0' || c > '9') c == '-' ? b = -1 : 0, c = getchar(); while(c >= '0' & c <= '9') num = num * 10 + c - '0', c = getchar(); return num * b; }
数学
最大公约数
int gcd(int a, int b){ if(!b) return a; return gcd(b, a % b); }
快速幂
int qpow(int a, int b){ // 分别代表底数、指数 int t = 1; while(b){ if(b & 1) t = t * a % MOD; // MOD 是模数 a = a * a % MOD; b >>= 1; } return t; }
埃氏筛法
bool b[1000010]; // b[i] 代表 i 是否是质数 void Prime(){ for(int i = 2; i <= 1000; i++){ if(!b[i]) for(int j = i; j <= 1000000; j += i) b[j] = 1; } }
线性筛
int p[1000010], ans[1000010], cnt; // 存储质数的序列 void Prime(){ for(int i = 2; i <= 1000000; i++){ if(!b[i]) ans[++cnt] = i; for(int j = 1; i * p[j] <= 1000000; j++){ b[i % p[j]] = 1; if(i % p[j] == 0) break; } } }
求单个数在模数为质数意义下的逆元
typedef long long ll; ll qpow(ll a, ll b){ // 分别代表底数、指数 ll t = 1; while(b){ if(b & 1) t = t * a % MOD; // MOD 是模数 a = a * a % MOD; b >>= 1; } return t; } ll inv(ll x){ return qpow(x, MOD - 2); }
线性求范围内模数为质数意义下的逆元
typedef long long ll; ll inv[1000010]; void Inv(){ inv[0] = inv[1] = 0; for(ll i = 2; i <= 1000000; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD; // MOD 是模数 }
数字 $aa$ 在模 $bb$ 意义下（不保证是质数）的逆元
typedef long long ll; void exgcd(ll a, ll b, int &x, int &y){ if(!b){ x = 1, y = 0; return } exgcd(b, a % b, x, y); y -= (a / b) * x; } ll inv(ll aa, ll bb){ ll x = 0, y = 0; exgcd(aa, bb, x, y); return (x + bb) % bb; }
图论
最小生成树（竞速：285s）
#include <algorithm> #include <cstdio> #define INF 1e9 #define eps 1e-9 typedef long long ll; struct Edge{ int from; int to; int val; }e[400010]; int n, m, f[10010], x, y, z, cnt, sum, ans; void add(int a, int b, int c){ e[++cnt].from = a; e[cnt].to = b; e[cnt].val = c; } bool cmp(Edge a, Edge b){ return a.val < b.val; } int find(int xx){ if(xx == f[xx]) return xx; return f[xx] = find(f[xx]); } int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) scanf("%d%d%d", &x, &y, &z), add(x, y, z), add(y, x, z); std::sort(e + 1, e + cnt + 1, cmp); for(int i = 1; i <= n; i++) f[i] = i; for(int i = 1; i <= cnt; i++){ x = find(e[i].from), y = find(e[i].to); if(x != y){ f[x] = y, ans += e[i].val; if(++sum == n - 1) break; } } if(sum != n - 1) puts("orz"); else printf("%d ", ans); return 0; }
单源最短路径（Dijkstra）（竞速：482s）
#include <cstring> #include <cstdio> #include <queue> #define INF (1 << 30) #define eps 1e-9 #define N 100010 typedef long long ll; using namespace std; struct Edge{ int to, next, val; }e[N << 1]; struct Point{ int id, dis; }; bool operator < (Point x, Point y){ return x.dis > y.dis; } priority_queue <Point> q; int n, m, s, fir[N], u, v, w, cnt, dis[N]; bool vis[N]; void add(int x, int y, int z){ e[++cnt].to = y; e[cnt].next = fir[x]; e[cnt].val = z; fir[x] = cnt; } void Dijkstra(){ for(int i = 1; i <= n; i++) dis[i] = INF; dis[s] = 0; q.push((Point){s, 0}); while(!q.empty()){ int x = q.top().id; q.pop(); if(vis[x]) continue; vis[x] = 1; for(int i = fir[x]; i; i = e[i].next){ int y = e[i].to; if(dis[y] > dis[x] + e[i].val){ dis[y] = dis[x] + e[i].val; q.push((Point){y, dis[y]}); } } } for(int i = 1; i <= n; i++) printf("%d ", dis[i]); puts(""); } int main(){ scanf("%d%d%d", &n, &m, &s); for(int i = 1; i <= m; i++) scanf("%d%d%d", &u, &v, &w), add(u, v, w); Dijkstra(); return 0; }
数据结构
线段树（区间加，区间和）（竞速：450s）
#include <cstdio> #define N 100010 #define INF 1e9 #define eps 1e-9 typedef long long ll; int n, m, p, q, opt; ll s, a[N << 2], add[N << 2], sum[N << 2]; void build(int i, int l, int r){ if(l == r){ sum[i] = a[l]; return; } int mid = (l + r) >> 1; build(i << 1, l, mid); build(i << 1 | 1, mid + 1, r); sum[i] = sum[i << 1] + sum[i << 1 | 1]; } void plu(int i, int l, int r, ll v){ add[i] += v; sum[i] += (r - l + 1) * v; } void pushdown(int i, int l, int r, int mid){ if(add[i] == 0) return; plu(i << 1, l, mid, add[i]); plu(i << 1 | 1, mid + 1, r, add[i]); add[i] = 0; } void modify(int i, int l, int r, int x, int y, ll v){ if(l >= x && r <= y){ plu(i, l, r, v); return; } int mid = (l + r) >> 1; pushdown(i, l, r, mid); if(x <= mid) modify(i << 1, l, mid, x, y, v); if(y > mid) modify(i << 1 | 1, mid + 1, r, x, y, v); sum[i] = sum[i << 1] + sum[i << 1 | 1]; } ll query(int i, int l, int r, int x, int y){ if(l >= x && r <= y) return sum[i]; int mid = (l + r) >> 1; ll ans = 0; pushdown(i, l, r, mid); if(x <= mid) ans += query(i << 1, l, mid, x, y); if(y > mid) ans += query(i << 1 | 1, mid + 1, r, x, y); return ans; } int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); build(1, 1, n); while(m--){ scanf("%d%d%d", &opt, &p, &q); if(opt == 1) scanf("%lld", &s), modify(1, 1, n, p, q, s); else printf("%lld ", query(1, 1, n, p, q)); } return 0; }
LCA（倍增）
#include <cstdio> #define INF 1e9 #define eps 1e-9 #define N 500010 typedef long long ll; struct Edge{ int to, next; }e[N << 1]; int n, m, s, u, v, lg[N]; int d[N], fir[N], cnt, f[N][25]; void add(int x, int y){ e[++cnt].to = y; e[cnt].next = fir[x]; fir[x] = cnt; } void dfs(int x, int fa){ d[x] = d[fa] + 1, f[x][0] = fa; for(int i = 1; (1 << i) <= d[x]; i++) f[x][i] = f[f[x][i - 1]][i - 1]; for(int i = fir[x]; i; i = e[i].next) if(e[i].to != fa) dfs(e[i].to, x); } int lca(int x, int y){ if(d[x] < d[y]) x ^= y, y ^= x, x ^= y; while(d[x] > d[y]) x = f[x][lg[d[x] - d[y]] - 1]; if(x == y) return x; for(int i = lg[d[x]] - 1; i >= 0; i--) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i]; return f[x][0]; } int main(){ scanf("%d%d%d", &n, &m, &s); for(int i = 1; i < n; i++) scanf("%d%d", &u, &v), add(u, v), add(v, u); dfs(s, 0); for(int i = 1; i <= n; i++) lg[i] = (1 << lg[i - 1]) == i ? lg[i - 1] + 1 : lg[i - 1]; while(m--){ scanf("%d%d", &u, &v); printf("%d ", lca(u, v)); } return 0; }
DP
……先咕着，以后再存