目录：
1.堆
2.扩展中国剩余定理
3.线段树
4.并查集
5.最小生成树
6.最短路
7.离散化
8.tarjan缩点
9.KMP算法
10.高斯消元法
一.堆（stl版）
1.大根堆
#include #include #include #include #include #include using namespace std;priority_queue < int , vector < int > > q;int n;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { int x,y; scanf("%d",&x); if(x==1)//将y插入到堆中 { scanf("%d",&y); q.push(y); } if(x==2)//删除该大根堆内的最大数 { q.pop(); } if(x==3)//输出该大根堆内的最大数 { printf("%d\n",q.top()); } }}
2.小根堆
#include #include #include #include #include #include using namespace std;priority_queue < int , vector < int > , greater < int > > q;int n;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { int x,y; scanf("%d",&x); if(x==1)//将y插入到堆中 { scanf("%d",&y); q.push(y); } if(x==2)//删除该小根堆内的最小数 { q.pop(); } if(x==3)//输出该小根堆内的最小数 { printf("%d\n",q.top()); } }}
二.扩展中国剩余定理
#include #include #include #include #include using namespace std;long long n,ai[100001],bi[100001];long long mul(long long x,long long y,long long p){ long long ans=0; while(y) { if(y&1) ans=(ans+x)%p; x=(x+x)%p; y>>=1; } return ans;}long long exgcd(long long a,long long b,long long &x,long long &y){ if(b==0) { x=1; y=0; return a; } long long cnt=exgcd(b,a%b,x,y); long long idx=x; x=y; y=idx-a/b*y; return cnt;}long long excrt(){ long long x=0,y=0; long long M=bi[1],ans=ai[1]; for(long long i=2;i<=n;i++) { long long a=M,b=bi[i],c=((ai[i]-ans)%b+b)%b; long long gcd=exgcd(a,b,x,y),idx=b/gcd; if(c%gcd!=0) return -1; x=mul(x,c/gcd,idx); ans+=x*M; M*=idx; ans=(ans%M+M)%M; } return (ans%M+M)%M;}int main(){ scanf("%lld",&n); for(long long i=1;i<=n;i++) scanf("%lld%lld",&ai[i],&bi[i]); printf("%lld\n",excrt());}
三.线段树
1.建树
#include #include #include #include #include #include using namespace std;int n,a[100001],sum[400001];void pushup(int k){ sum[k]=sum[k<<1]+sum[k<<1|1];}void build(int l,int r,int k){ if(l==r) { sum[k]=a[l]; return; } int mid=(l+r)>>1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); pushup(k);}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,n,1);}
2.单点修改（单点加同理）
#include #include #include #include #include #include using namespace std;int n,a[100001],sum[400001],m;void pushup(int k){ sum[k]=sum[k<<1]+sum[k<<1|1];}void update(int l,int r,int p,int v,int k){ if(l==r) { sum[k]=v; return; } int mid=(l+r)>>1; if(mid>=p) update(l,mid,p,v,k<<1); if(mid
3.区间加
#include #include #include #include #include #include using namespace std;int n,a[100001],sum[400001],m,tag[400001];void pushup(int k){ sum[k]=sum[k<<1]+sum[k<<1|1];}void lazy(int l,int r,int v,int k){ tag[k]+=v; sum[k]+=(r-l+1)*v;}void pushdown(int l,int r,int k){ int mid=(l+r)>>1; lazy(l,mid,tag[k],k<<1); lazy(mid+1,r,tag[k],k<<1|1); tag[k]=0;}void update(int l,int r,int x,int y,int v,int k){ if(x<=l&&r<=y) { sum[k]+=(r-l+1)*v; tag[k]+=v; return; } int mid=(l+r)>>1; pushdown(l,r,k); if(mid>=x) update(l,mid,x,y,v,k<<1); if(mid
4.区间修改
#include #include #include #include #include #include using namespace std;int n,a[100001],sum[400001],m,tag[400001];void pushup(int k){ sum[k]=sum[k<<1]+sum[k<<1|1];}void lazy(int l,int r,int v,int k){ tag[k]=v; sum[k]=(r-l+1)*v;}void pushdown(int l,int r,int k){ int mid=(l+r)>>1; lazy(l,mid,tag[k],k<<1); lazy(mid+1,r,tag[k],k<<1|1); tag[k]=0;}void update(int l,int r,int x,int y,int v,int k){ if(x<=l&&r<=y) { sum[k]=(r-l+1)*v; tag[k]=v; return; } int mid=(l+r)>>1; pushdown(l,r,k); if(mid>=x) update(l,mid,x,y,v,k<<1); if(mid
5.单点查询
#include #include #include #include #include #include using namespace std;int n,a[100001],sum[400001],m,tag[400001];void lazy(int l,int r,int v,int k){ tag[k]=v; sum[k]=(r-l+1)*v;}void pushdown(int l,int r,int k){ int mid=(l+r)>>1; lazy(l,mid,tag[k],k<<1); lazy(mid+1,r,tag[k],k<<1|1); tag[k]=0;}int query(int l,int r,int p,int k){ if(l==r) return sum[k]; int mid=(l+r)>>1,ans=0; pushdown(l,r,k); if(mid>=p) ans+=query(l,mid,p,k<<1); if(mid
6.区间查询
#include #include #include #include #include #include using namespace std;int n,a[100001],sum[400001],m,tag[400001];void lazy(int l,int r,int v,int k){ tag[k]=v; sum[k]=(r-l+1)*v;}void pushdown(int l,int r,int k){ int mid=(l+r)>>1; lazy(l,mid,tag[k],k<<1); lazy(mid+1,r,tag[k],k<<1|1); tag[k]=0;}int query(int l,int r,int x,int y,int k){ if(x<=l&&r<=y) return sum[k]; int mid=(l+r)>>1,ans=0; pushdown(l,r,k); if(mid>=x) ans+=query(l,mid,x,y,k<<1); if(mid
四.并查集
1.路径压缩
#include #include #include #include #include #include using namespace std;int n,m,f[10001];int find(int p){ if(p!=f[p]) f[p]=find(f[p]); return f[p];}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=n;i++) { int x=find(i); printf("%d\n",x); }}
2.普通合并
#include #include #include #include #include #include using namespace std;int n,m,f[10001];int find(int p){ if(p!=f[p]) f[p]=find(f[p]); return f[p];}void merge(int x,int y){ int fx=find(x),fy=find(y); if(fx!=fy) f[fx]=fy;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); merge(x,y); }}
3.启发式合并
#include #include #include #include #include #include using namespace std;int n,m,f[10001],s[10001];int find(int p){ if(p!=f[p]) f[p]=find(f[p]); return f[p];}void merge(int x,int y){ int fx=find(x),fy=find(y); if(s[fx]
五.最小生成树
1.Prim算法
#include #include #include #include #include #include using namespace std;int n,l[101][101],minn[101];bool used[101];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;i++) scanf("%d",&l[i][j]); memset(minn,999999999,sizeof(minn)); minn[1]=0; memset(u,1,sizeof(u)); for(int i=1;i<=n;i++) { int k=0; for(int j=1;j<=n;j++) if(u[j]&&minn[j]
2.Kruskal算法
#include #include #include #include #include #include using namespace std;int n,f[101],m,tot,k,idx;struct Edge{ int x,y,v;}a[9001];bool cmp(const Edge &a,const Edge &b){ return a.v
六.最短路
1.Floyed算法
#include #include #include #include #include #include using namespace std;int n,f[101][101],s,t;int main(){ scanf("%d",&n); memset(f,0x7f,sizeof(f)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&f[i][j]); scanf("%d%d",&s,&t); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((i!=j)&&(j!=k)&&(j!=k)&&f[i][k]+f[k][j]
2.Dijkstra算法
#include #include #include #include #include #include using namespace std;int f[101][101],n,s,t,minn[101];bool vis[101];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&f[i][j]); scanf("%d%d",&s,&t); for(int i=1;i<=n;i++) minn[i]=f[s][i]; minn[s]=0; vis[s]=1; for(int i=1;i
3.Dijkstra堆优化
#include #include #include #include #include #include using namespace std;#define inf 0x3f3f3f3fint t,c,ts,te,to[12401],head[12401],nxt[12401],idx,len[12401],minn[3001];bool vis[3001];priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > q;void addedge(int a,int b,int c){ to[++idx]=b; len[idx]=c; nxt[idx]=head[a]; head[a]=idx;}int main(){ scanf("%d%d%d%d",&t,&c,&ts,&te); for(int i=1;i<=c;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); addedge(b,a,c); } memset(minn,inf,sizeof(minn)); minn[ts]=0; q.push(make_pair(0,ts)); while(!q.empty()) { int p=q.top().second; q.pop(); if(vis[p]) continue; vis[p]=1; for(int i=head[p];i;i=nxt[i]) { if(minn[to[i]]>minn[p]+len[i]) { minn[to[i]]=minn[p]+len[i]; q.push(make_pair(minn[to[i]],to[i])); } } } printf("%d",minn[te]); return 0;}
4.Spfa算法及判负环（以洛谷模板为例）
#include #include #include #include #include #include using namespace std;int n,m,t,head[100001],idx,dis[100001],cnt[100001],to[100001],nxt[100001],len[100001];bool vis[100001];void addedge(int x,int y,int z){ to[++idx]=y; nxt[idx]=head[x]; len[idx]=z; head[x]=idx;}bool spfa(int s){ memset(vis,0,sizeof(vis)); memset(dis,0x3f3f3f3f,sizeof(dis)); memset(cnt,0,sizeof(cnt)); queue < int > q; q.push(s); vis[s]=1; dis[s]=0; while(!q.empty()) { int p=q.front(); q.pop(); vis[p]=0; for(int i=head[p];i;i=nxt[i]) { if(dis[to[i]]>dis[p]+len[i]) { dis[to[i]]=dis[p]+len[i]; if(!vis[to[i]]) { q.push(to[i]); vis[to[i]]=1; cnt[to[i]]++; if(cnt[to[i]]>=n)//判负环部分，若一个点入队大于n次，则它一定在一个环内 return 1; } } } } return 0;}int main(){ scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); idx=0; memset(head,0,sizeof(head)); for(int i=1,u,v,w;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); if(w<0) addedge(u,v,w); else { addedge(u,v,w); addedge(v,u,w); } } if(spfa(1)==1) printf("YE5\n"); else printf("N0\n"); }}
七.离散化
#include #include #include #include #include #include using namespace std;int a[10001],b[10001],n,idx;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[++idx]=a[i]; } sort(b+1,b+idx+1); idx=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+idx+1,a[i])-b;}
八.tarjan缩点
int z[100001],dep[100001],low[100001],top,ans,cnt,neww[100001],f[100001];bool inz[100001];void tarjan(int x){ inz[x]=1; vis[x]=1; dep[x]=low[x]=++cnt; z[++top]=x; for(int i=head[x];i;i=nxt[i]) { if(dep[to[i]]==0) { tarjan(to[i]); low[x]=min(low[x],low[to[i]]); } else if(inz[to[i]]!=0) low[x]=min(low[x],dep[to[i]]); } if(dep[x]==low[x]) { ans++; int t; do { t=z[top--]; neww[ans]++; f[t]=ans; inz[t]=0; }while(t!=x); }} 九.KMP算法（以洛谷模板为例）
#include #include #include #include #include #include using namespace std;int nxt[1000001],k,ans[1000001],cnt,l1,l2;char s1[1000001],s2[1000001];void getnxt(){ for(int i=2;i<=l2;i++) { while(k!=0&&s2[i]!=s2[k+1]) k=nxt[k]; if(s2[i]==s2[k+1]) k++; nxt[i]=k; }}void KMP(){ for(int i=1;i<=l1;i++) { while(k!=0&&s1[i]!=s2[k+1]) k=nxt[k]; if(s1[i]==s2[k+1]) k++; if(k==l2) ans[++cnt]=i-l2+1; }}int main(){ scanf("%s%s",s1+1,s2+1); l1=strlen(s1+1); l2=strlen(s2+1); nxt[1]=0; getnxt(); k=0; KMP(); for(int i=1;i<=cnt;i++) printf("%d\n",ans[i]); for(int i=1;i<=l2;i++) printf("%d ",nxt[i]);}
十.高斯消元法
#include #include #define eps 1e-8int n;double a[105][105],idx2;int main(){ scanf("%d",&n); for(int i=0;i