算法模板

23 年 9 月 13 日 星期三
596 字
3 分钟

快读：

cpp
namespace FastIO{
	char *p1,*p2,buf[1<<14];
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<14),stdin),p1==p2)?EOF:*p1++)
	template <typename T>
	inline void read(T& x){
    	x=0;
    	register int t=1;
    	register char ch=getchar();
    	while(ch<'0'||ch>'9'){
        	if(ch=='-')t=-1;
        	ch=getchar();
    	}
    	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    	x*=t;
	}
	template <typename T>
	void write(T x){
    	if(x<0)putchar('-'),x=-x;
    	if(x>9)write(x/10);
    	putchar(x%10^48);
	}
	template <typename T>
	inline void writeln(T x,char sep='\n'){
		write(x);putchar(sep);
	}
}
using namespace FastIO;

ST表：

cpp
#include<bits/stdc++.h>
using namespace FastIO;
using namespace std;
const int N=1e6+10;
int n,T,i,j,x,y,a[N][21];
int Query(int x,int y){
    int z=__lg(y-x+1);
    return max(a[x][z],a[y-(1<<z)+1][z]);
}
int main(){
   	read(n);read(T);
    for(i=1;i<=n;i++)read(a[i][0]);
    for(j=1;j<=21;j++)
        for(i=1;i<=n-(1<<j)+1;i++)
            a[i][j]=max(a[i][j-1],a[i+(1<<(j-1))][j-1]);
	while(T--)read(x),read(y),writeln(Query(x,y));
}

线段树（维护加法和乘法）：

cpp
#include<bits/stdc++.h>
#define ls x<<1
#define rs x<<1|1
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll n,m,mod,i,op,x,y,z,a[N];
struct Node{ll sum,l,r,Mul,Add;}Tree[N];
void Build(ll x,ll l,ll r){
	Tree[x].l=l,Tree[x].r=r;Tree[x].Mul=1;
	if(l==r){Tree[x].sum=a[l]%mod;return;}
	ll mid=(l+r)>>1;
	Build(ls,l,mid);Build(rs,mid+1,r);
	Tree[x].sum=(Tree[ls].sum+Tree[rs].sum)%mod;
}
void Spread(ll x){
    Tree[ls].sum=(Tree[x].Mul*Tree[ls].sum+((Tree[ls].r-Tree[ls].l+1)*Tree[x].Add)%mod)%mod;
    Tree[rs].sum=(Tree[x].Mul*Tree[rs].sum+(Tree[x].Add*(Tree[rs].r-Tree[rs].l+1))%mod)%mod;
    Tree[ls].Mul=(Tree[ls].Mul*Tree[x].Mul)%mod;
    Tree[rs].Mul=(Tree[rs].Mul*Tree[x].Mul)%mod;
	Tree[ls].Add=(Tree[ls].Add*Tree[x].Mul+Tree[x].Add)%mod;
    Tree[rs].Add=(Tree[rs].Add*Tree[x].Mul+Tree[x].Add)%mod;
    Tree[x].Mul=1;Tree[x].Add=0;
}
void Add(ll x,ll l,ll r,ll k){
	if(Tree[x].l>=l&&Tree[x].r<=r){
		Tree[x].Add=(Tree[x].Add+k)%mod;
		Tree[x].sum=(Tree[x].sum+k*(Tree[x].r-Tree[x].l+1))%mod;
		return;
	}
	Spread(x);
	Tree[x].sum=(Tree[ls].sum+Tree[rs].sum)%mod;
	ll mid=(Tree[x].l+Tree[x].r)>>1;
	if(l<=mid)Add(ls,l,r,k);
	if(mid<r)Add(rs,l,r,k);
	Tree[x].sum=(Tree[ls].sum+Tree[rs].sum)%mod;
}
void Mul(ll x,ll l,ll r,ll k){
	if(Tree[x].l>=l&&Tree[x].r<=r){
		Tree[x].Add=(Tree[x].Add*k)%mod;
		Tree[x].Mul=(Tree[x].Mul*k)%mod;
		Tree[x].sum=(Tree[x].sum*k)%mod;
		return;
	}
	Spread(x);
    Tree[x].sum=Tree[ls].sum+Tree[rs].sum;
	ll mid=(Tree[x].l+Tree[x].r)>>1;
	if(l<=mid)Mul(ls,l,r,k);
	if(mid<r)Mul(rs,l,r,k);
	Tree[x].sum=(Tree[ls].sum+Tree[rs].sum)%mod;
}
ll Query(ll x,ll l,ll r){
	if(Tree[x].l>=l&&Tree[x].r<=r)return Tree[x].sum;
	Spread(x);
	ll v=0,mid=(Tree[x].l+Tree[x].r)>>1;
	if(l<=mid)v=(v+Query(ls,l,r))%mod;
	if(mid<r)v=(v+Query(rs,l,r))%mod;
	return v;
}
int main(){
	cin>>n>>m>>mod;
	for(i=1;i<=n;i++)cin>>a[i];
	Build(1,1,n);
	for(i=1;i<=m;i++){
		cin>>op;
		if(op==1)cin>>x>>y>>z,Mul(1,x,y,z);
		else if(op==2)cin>>x>>y>>z,Add(1,x,y,z);
		else cin>>x>>y,cout<<Query(1,x,y)<<'\n';
    }
}

