竞赛算法模板
GESP 四至八级与 CSP 备考的核心模板，全部按 C++11 标准编写，可直接复制到在线编译器运行验证。
快读快写 输入量大时提速
数据规模 10⁵ 以上建议用。最简做法是关流同步；追求极致用自定义快读。
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 之后 cin / cout 更快，但不能再混用 printf / scanf
int n; cin >> n;
cout << n << endl;
return 0;
}gcd / lcm 数论基础
辗转相除法，O(log n)。C++17 才提供 std::gcd，考试用下面手写版。
long long gcd(long long a, long long b){
return b ? gcd(b, a % b) : a;
}
long long lcm(long long a, long long b){
return a / gcd(a, b) * b; // 先除再乘防溢出
}快速幂 O(log n)
求 a 的 b 次方模 mod，处理大指数时必备。
long long qpow(long long a, long long b, long long mod){
long long res = 1;
while (b){
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
// 例：qpow(2, 10, 1000000007)二分答案 最大值最小化
答案具有单调性时，在可行区间上二分。这是 CSP/NOIP 高频思想。
bool ok(int x){ /* 判断 x 是否可行，自行实现 */ }
int l = 0, r = 1e9, ans = 0;
while (l <= r){
int mid = (l + r) / 2;
if (ok(mid)){ ans = mid; l = mid + 1; } // 找最大的可行值
else r = mid - 1;
}前缀和 区间求和 O(1)
预处理后，任意区间 [l, r] 的和 = s[r] − s[l−1]。
int n, q; cin >> n >> q;
vector<long long> s(n + 1, 0);
for (int i = 1; i <= n; i++){
long long x; cin >> x;
s[i] = s[i-1] + x; // 前缀和
}
while (q--){
int l, r; cin >> l >> r;
cout << s[r] - s[l-1] << endl;
}DFS 深度优先 搜索 / 遍历
邻接表存图，visited 防重复。适合找路径、连通块、排列组合。
vector<int> g[100005];
bool vis[100005];
void dfs(int u){
vis[u] = true;
for (int v : g[u])
if (!vis[v]) dfs(v);
}BFS 广度优先 无权图最短路
按层扩展，第一次到达的步数即最短路。队列实现。
queue<int> q;
int dist[100005];
memset(dist, -1, sizeof dist);
q.push(1); dist[1] = 0;
while (!q.empty()){
int u = q.front(); q.pop();
for (int v : g[u])
if (dist[v] == -1){
dist[v] = dist[u] + 1;
q.push(v);
}
}01 背包 动态规划
每件物品选或不选，容量 V。dp[j] 表示容量 j 的最大价值。
int n, V; cin >> n >> V;
vector<int> dp(V + 1, 0);
for (int i = 0; i < n; i++){
int w, v; cin >> w >> v; // 重量、价值
for (int j = V; j >= w; j--) // 倒序！保证每件只取一次
dp[j] = max(dp[j], dp[j - w] + v);
}
cout << dp[V] << endl;并查集 连通性 / 分组
合并集合 + 查询是否同组，带路径压缩近似 O(1)。
int f[100005];
int find(int x){ return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int a, int b){ f[find(a)] = find(b); }
for (int i = 1; i <= n; i++) f[i] = i;
// merge(a, b); 合并
// find(a) == find(b) 判断是否同组素数筛（埃氏筛） 预处理素数
O(n log log n)，筛出 n 以内所有素数。
bool isp[1000005];
void sieve(int n){
fill(isp, isp + n + 1, true);
isp[0] = isp[1] = false;
for (int i = 2; 1LL * i * i <= n; i++)
if (isp[i])
for (int j = i * i; j <= n; j += i)
isp[j] = false;
}