算法竞赛实战模板精讲（C++）—— 从入门到赛场速通
1. 算法竞赛必备C++模板入门
算法竞赛中，模板代码是选手的"武器库"。掌握这些模板能让你在赛场上快速解决常见问题，把更多时间留给难题。我们先从最基础的输入输出优化开始：
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);这三行代码能显著提升C++的输入输出速度。第一行解除C++与C的IO同步，后两行解绑cin和cout的关联。实测在读取10^5量级数据时，速度能提升5-8倍。
注意：使用后不能混用C和C++的IO函数（如printf和cout）
2. 数学相关模板
2.1 素数判断与筛法
简单判断法：
bool is_prime(int x) { if(x == 1) return false; if(x == 2) return true; for(int i = 2; i*i <= x; i++) if(x%i == 0) return false; return true; }埃拉托斯特尼筛法：
const int N = 1e8; bool is_prime[N+1]; for(int i = 2; i <= sqrt(n); i++) { if(!is_prime[i]) { for(int j = i*i; j <= n; j += i) is_prime[j] = 1; } }欧拉筛（线性筛）：
const int N = 1e7; int prime[N+1]; bool visit[N+1]; memset(visit, 0, sizeof visit); int cnt = 0; for(int i = 2; i <= n; i++) { if(!visit[i]) prime[cnt++] = i; for(int j = 0; j < cnt; j++) { if(i * prime[j] > n) break; visit[i * prime[j]] = 1; if(i % prime[j] == 0) break; } }欧拉筛的优势在于每个合数只被标记一次，时间复杂度O(n)。我在实际比赛中发现，当n>1e7时，欧拉筛比埃筛快约30%。
3. 字符串处理
3.1 字符串排序
#include <bits/stdc++.h> using namespace std; string s[100]; int main() { int n; cin >> n; for(int i = 0; i < n; i++) cin >> s[i]; sort(s, s+n); for(int i = 0; i < n; i++) cout << s[i]; return 0; }3.2 字符串与数字转换
// 字符串转数字 int num = stoi(str); // 转为int long num = stol(str); // 转为long long long num = stoll(str); // 转为long long // 数字转字符串 string str = to_string(num);4. 数据结构模板
4.1 优先队列（堆）
// 小顶堆 priority_queue<int, vector<int>, greater<int>> q; // 大顶堆 priority_queue<int> q;优先队列在Dijkstra算法中非常有用。我曾用它在蓝桥杯比赛中解决了一道最短路径问题，比普通队列快了3倍。
4.2 并查集
int fa[MAXN]; void init() { for(int i = 1; i <= MAXN; i++) fa[i] = i; } int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); } void merge(int x, int y) { fa[find(x)] = find(y); }并查集的路径压缩优化能让查找操作接近O(1)。在解决连通性问题时，这个模板是我的首选。
5. 动态规划模板
5.1 01背包
int dp[MAXW]; for(int i = 1; i <= n; i++) { for(int j = W; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j-w[i]] + v[i]); } }5.2 最长上升子序列
int dp[MAXN], a[MAXN]; for(int i = 1; i <= n; i++) { dp[i] = 1; for(int j = 1; j < i; j++) { if(a[j] < a[i]) dp[i] = max(dp[i], dp[j]+1); } }对于n>1e5的情况，可以用贪心+二分优化到O(nlogn)：
vector<int> d; d.push_back(a[1]); for(int i = 2; i <= n; i++) { if(a[i] > d.back()) d.push_back(a[i]); else *lower_bound(d.begin(), d.end(), a[i]) = a[i]; }6. 图论算法
6.1 Dijkstra最短路径
typedef pair<int, int> PII; priority_queue<PII, vector<PII>, greater<PII>> q; int dist[MAXN]; memset(dist, 0x3f, sizeof dist); dist[s] = 0; q.push({0, s}); while(!q.empty()) { auto t = q.top(); q.pop(); int u = t.second; if(vis[u]) continue; vis[u] = true; for(auto &e : G[u]) { int v = e.to, w = e.w; if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w; q.push({dist[v], v}); } } }6.2 Kruskal最小生成树
struct Edge { int u, v, w; bool operator<(const Edge &e) const { return w < e.w; } } edges[MAXM]; int fa[MAXN]; int find(int x) { /* 并查集find函数 */ } int kruskal() { sort(edges, edges+m); int res = 0, cnt = 0; for(int i = 0; i < m; i++) { int u = edges[i].u, v = edges[i].v; int fu = find(u), fv = find(v); if(fu != fv) { fa[fu] = fv; res += edges[i].w; cnt++; } } return cnt == n-1 ? res : -1; }7. 实用技巧
7.1 快速幂
long long fastpow(long long a, long long n, long long mod) { long long res = 1; while(n) { if(n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; }7.2 离散化
sort(a, a+n); int size = unique(a, a+n) - a; for(int i = 0; i < n; i++) { a[i] = lower_bound(a, a+size, a[i]) - a + 1; }8. 竞赛经验分享
在ACM/蓝桥杯等比赛中，我总结出几点经验：
- 先写暴力解法保底分，再优化
- 注意数据范围，选择合适算法
- 多用预处理和记忆化减少重复计算
- 边界条件要特别小心（如n=0,1的情况）
记得去年蓝桥杯有一题，我因为没处理n=0的边界情况丢了20分。从那以后，我都会特意检查边界条件。