快速幂：

cpp
const ll mod=/*模数*/;
ll qpow(ll x,ll y){
	ll s=1;
	while(y){
		if(y&1)s=s*x%mod;
		y>>=1;x=x*x%mod;
	}
	return s;
}

Trie树：

cpp
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10,M=70;
int T,q,n,i,j,l,f[N][M],sum[N];
char s[N];
int _(char x){
    if(x>='A'&&x<='Z')return x-65;
    else if(x>='a'&&x<='z')return x-71;
    else return x+4;
}
void Add(char str[]){
    int p=0,len=strlen(str),i,c;
    for(i=0;i<len;i++){
        c=_(str[i]);
        if(!f[p][c])f[p][c]=++l;
        p=f[p][c];
        sum[p]++;
    }
}
int Query(char str[]){
    int p=0,len=strlen(str),i,c;
    for(i=0;i<len;i++){
        c=_(str[i]);
        if(!f[p][c])return 0;
        p=f[p][c];
    }
    return sum[p];
}
int main(){
    cin>>T;
    while(T--){
        for(i=0;i<=l;i++)for(j=0;j<=122;j++)f[i][j]=0;
        for(i=0;i<=l;i++)sum[i]=0;
        l=0;
        cin>>n>>q;
        for(i=1;i<=n;i++)cin>>s,Add(s);
        for(i=1;i<=q;i++)cin>>s,cout<<Query(s)<<'\n';
    }
}

Floyd：

cpp
int main(){
	cin>>n>>m;memset(f,0x3f,sizeof f);
	for(i=1;i<=m;i++)cin>>x>>y>>z,f[x][y]=f[y][x]=z;
	for(i=1;i<=n;i++)f[i][i]=0;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(f[i][k]+f[k][j]<f[i][j])
                    f[i][j]=f[i][k]+f[k][j];
	for(i=1;i<=n;i++,cout<<'\n')
		for(j=1;j<=n;j++)
			if(f[i][j]!=2139062143)cout<<f[i][j]<<' ';
			else cout<<0<<' ';
}

并查集：

cpp
#include<bits/stdc++.h>
using namespace std;
int n,T,k,x,y,i,j,f[10010];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int main(){
    cin>>n>>T;
    for(i=1;i<=n;i++)f[i]=i;
    while(T--){
        cin>>k>>x>>y;
        if(k==1)f[find(x)]=find(y);
        else
            if(find(x)==find(y))cout<<"Y\n";
            else cout<<"N\n";
    }
}

KMP：

cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int i,j,l1,l2,f[N];
char a[N],b[N];
int main(){
	cin>>a+1>>b+1;l1=strlen(a+1);l2=strlen(b+1);
	for(i=2;i<=l2;i++){
		while(j&&b[i]!=b[j+1])j=f[j];
		if(b[j+1]==b[i])j++;
		f[i]=j;
	}
	j=0;
	for(i=1;i<=l1;i++){
		while(j>0&&b[j+1]!=a[i])j=f[j];
		if(b[j+1]==a[i])j++;
		if(j==l2)cout<<i-l2+1<<'\n',j=f[j];
	}
	for(i=1;i<=l2;i++)cout<<f[i]<<' ';
}

SPFA：死了，换Dijkstra。

Dijkstra：

cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=5e5+10,inf=INT_MAX;
struct Edge{int to,nxt,val;}E[M];
int n,m,s,i,x,y,z,cnt,head[N],dis[N],vis[N];
void add(int x,int y,int z){E[++cnt]={y,head[x],z};head[x]=cnt;}
struct Node{
    int x,y;
    bool operator<(const Node &y)const{return y.x<x;}
};
priority_queue<Node>q;
void Dij(){
	int u,v,i;dis[s]=0;q.push({0,s});
	while(!q.empty()){
		u=q.top().y;x=q.top().x;q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(i=head[u];i;i=E[i].nxt){
			v=E[i].to;
			if(dis[v]>dis[u]+E[i].val){
				dis[v]=dis[u]+E[i].val;
				if(!vis[v])q.push({dis[v],v});
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	for(i=1;i<=n;i++)dis[i]=inf;
	for(i=1;i<=m;i++)cin>>x>>y>>z,add(x,y,z);
	Dij();
	for(i=1;i<=n;i++)cout<<dis[i]<<' ';
}

CRT：

cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,i,x,y,a[16],m[16],f[16],mul=1,ans;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    int z=x;x=y,y=z-y*(a/b);
}
int main(){
    cin>>n;
    for(i=1;i<=n;i++)cin>>x>>a[i],m[i]=x,mul*=x;
    for(i=1;i<=n;i++)f[i]=mul/m[i],x=y=0,exgcd(f[i],m[i],x,y),ans+=a[i]*f[i]*(x<0?x+m[i]:x);
    cout<<ans%mul;
}

逆元：

cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3e6+10;
ll n,mod,i,inv[N];
int main(){
    cin>>n>>mod;inv[1]=1;
    cout<<1<<'\n';
    for(i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod,cout<<inv[i]<<'\n';
}

单调队列：

cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,i,l,r,a[N],q1[N],q2[N];
int main(){
    cin>>n>>m;
    for(i=1;i<=n;i++)cin>>a[i];
	l=1;r=0;
    for(i=1;i<=n;i++){
        while(l<=r&&q1[l]+m<=i)l++;
        while(l<=r&&a[i]<a[q1[r]])r--;
        q1[++r]=i;
        if(i>=m)cout<<a[q1[l]]<<' ';
    }
    cout<<'\n';
    l=1;r=0;
    for(i=1;i<=n;i++){
        while(l<=r&&q2[l]+m<=i)l++;
        while(l<=r&&a[i]>a[q2[r]])r--;
        q2[++r]=i;
        if(i>=m)cout<<a[q2[l]]<<' ';
    }
}

扩展欧拉（abmod  ma^b\mod m）：

cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,m,b,x=1,y,i,flag;
char ch;
ll qpow(ll x,ll y){
	ll s=1;
	for(;y;y>>=1,x=x*x%m)if(y&1)s=s*x%m;
	return s;
}
int main(){
	cin>>a>>m;a%=m;y=m;
	for(i=2;i<=sqrt(y);i++){
		if(y%i)continue;
		x*=i-1;y/=i;
		while(!(y%i))x*=i,y/=i;
	}
	if(y>1)x*=y-1;
	while((ch=getchar())<'0'||ch>'9');
	while(b=b*10+ch-'0',(ch=getchar())>='0'&&ch<='9')if(b>=x)flag=1,b%=x;
	if(b>=x)flag=1,b%=x;
	if(flag)b+=x;
	cout<<qpow(a,b);
}

最小生成树（Kruskal）：

cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll n,m,i,j,s,ans,f[N];
struct Edge{ll x,y,v;}E[N<<1];
ll find(ll x){return f[x]==x?x:f[x]=find(f[x]);}
bool cmp(Edge x,Edge y){return x.v<y.v;}
void Kruskal(){
	int i,fx,fy;
    for(i=1;i<=m;i++){
        fx=find(E[i].x);fy=find(E[i].y);
        if(fx==fy)continue;
        ans+=E[i].v;f[fx]=fy;s++;
        if(s==n-1)break;
    }
}
int main(){
    cin>>n>>m;
    for(i=1;i<=n;i++)f[i]=i;
    for(i=1;i<=m;i++)cin>>E[i].x>>E[i].y>>E[i].v;
    sort(E+1,E+1+m,cmp);
    Kruskal();
    if(s!=n-1)return cout<<"orz",0;
    cout<<ans;
}

文章标题：算法模板

文章作者：Walter_Fang

文章链接：https://blog.walterfang.us.kg/posts/algorithm-template[复制]

最后修改时间：

商业转载请联系站长获得授权，非商业转载请注明本文出处及文章链接，您可以自由地在任何媒体以任何形式复制和分发作品，也可以修改和创作，但是分发衍生作品时必须采用相同的许可协议。
本文采用CC BY-NC-SA 4.0进行许可。