算法竞赛模板

Misc

inline void fastio(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

数学

快速幂+求逆元+快速求组合数

ll fac[N], inv[N];
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void init_fac(){
    fac[0]=1;
    for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
    inv[N-1]=qpow(fac[N-1],mod-2);
    for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(int n,int k){
    if(k<0||k>n)return 0;
    return fac[n]*inv[k]%mod*inv[n-k]%mod;
}

图论部分

链式前向星+堆优化dijkstra

void add_edge(int u,int v,int w){
	to[++_]=v;
	nxt[_]=frm[u];
	frm[u]=_;
	val[_]=w;
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;
int vis[N],dis[N];
void dijkstra(){
	while(!Q.empty()){
		int u=Q.top().second;
		Q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=frm[u];i;i=nxt[i]){
			if(dis[to[i]]>dis[u]+val[i]){
				dis[to[i]]=dis[u]+val[i];
				Q.push(make_pair(dis[to[i]],to[i]));
			}
		}
	}
}
int main(){
	for(int i=1;i<=n;i++){
		dis[i]=INF;
	}
	dis[1]=0;
	Q.push(make_pair(0,1));
	dijkstra();
	return 0;
}

EK 最大流

#include<bits/stdc++.h>
using namespace std;
#define int long long
int _=1,frm[M],to[M],nxt[M],val[M];
int cn[N][N];
void add_edge(int u,int v,int w){
	to[++_]=v;
	nxt[_]=frm[u];
	frm[u]=_;
	val[_]=w;
}
bool vis[N];
int pre[M];
int flow[N];
int ans=0;
bool bfs(){
    memset(vis,0,sizeof(vis));
    memset(flow,0x3f,sizeof(flow));
    bool ret=0;
    queue<int> Q;
    Q.push(s);
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(int i=frm[u];i;i=nxt[i]){
            int v=to[i],w=val[i];
            if(val[i]<=0||vis[v])continue;
            flow[v]=min(flow[u],w);
            pre[v]=i;
            vis[v]=1;
            Q.push(v);
            if(v==t)ret=1;
        }
    }
    return ret;
}
void update(){
    for(int i=t;i!=s;i=to[pre[i]^1]){
		val[pre[i]]-=flow[t];
		val[pre[i]^1]+=flow[t];
	}
}
signed main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        if(!cn[u][v]){
            add_edge(u,v,w);
            cn[u][v]=_;
            add_edge(v,u,0);
        }else{
            val[cn[u][v]]+=w;
        }
    }
    while(bfs()){update();ans+=flow[t];}
    cout<<ans<<endl;
    return 0;
}

最小费用最大流

int n,m,s,t;
int _=1,frm[M],to[M],nxt[M],val[M],cost[M];
void add_edge(int u,int v,int w,int c){
	nxt[++_]=frm[u];frm[u]=_;to[_]=v;val[_]=w;cost[_]=c;
	nxt[++_]=frm[v];frm[v]=_;to[_]=u;val[_]=0;cost[_]=-c;
}
int d[N];bool vis[N];
int flow[N],pre[N];
inline bool spfa(){
	queue<int> Q;
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	memset(pre,-1,sizeof(pre));
	d[s]=0;flow[s]=inf;vis[s]=1;
	Q.push(s);
	while(Q.size()){
		int u=Q.front();Q.pop();vis[u]=0;
		for(int i=frm[u];i;i=nxt[i]){
			int v=to[i];
			if(val[i]&&d[v]>d[u]+cost[i]){
				d[v]=d[u]+cost[i];
				flow[v]=min(flow[u],val[i]);
				pre[v]=i;
				if(!vis[v]){
					vis[v]=1;
					Q.push(v);
				}
			}
		}
	}
	return d[t]!=inf;
}
signed main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,w,c;cin>>u>>v>>w>>c;
		add_edge(u,v,w,c);
	}
	int maxflow=0,mincost=0;
	while(spfa()){
		maxflow+=flow[t];
		mincost+=flow[t]*d[t];
		for(int i=t;i!=s;i=to[pre[i]^1]){
			val[pre[i]]-=flow[t];
			val[pre[i]^1]+=flow[t];
		}
	}
	cout<<maxflow<<" "<<mincost<<endl;
}

数据结构

ST 表

lg[1]=0;lg[2]=1;for(int i=3;i<=n;i++)lg[i]=lg[i/2]+1;
for(int i=1;i<=n;i++)f[i][0]=read();
for(int k=1;k<=20;k++){
	for(int i=1;i+(1<<k)-1<=n;i++){
		f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
	}
}
while(m--){
	int l,r;l=read();r=read();
	int s=lg[r-l+1];
	cout<<max(f[l][s],f[r-(1<<s)+1][s])<<'\n';
}

字符串

kmp

int main(){
    cin>>s1;
    cin>>s2;
    int n=strlen(s1);
    int m=strlen(s2);
    nxt[0]=0;
    int j=0;
    for(int i=1;i<m;i++){
        while(j>0&&s2[i]!=s2[j])j=nxt[j];
        if(s2[i]==s2[j]){
            j++;
        }
        nxt[i+1]=j;
    }
    j=0;
    for(int i=0;i<n;i++){
        while(j>0&&s1[i]!=s2[j])j=nxt[j];
        if(s1[i]==s2[j]){
            j++;
        }
        if(j==m){
            cout<<i-m+2<<endl;
        }
    }
    for(int i=1;i<=m;i++){
        cout<<nxt[i]<<" ";
    }
    cout<<endl;
    return 0;
}