C++CSP-J/S必背模板
1 头文件 & 快读快写
#include <bits/stdc++.h>
using namespace std;
using int64 = long long; // 64 位整数
using pii = pair<int,int>;
using pll = pair<int64,int64>;
constexpr int MAXN = 1e6 + 10;
constexpr int INF = 0x3f3f3f3f;
constexpr double EPS = 1e-8;
// ---------- 快读 ----------
inline int read(){int x=0,f=1; char ch=getchar();while(!isdigit(ch)){ if(ch=='-')f=-1; ch=getchar(); }while(isdigit(ch)){ x=x*10+(ch^48); ch=getchar(); }return x*f;
}
2 数学工具箱
2.1 快速幂 & 逆元
int64 qpow(int64 a,int64 b,int64 mod){int64 res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod; b>>=1;}return res;
}
int64 inv(int64 a,int64 mod){ return qpow(a,mod-2,mod); } // 要求 mod 为质数
2.2 线性筛素数
bool vis[MAXN]; int prime[MAXN],cnt;
void sieve(int n){for(int i=2;i<=n;++i){if(!vis[i]) prime[cnt++]=i;for(int j=0;j<cnt&&i*prime[j]<=n;++j){vis[i*prime[j]]=1;if(i%prime[j]==0) break;}}
}
2.3 组合数（小范围 n≤1000）
int C[1010][1010];
void init_C(int n,int mod){for(int i=0;i<=n;++i){C[i][0]=1;for(int j=1;j<=i;++j)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;}
}
3 数据结构模板
3.1 并查集（路径压缩 + 按秩合并）
int fa[MAXN], rk[MAXN];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){x=find(x); y=find(y);if(x==y) return;if(rk[x]<rk[y]) swap(x,y);fa[y]=x; if(rk[x]==rk[y]) ++rk[x];
}
3.2 树状数组（单点加 + 区间和）
template<int SZ>
struct Fenwick{int64 c[SZ];void add(int p,int64 v){ for(;p<SZ;p+=p&-p) c[p]+=v; }int64 ask(int p){ int64 res=0; for(;p;p-=p&-p) res+=c[p]; return res; }int64 ask(int l,int r){ return ask(r)-ask(l-1); }
};
3.3 线段树（区间加 + 区间和）
struct SegTree{struct Node{ int64 sum,add; } tr[MAXN<<2];void pushup(int p){ tr[p].sum = tr[p<<1].sum + tr[p<<1|1].sum; }void pushdown(int p,int l,int r){if(!tr[p].add) return;int mid=(l+r)>>1;apply(p<<1,l,mid,tr[p].add);apply(p<<1|1,mid+1,r,tr[p].add);tr[p].add=0;}void apply(int p,int l,int r,int64 v){tr[p].sum += (r-l+1)*v;tr[p].add += v;}void add(int p,int l,int r,int L,int R,int64 v){if(L<=l && r<=R){ apply(p,l,r,v); return; }pushdown(p,l,r);int mid=(l+r)>>1;if(L<=mid) add(p<<1,l,mid,L,R,v);if(R>mid) add(p<<1|1,mid+1,r,L,R,v);pushup(p);}int64 ask(int p,int l,int r,int L,int R){if(L<=l && r<=R) return tr[p].sum;pushdown(p,l,r);int mid=(l+r)>>1; int64 res=0;if(L<=mid) res += ask(p<<1,l,mid,L,R);if(R>mid) res += ask(p<<1|1,mid+1,r,L,R);return res;}
};
4 图论模板
4.1 链式前向星
struct Edge{ int to,nxt,w; } e[MAXN<<1];
int head[MAXN],tot=0;
void addEdge(int u,int v,int w=0){e[++tot]={v,head[u],w}; head[u]=tot;
}
4.2 单源最短路径（Dijkstra + 堆优化）
int64 dis[MAXN]; bool vis[MAXN];
void dijkstra(int s,int n){fill(dis,dis+n+1,LLONG_MAX);fill(vis,vis+n+1,false);priority_queue<pll,vector<pll>,greater<pll>> q;dis[s]=0; q.emplace(0,s);while(!q.empty()){auto [d,u]=q.top(); q.pop();if(vis[u]) continue;vis[u]=true;for(int i=head[u];i;i=e[i].nxt){int v=e[i].to,w=e[i].w;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.emplace(dis[v],v);}}}
}
4.3 Tarjan 强连通分量
int dfn[MAXN],low[MAXN],col[MAXN],stk[MAXN],top,scc;
bool instk[MAXN]; int tim=0;
void tarjan(int u){dfn[u]=low[u]=++tim;stk[++top]=u; instk[u]=true;for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(instk[v]) low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u]){++scc; int v;do{v=stk[top--];instk[v]=false;col[v]=scc;}while(v!=u);}
}
5 字符串模板
5.1 KMP
int nxt[MAXN];
void getNext(const string& s){int n=s.size(),j=0;nxt[0]=0;for(int i=1;i<n;++i){while(j && s[i]!=s[j]) j=nxt[j-1];if(s[i]==s[j]) ++j;nxt[i]=j;}
}
vector<int> kmp(const string& s,const string& p){vector<int> res;int n=s.size(),m=p.size();getNext(p); int j=0;for(int i=0;i<n;++i){while(j && s[i]!=p[j]) j=nxt[j-1];if(s[i]==p[j]) ++j;if(j==m){ res.push_back(i-m+1); j=nxt[j-1]; }}return res;
}
6 动态规划模板
6.1 01背包
int64 dp[MAXN];
void knapsack(int n,int W,vector<int>& w,vector<int>& v){fill(dp,dp+W+1,0);for(int i=0;i<n;++i)for(int j=W;j>=w[i];--j)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
6.2 区间 DP（石子合并）
int64 f[510][510], s[510];
int64 mergeStones(int n){for(int len=2;len<=n;++len)for(int l=1;l+len-1<=n;++l){int r=l+len-1;f[l][r]=1e18;for(int k=l;k<r;++k)f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);}return f[1][n];
}
7 数学/几何模板
7.1 最大公约数 & 扩展欧几里得
int64 gcd(int64 a,int64 b){ return b?gcd(b,a%b):a; }
int64 exgcd(int64 a,int64 b,int64& x,int64& y){if(!b){ x=1; y=0; return a; }int64 d=exgcd(b,a%b,y,x);y-=a/b*x; return d;
}
7.2 面积法判点是否在三角形内
double area(double x1,double y1,double x2,double y2,double x3,double y3){return fabs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))/2;
}
bool inTri(double x,double y,double x1,double y1,double x2,double y2,double x3,double y3){double s=area(x1,y1,x2,y2,x3,y3);double s1=area(x,y,x2,y2,x3,y3);double s2=area(x1,y1,x,y,x3,y3);double s3=area(x1,y1,x2,y2,x,y);return fabs(s-(s1+s2+s3)) < EPS;
}
8 复赛文件操作模板
int main(){freopen("xxx.in","r",stdin);freopen("xxx.out","w",stdout);/* 原题逻辑 */return 0;
}
9 调试宏（赛场上慎用）
#ifdef LOCAL#define dbg(...) fprintf(stderr,__VA_ARGS__)
#else#define dbg(...)
#endif
10 一行主函数模板（极短题）
int main(){ int n; cin>>n; cout<<fixed<<setprecision(2)<</*...*/<<endl; }