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

前言

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

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

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

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

常用板子

树状数组

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

int bit[500010]; void add(int k, int x) { 	while (k <= n) { 		bit[k] += x; 		k += lowbit(k); 	} } int ask(int k) { 	int res = 0; 	while (k) { 		res += bit[k]; 		k -= lowbit(k); 	} 	return res; } 

线段树

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

struct SegmentTree { 	ll sum[N << 2], lazy[N << 2]; 	int l[N << 2], r[N << 2]; 	void update(int rt) { 		sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; 	} 	void pushdown(int rt) { 		if (!lazy[rt]) return ; 		sum[rt << 1] += (r[rt << 1] - l[rt << 1] + 1) * lazy[rt], lazy[rt << 1] += lazy[rt]; 		sum[rt << 1 | 1] += (r[rt << 1 | 1] - l[rt << 1 | 1] + 1) * lazy[rt], lazy[rt << 1 | 1] += lazy[rt]; 		lazy[rt] = 0; 		update(rt); 	} 	void build(int rt, int L, int R) { 		l[rt] = L, r[rt] = R; 		if (L == R) { 			sum[rt] = a[L]; 			return ; 		} 		int mid = L + R >> 1; 		build(rt << 1, L, mid), build(rt << 1 | 1, mid + 1, R); 		update(rt); 	} 	void change(int rt, int L, int R, int x) { 		if (L <= l[rt] && r[rt] <= R) { 			sum[rt] += (r[rt] - l[rt] + 1) * x; 			lazy[rt] += x; 			return ; 		} 		pushdown(rt); 		if (L <= r[rt << 1]) change(rt << 1, L, R, x); 		if (l[rt << 1 | 1] <= R) change(rt << 1 | 1, L, R, x); 		update(rt); 	} 	ll query(int rt, int L, int R) { 		if (L <= l[rt] && r[rt] <= R) return sum[rt]; 		pushdown(rt); 		ll res = 0; 		if (L <= r[rt << 1]) res += query(rt << 1, L, R); 		if (l[rt << 1 | 1] <= R) res += query(rt << 1 | 1, L, R); 		return res; 	} } tree; 

堆

不是吧真有人手写堆吗

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 << 1 <= cnt) { 		if ((id << 1 | 1) <= cnt) { 			if (q[id] < min(q[id << 1], q[id << 1 | 1])) break;; 			if (q[id << 1] < q[id << 1 | 1]) swap(q[id], q[id << 1]), id <<= 1; 			else swap(q[id], q[id << 1 | 1]), id = id << 1 | 1; 		} 		else { 			if (q[id] > q[id << 1]) swap(q[id], q[id << 1]); 			break; 		} 	} } void add(ll x) { 	q[++cnt] = x; 	pushup(cnt); } void pop() { 	swap(q[1], q[cnt]); 	cnt--; 	movedown(); } 

并查集

struct Disjoint_Set { 	int p[N], size[N]; 	void build() { 		for (int i = 1; i <= n; i++) p[i] = i, size[i] = 1; 	} 	int root(int x) { 		if (p[x] != x) return p[x] = root(p[x]); 		return x; 	} 	void merge(int x, int y) { 		x = root(x), y = root(y); 		if (size[x] > 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 <= n; i++) st[0][i] = a[i]; for (int j = 1; j <= lg; j++) { 	for (int i = 1; i <= n - (1 << j) + 1; i++) { 		st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]); 	} } int l, r, lg2, len; for (int i = 1; i <= m; i++) { 	l = read(), r = read(); 	lg2 = log2(r - l + 1); 	len = 1 << lg2; 	printf("%dn", max(st[lg2][l], st[lg2][r - len + 1])); } 

边链表

const int N = 100010; int last[N], cnt; struct edge { 	int to, next, w; } e[N << 1]; void addedge(int x, int y, int w) { 	e[++cnt].to = y; 	e[cnt].next = last[x]; 	e[cnt].w = w; 	last[x] = cnt; } 

LCA

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

