C++常用模版
Heartlessly
2018-08-06 16:40:18
## 快速读入模版
```cpp
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}
```
------------
## 快速输出模版
```cpp
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
```
------------
## 指令优化模版
```cpp
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
```
------------
## 最大公约数(gcd)模板
```cpp
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
```
------------
## 扩展欧几里得(exgcd)模版
```cpp
LL exGcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return a;
}
LL d = exGcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
```
------------
## 快速幂模版
```cpp
long long ksm(long long x, long long p) { long long res = 1; for (; p; p >>= 1, x = x * x % mod) if (p & 1) res = res * x % mod; return res; }
```
------------
## 快速乘模版
```cpp
long long ksc(long long x, long long p) { long long res = 0; for (; p; p >>= 1, x = (x << 1) % mod) if (p & 1) res = (res + x) % mod; return res; }
```
------------
## 最长不下降子序列模板
```cpp
/*
8
1 9 2 4 5 7 3 6
*/
for (int i = 1; i <= n; i++) read(a[i]);
b[++len] = a[1];
for (int i = 2; i <= n; i++) {
if (a[i] >= b[len]) b[++len] = a[i];
else {
int j = upper_bound(b + 1, b + len + 1, a[i]) - b;//找到第一个大于它的b的下标
b[j] = a[i];
}
}
```
------------
## 最长上升子序列模板
```cpp
for (int i = 1; i <= n; i++) read(a[i]);
b[++len] = a[1];
for (int i = 2; i <= n; i++) {
if (a[i] > b[len]) b[++len] = a[i];
else {
int j = lower_bound(b + 1, b + len + 1, a[i]) - b;//找到第一个大于等于它的b的下标
b[j] = a[i];
}
}
```
------------
## 并查集模板
```cpp
struct ufSet {
int fa[maxN];
inline void init() { for (int i = 1; i <= n; ++i) fa[i] = i; }
int find(int x) { return x ^ fa[x] ? fa[x] = find(fa[x]) : x; }
inline bool check(int x, int y) { return find(x) == find(y); }
inline void merge(int x, int y) { fa[find(x)] = find(y); }
} s;
```
------------
## 链式前向星存图模版
```cpp
int tot, head[maxN];
struct Edge {
int next, to, dis;
} e[maxM];
inline void addEdge(int u, int v, int w) { e[++tot] = (Edge) { head[u], v, w }; head[u] = tot; }
```
------------
## SPFA模板
```cpp
struct SPFA {
inline void solve(int s) {
memset(dis, 0x3f, sizeof (dis));
memset(vis, 0, sizeof (vis));
q.push(s); vis[s] = 1; dis[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (dis[v] > dis[u] + e[i].dis) {
dis[v] = dis[u] + e[i].dis;
if (!vis[v]) { vis[v] = 1; q.push(v); }
}
}
}
}
inline int query(int u, int v) { solve(u); return dis[v]; }
} graph;
```
------------
## Dijkstra模板
```cpp
struct Edge {
int next, to, dis;
} e[maxM];
struct Node {
int id, val;
};
int tot, head[maxN], dis[maxN];
bool vis[maxN];
priority_queue <Node> q;
inline bool operator < (Node x, Node y) { return x.val > y.val; }
inline void addEdge(int u, int v, int w) { e[++tot] = (Edge) { head[u], v, w }; head[u] = tot; }
inline void Dijkstra(int s) {
memset(dis, 0x3f, sizeof (dis));
dis[s] = 0;
q.push((Node) { s, 0 });
while (!q.empty()) {
Node tmp = q.top(); q.pop();
int u = tmp.id;
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (dis[v] > dis[u] + e[i].dis) {
dis[v] = dis[u] + e[i].dis;
if (!vis[v]) q.push((Node) { v, dis[v] });
}
}
}
}
```
------------
## Prim模板
```cpp
inline int prim() {
int res = 0;
memset(dis, 0x3f, sizeof (dis));
dis[1] = 0;
for (int j = 1; j <= n; ++j) {
int u = 0;
for (int v = 1; v <= n; ++v)
if (!vis[v] && dis[v] < dis[u])
u = v;
vis[u] = 1;
res += dis[u];
for (int v, w, i = head[u]; v = e[i].to, w = e[i].dis, i; i = e[i].next)
if (!vis[v] && dis[v] > w) dis[v] = w;
}
return res;
}
```
------------
## Kruscal模板
```cpp
struct Kruscal {
int fa[maxN];
inline void init() { for (int i = 1; i <= n; ++i) fa[i] = i; }
int find(int x) { return x ^ fa[x] ? fa[x] = find(fa[x]) : x; }
inline bool check(int x, int y) { return find(x) == find(y); }
inline void merge(int x, int y) { fa[find(x)] = find(y); }
inline int solve() {
init();
sort(e + 1, e + m + 1);
int res = 0, cnt = 0;
for (int i = 1; i <= m; ++i) {
if (check(e[i].u, e[i].v)) continue;
merge(e[i].u, e[i].v);
res += e[i].w;
if (++cnt == n - 1) return res;
}
return -1;
}
} mst;
```
------------
## LCA(最近公共祖先)模板
```cpp
struct LCA {
int depth[maxN], lg[maxN], fa[22][maxN];
inline void dfs(int x, int par) {
depth[x] = depth[par] + 1;
fa[0][x] = par;
for (int i = 1; i <= lg[depth[x]]; ++i)
fa[i][x] = fa[i - 1][fa[i - 1][x]];
for (int i = head[x]; i; i = next[i])
if (to[i] ^ par)
dfs(to[i], x);
}
inline void init(int root) {
lg[0] = -1;
for (int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
dfs(root, 0);
}
inline int query(int x, int y) {
if (depth[x] < depth[y]) swap(x, y);
while (depth[x] > depth[y]) x = fa[lg[depth[x] - depth[y]]][x];
if (x == y) return x;
for (int i = lg[depth[x]]; ~i; --i)
if (fa[i][x] ^ fa[i][y]) x = fa[i][x], y = fa[i][y];
return fa[0][x];
}
} lca;
```
------------
## 莫队模板
```cpp
bool operator<(Mo a, Mo b) { return (a.l / blockSize) ^ (b.l / blockSize) ? a.l < b.l : (((a.l / blockSize) & 1) ? a.r < b.r : a.r > b.r); }
inline void add() {}
inline void del() {}
for (; l > ql; add(col[--l]));
for (; r < qr; add(col[++r]));
for (; l < ql; del(col[l++]));
for (; r > qr; del(col[r--]));
```
------------
## 高斯消元模板
```cpp
inline int Gauss() {
for (int i = 1; i <= n; ++i) {
int p = i;
for (int j = i + 1; j <= n; ++j)
if (fabs(m[p][i]) < fabs(m[j][i]))
p = j;
swap(m[p], m[i]);
double t = m[i][i];
if (fabs(t) < eps) continue;
for (int j = i; j <= n + 1; ++j)
m[i][j] /= t;
for (int j = 1; j <= n; ++j)
if (i != j) {
t = m[j][i];
for (int k = 1; k <= n + 1; ++k)
m[j][k] -= m[i][k] * t;
}
}
bool f1 = 0, f2 = 0;
for (int i = 1; i <= n; ++i) {
int t = 0;
for (int j = 1; j <= n + 1; ++j)
if (fabs(m[i][j]) < eps)
++t;
if (t == n && fabs(m[i][n + 1]) > eps) f1 |= 1;
if (t == n + 1) f2 |= 1;
}
if (f1) return -1;//方程组无解
if (f2) return 0;//方程组有无数解
for (int i = n - 1; i; --i)
for (int j = i + 1; j <= n; ++j)
m[i][n + 1] -= m[i][j] * m[j][n + 1];
return 1;//方程组有唯一解
}
```
------------
## 矩阵加速模板
```cpp
struct Matrix {
LL m[3][3];
inline void clear() {
memset(m, 0, sizeof (m));
}
inline Matrix friend operator*(Matrix a, Matrix b) {
Matrix c;
c.clear();
for (int i = 1; i <= 2; ++i)
for (int j = 1; j <= 2; ++j)
for (int k = 1; k <= 2; ++k)
c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j] % mod) % mod;
return c;
}
inline Matrix friend operator^(Matrix x, LL p) {
Matrix res;
res.clear();
for (int i = 1; i <= 2; ++i)
res.m[i][i] = 1;
for (; p; p >>= 1, x = x * x)
if (p & 1)
res = res * x;
return res;
}
} ans, base;
```
------------
## 中国剩余定理(crt)模板
```cpp
void exGcd(LL a, LL b, LL &x, LL &y) {
if (!b) x = 1, y = 0;
else {
exGcd(b, a % b, y, x);
y -= a / b * x;
}
}
inline LL crt(int n, LL *a, LL *b) {
LL m = 1, ans = 0;
for (int i = 1; i <= n; ++i) m *= b[i];
for (int i = 1; i <= n; ++i) {
LL mi = m / b[i], x, y;
exGcd(mi, b[i], x, y);
x = (x % b[i] + b[i]) % b[i];
ans = (ans + quickMul(quickMul(mi, x, m), a[i], m)) % m;
}
return (ans % m + m) % m;
}
```
------------
## 扩展中国剩余定理(exCRT)模板
```cpp
LL exGcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return a;
}
LL d = exGcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
inline LL exCrt(int n, LL *a, LL *b) {
LL res = a[1], lcm = b[1];
for (int i = 2; i <= n; ++i) {
LL x, y, c = ((a[i] - res) % b[i] + b[i]) % b[i], d = exGcd(lcm, b[i], x, y), m = b[i] / d;
if (c % d) return -1;
x = slowMul(x, c / d, m);
res += lcm * x;
lcm *= m;
res = (res + lcm) % lcm;
}
return res;
}
```
------------
## Hash模板
```cpp
struct Hash {
int mod, base, power[MAXN + 5], hashes[MAXN + 5];
Hash(int a, int b) {
mod = a, base = b;
}
inline void init(char *s, int n) {
power[0] = 1;
for (int i = 1; i <= n; ++i) power[i] = power[i - 1] * base % mod;
for (int i = 1; i <= n; ++i) hashes[i] = ((LL) hashes[i - 1] * power[i] % mod + s[i]) % mod;
}
inline int query(int x) {
return hashes[x];
}
inline int query(int l, int r) {
return (hashes[r] - (LL) hashes[l - 1] * power[r - l + 1] % mod + mod) % mod;
}
};
```
## 最大流模板
```cpp
inline bool bfs(int s, int t) {
for (int i = 0; i <= n; ++i) cur[i] = head[i];
memset(depth, 0, sizeof (depth));
queue<int> q;
depth[s] = 1;
q.push(s);
for (; !q.empty(); ) {
int u = q.front();
q.pop();
for (int v, w, i = head[u]; v = e[i].to, w = e[i].dis, i; i = e[i].next) {
if (depth[v] || !w) continue;
depth[v] = depth[u] + 1;
if (v == t) return 1;
q.push(v);
}
}
return 0;
}
inline int dinic(int u, int t, int flow) {
if (u == t) return flow;
int rest = flow;
for (int v, w, i = cur[u]; v = e[i].to, w = e[i].dis, i && rest; i = e[i].next) {
cur[u] = i;
if (depth[v] != depth[u] + 1 || !w) continue;
int k = dinic(v, t, min(rest, w));
if (!k) depth[v] = 0;
else {
e[i].dis -= k;
e[i ^ 1].dis += k;
rest -= k;
}
}
return flow - rest;
}
inline LL maxFlow(int s, int t) {
LL res = 0;
for (; bfs(s, t); ) res += dinic(s, t, INF);
return res;
}
```
## 最小费用最大流模板
```cpp
inline bool spfa(int s, int t) {
memset(vis, 0, sizeof (vis));
memset(dis, 0x3f, sizeof (dis));
queue<int> q;
dis[s] = 0;
flow[s] = INF;
q.push(s);
for (; !q.empty(); ) {
int u = q.front();
q.pop();
vis[u] = 0;
for (int v, w, c, i = head[u]; v = e[i].to, w = e[i].dis, c = e[i].cost, i;
i = e[i].next)
if (dis[v] > dis[u] + c && w) {
dis[v] = dis[u] + c;
pre[v] = i;
flow[v] = min(flow[u], w);
if (!vis[v]) {
q.push(v);
vis[v] = 1;
}
}
}
return dis[t] < INF;
}
inline void query(int s, int t) {
LL maxFlow = 0, minCost = 0;
for (; spfa(s, t); ) {
for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
e[pre[i]].dis -= flow[t];
e[pre[i] ^ 1].dis += flow[t];
}
maxFlow += flow[t];
minCost += flow[t] * dis[t];
}
write(maxFlow);
putchar(' ');
write(minCost);
putchar('\n');
}
```