1. C 算法竞赛模板汇总在算法竞赛中一套顺手、经过验证的模板能极大提升做题效率避免在赛场上重复造轮子。本文整理了我个人常用的 C 竞赛模板涵盖基础输入输出、数据结构、图论、数学和字符串等高频模块模板均经过实战检验可以直接复制使用。2. 基础模板2.1 头文件与宏定义#include bits/stdc.h using namespace std; #define endl \n #define int long long #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() #define rep(i, a, b) for (int i (a); i (b); i) #define per(i, a, b) for (int i (a); i (b); i--) using ll long long; using ull unsigned long long; using pii pairint, int; using vi vectorint; using vll vectorll; const int INF 0x3f3f3f3f; const ll LINF 0x3f3f3f3f3f3f3f3f; const int MOD 1e9 7;2.2 快读快写inline int read() { int x 0, f 1; char ch getchar(); while (ch 0 || ch 9) { if (ch -) f -1; ch getchar(); } while (ch 0 ch 9) { x x * 10 ch - 0; ch getchar(); } return x * f; } inline void write(int x) { if (x 0) putchar(-), x -x; if (x 9) write(x / 10); putchar(x % 10 0); }3. 数据结构3.1 并查集DSUstruct DSU { vectorint fa, sz; DSU(int n) : fa(n 1), sz(n 1, 1) { iota(all(fa), 0); } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void unite(int x, int y) { x find(x), y find(y); if (x y) return; if (sz[x] sz[y]) swap(x, y); fa[y] x; sz[x] sz[y]; } bool same(int x, int y) { return find(x) find(y); } };3.2 树状数组Fenwick Treetemplatetypename T struct Fenwick { int n; vectorT tr; Fenwick(int n) : n(n), tr(n 1) {} void add(int x, T v) { for (; x n; x x -x) tr[x] v; } T sum(int x) { T res 0; for (; x; x - x -x) res tr[x]; return res; } T range(int l, int r) { return sum(r) - sum(l - 1); } };3.3 线段树Segment Treetemplatetypename T struct SegTree { int n; vectorT tr, lazy; SegTree(int n) : n(n), tr(4 * n), lazy(4 * n) {} void push(int u, int l, int r) { if (lazy[u]) { int mid (l r) 1; tr[u 1] lazy[u] * (mid - l 1); tr[u 1 | 1] lazy[u] * (r - mid); lazy[u 1] lazy[u]; lazy[u 1 | 1] lazy[u]; lazy[u] 0; } } void update(int u, int l, int r, int ql, int qr, T v) { if (ql l r qr) { tr[u] v * (r - l 1); lazy[u] v; return; } push(u, l, r); int mid (l r) 1; if (ql mid) update(u 1, l, mid, ql, qr, v); if (qr mid) update(u 1 | 1, mid 1, r, ql, qr, v); tr[u] tr[u 1] tr[u 1 | 1]; } T query(int u, int l, int r, int ql, int qr) { if (ql l r qr) return tr[u]; push(u, l, r); int mid (l r) 1; T res 0; if (ql mid) res query(u 1, l, mid, ql, qr); if (qr mid) res query(u 1 | 1, mid 1, r, ql, qr); return res; } };3.4 ST 表Sparse Tabletemplatetypename T struct SparseTable { vectorvectorT st; vectorint lg; SparseTable(const vectorT a) { int n sz(a); lg.resize(n 1); for (int i 2; i n; i) lg[i] lg[i / 2] 1; int k lg[n] 1; st.assign(k, vectorT(n)); for (int i 0; i n; i) st[0][i] a[i]; for (int j 1; j k; j) for (int i 0; i (1 j) n; i) st[j][i] max(st[j - 1][i], st[j - 1][i (1 (j - 1))]); } T query(int l, int r) { int j lg[r - l 1]; return max(st[j][l], st[j][r - (1 j) 1]); } };4. 图论4.1 Dijkstra 最短路vectorll dijkstra(int n, int s, const vectorvectorpii g) { vectorll dist(n 1, LINF); dist[s] 0; priority_queuepairll, int, vectorpairll, int, greater pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; for (auto [v, w] : g[u]) { if (dist[v] d w) { dist[v] d w; pq.push({dist[v], v}); } } } return dist; }4.2 Kruskal 最小生成树struct Edge { int u, v, w; bool operator(const Edge o) const { return w o.w; } }; ll kruskal(int n, vectorEdge edges) { sort(all(edges)); DSU dsu(n); ll res 0; int cnt 0; for (auto [u, v, w] : edges) { if (!dsu.same(u, v)) { dsu.unite(u, v); res w; cnt; } } return cnt n - 1 ? res : -1; }4.3 拓扑排序Kahn 算法vectorint toposort(int n, const vectorvectorint g) { vectorint indeg(n 1), res; for (int u 1; u n; u) for (int v : g[u]) indeg[v]; queueint q; for (int i 1; i n; i) if (!indeg[i]) q.push(i); while (!q.empty()) { int u q.front(); q.pop(); res.push_back(u); for (int v : g[u]) if (--indeg[v] 0) q.push(v); } return res; }5. 数学5.1 快速幂ll qpow(ll a, ll b, ll p MOD) { ll res 1; for (; b; b 1, a a * a % p) if (b 1) res res * a % p; return res; }5.2 线性筛素数vectorint primes; vectorbool isPrime; void sieve(int n) { isPrime.assign(n 1, true); isPrime[0] isPrime[1] false; for (int i 2; i n; i) { if (isPrime[i]) primes.push_back(i); for (int p : primes) { if (1LL * i * p n) break; isPrime[i * p] false; if (i % p 0) break; } } }5.3 最大公约数与最小公倍数ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }5.4 组合数预处理阶乘const int MAXN 1e5 5; ll fact[MAXN], invFact[MAXN]; void initComb() { fact[0] 1; for (int i 1; i MAXN; i) fact[i] fact[i - 1] * i % MOD; invFact[MAXN - 1] qpow(fact[MAXN - 1], MOD - 2); for (int i MAXN - 2; i 0; i--) invFact[i] invFact[i 1] * (i 1) % MOD; } ll C(int n, int m) { if (n m || m 0) return 0; return fact[n] * invFact[m] % MOD * invFact[n - m] % MOD; }6. 字符串6.1 KMP 匹配vectorint kmp(const string s) { int n sz(s); vectorint pi(n); for (int i 1; i n; i) { int j pi[i - 1]; while (j s[i] ! s[j]) j pi[j - 1]; if (s[i] s[j]) j; pi[i] j; } return pi; } vectorint kmpMatch(const string txt, const string pat) { string s pat # txt; auto pi kmp(s); int plen sz(pat); vectorint occ; for (int i plen 1; i sz(s); i) if (pi[i] plen) occ.push_back(i - 2 * plen); return occ; }6.2 字符串哈希双哈希struct StringHash { using P pairint, int; static constexpr int B1 131, B2 13331; static constexpr int M1 1e9 7, M2 1e9 9; vectorll h1, h2, p1, p2; StringHash(const string s) { int n sz(s); h1.resize(n 1); h2.resize(n 1); p1.resize(n 1, 1); p2.resize(n 1, 1); for (int i 0; i n; i) { h1[i 1] (h1[i] * B1 s[i]) % M1; h2[i 1] (h2[i] * B2 s[i]) % M2; p1[i 1] p1[i] * B1 % M1; p2[i 1] p2[i] * B2 % M2; } } P get(int l, int r) { return { (h1[r 1] - h1[l] * p1[r - l 1] % M1 M1) % M1, (h2[r 1] - h2[l] * p2[r - l 1] % M2 M2) % M2 }; } };以上是本人常用的一些 C 算法竞赛模板涵盖了从基础工具到核心算法的常用模块。在实际比赛中建议根据题目特点灵活选用同时也鼓励大家在理解原理的基础上打磨自己的模板不断优化可读性和鲁棒性。祝大家比赛顺利AC 不断
