算法竞赛模板

Misc

常用常数

#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f

取消输入输出流同步

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

二分查找边界

while(l<r){
    int mid=(l+r)/2;
    if(check(mid))r=mid;
    else l=mid+1;
}
while(l<r){
    int mid=(l+r+1)/2;
    if(check(mid))l=mid;
    else r=mid-1;
}

三分求函数最大值

const double eps=1e-7;
double f(double x){
    //...
}
int main(){
    cin>>N>>l>>r;
    for(int i=N;i>=0;i--)cin>>a[i];
    while(r-l>eps){
        double mid=(l+r)/2;
        double lmid=mid-eps,rmid=mid+eps;
        if(f(lmid)>f(rmid))r=mid;
        else l=mid;
    }
    printf("%.5f",l);
    return 0;
}

数学

快速幂+快速求组合数

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;
}

求逆元

inline ll inv(ll x){
    return qpow(x,R-2);
}

欧拉函数

int phi(int n) {
    int ans=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0) {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
int n,isp[N],phi[N];
vector<int> primes;
void get_phi(){
    for(int i=2;i<=n;i++)isp[i]=1;
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(isp[i]){
            primes.push_back(i);
            phi[i]=i-1;
        }
        for(int p:primes){
            if(i*p>n)break;
            isp[i*p]=0;
            if(i%p==0){
            // i的质因数分解中已经包含了p，
            // 由phi(n)=n*∏(1-1/p_i)，phi[i*p]=phi[i]*p
                phi[i*p]=phi[i]*p;
                break;
            }else{      //互质，利用欧拉函数的积性
                phi[i*p]=phi[i]*phi[p];
            }
        }
    }
}

图论部分

链式前向星+堆优化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;
}

SPFA找负环

queue<int> Q;
int in_queue[N],cnt[N];
bool spfa(){
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        in_queue[u]=0;
        for(int i=frm[u];i;i=nxt[i]){
            if(dis[to[i]]>dis[u]+val[i]){
                dis[to[i]]=dis[u]+val[i];
                if(!in_queue[to[i]]){
                    Q.push(to[i]);
                    in_queue[to[i]]=1;
                    cnt[to[i]]++;
                    if(cnt[to[i]]>n)return true;
                }
            }
        }
    }
    return false;
}
int main(){
    for(int i=1;i<=n;i++){
        dis[i]=INF;
        cnt[i]=0;
    }
    dis[1]=0;
    Q.push(1);
    in_queue[1]=1;
    if(spfa())printf("存在负环");
    else printf("不存在负环");
    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;
}

数据结构

二维差分

diff[x1][y1] += v
diff[x1][y2+1] -= v
diff[x2+1][y1] -= v
diff[x2+1][y2+1] += v

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';
}

树状数组

#define lowbit(x) ((x)&(-(x)))
int n,m;
void add(int x,int v){
	for(int i=x;i<=n;i+=lowbit(i)){
		tree[i]+=v;
	}
}

int query(int x){
	int ret=0;
	for(int i=x;i;i-=lowbit(i)){
		ret+=tree[i];
	}
	return ret;
}

字符串

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;
}