struct Disjoint_Set { 	int p[N], size[N]; 	void build() { 		for (int i = 1; i <= n; i++) p[i] = i, size[i] = 1; 	} 	int root(int x) { 		if (p[x] != x) return p[x] = root(p[x]); 		return x; 	} 	void merge(int x, int y) { 		x = root(x), y = root(y); 		if (size[x] > 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 << 1]; void addedge(int x, int y) { 	e[++cnt].to = y; 	e[cnt].next = last[x]; 	last[x] = cnt; } struct node { 	int x, y, ans; } ask[N]; vector <int> 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 <pii, vector<pii>, greater<pii> > 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 < dis[v]) dis[v] = dis[pos] + e[j].w, q.push({dis[v], v}); 		} 	} 

缩点

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

int dfn[N], low[N], dcnt; bool instack[N]; stack <int> 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 << 1]; int rd[N], cd[N]; bool cmp(edge x, edge y) { 	if (x.u != y.u) return x.u < y.u; 	return x.v < y.v; } int ans[N << 1], cnt; void dfs(int x) { 	while (st[x] <= ed[x]) { 		st[x]++; 		dfs(e[st[x] - 1].v); 	} 	ans[++cnt] = x; } 

乘法逆元

fac[0] = fac[1] = 1; for (int i = 2; i <= n; i++) fac[i] = fac[i - 1] * i % mod; inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod; 

快速幂

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 <= n; i++) x[i][i] = 1; 	} 	void dd() { 		for (int i = 1; i <= n; i++) 			for (int j = 1; j <= n; j++) 				x[i][j] = 0; 	} } a, ans; sq operator *(const sq &x, const sq &y) { 	sq res; 	res.dd(); 	for (int k = 1; k <= n; k++) 		for (int i = 1; i <= n; i++) 			for (int j = 1; j <= n; j++) 				res.x[i][j] = (res.x[i][j] + x.x[i][k] * y.x[k][j] % mod) % mod; 	return res; } void qpow(ll x) { 	while (x) { 		if (x & 1) ans = ans * a; 		a = a * a; 		x >>= 1; 	} } 

线性基

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

int p[N]; void add(ll x) { 	for (int i = N; i >= 0; i--) { 		if (!(x & (1ll << i))) continue; 		if (p[i]) x ^= p[i]; 		else {p[i] = x; return ;} 	} } 

线性筛

int prime[6000010], cnt; bool isprime[N + 10]; void prim() { 	isprime[0] = isprime[1] = 1; 	for (int i = 2; i <= n; i++) { 		if (!isprime[i]) prime[++cnt] = i; 		for (int j = 1; j <= cnt && i * prime[j] <= n; j++) { 			isprime[i * prime[j]] = 1; 			if (i % prime[j] == 0) break; 		} 	} } 

字符串哈希

int Char(char c) { 	if (c >= '0' && c <= '9') return c - '0' + 1; //0~9: 1~10 	if (c >= 'a' && c <= 'z') return c - 'a' + 11; //a~z: 11~37 	if (c >= 'A' && c <= 'Z') return c - 'A' + 38; //A~Z: 38~65 	return 0; } map <ll, int> mp;  cin >> s; ll x = 0; for (int i = 0; i < s.size(); i++) x = (x * 100) + Char(s[i]); mp[x] = 1; 

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 <= lt; i++) { 	while (j >= 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 <= ls) { 	while (tx >= 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 < s.size(); i++) { 		if (!t[now].id[s[i] - 'a']) t[now].id[s[i] - 'a'] = ++cnt; 		now = t[now].id[s[i] - 'a']; 	} 	t[now].cnt++; } void Fail() { 	queue <int> q; 	for (int i = 0; i < 26; i++) { 		int v = t[0].id[i]; 		if (v != 0) { 			t[v].fail = 0; 			q.push(v); 		} 	} 	while (!q.empty()) { 		int u = q.front(); q.pop(); 		for (int i = 0; i < 26; i++) { 			int v = t[u].id[i]; 			if (v != 0) { 				t[v].fail = t[t[u].fail].id[i]; 				q.push(v); 			} 			else t[u].id[i] = t[t[u].fail].id[i]; 		} 	} } string s; int ans; void Query() { 	int now = 0; 	for (int i = 0; i < s.size(); i++) { 		now = t[now].id[s[i] - 'a']; 		for (int to = now; to; to = t[to].fail) { 			if (t[to].cnt == -1) break; 			ans += t[to].cnt; 			t[to].cnt = -1; 		} 	} }