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和cout2. 数学相关模板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[N1]; 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[N1]; bool visit[N1]; 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)。我在实际比赛中发现当n1e7时欧拉筛比埃筛快约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, sn); 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_queueint, vectorint, greaterint q; // 大顶堆 priority_queueint 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); } }对于n1e5的情况可以用贪心二分优化到O(nlogn)vectorint 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 pairint, int PII; priority_queuePII, vectorPII, greaterPII 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, edgesm); 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, an); int size unique(a, an) - a; for(int i 0; i n; i) { a[i] lower_bound(a, asize, a[i]) - a 1; }8. 竞赛经验分享在ACM/蓝桥杯等比赛中我总结出几点经验先写暴力解法保底分再优化注意数据范围选择合适算法多用预处理和记忆化减少重复计算边界条件要特别小心如n0,1的情况记得去年蓝桥杯有一题我因为没处理n0的边界情况丢了20分。从那以后我都会特意检查边界条件。