蒟蒻目前还是提高组选手，模板将会持续更新！

目录：

线段树 对拍 exgcd st 树状数组 树剖 dijsktra spfa tarjan 匈牙利 埃筛 差分树状数组 dinic 快速幂取余

Exgcd

#include<bits/stdc++.h>

using namespace std;

int exgcd(int a,int b,int &x,int &y)

{

    if(b==)

    {

        x=;

        y=;

        return a;

    }

    int r=exgcd(b,a%b,x,y);

    int t = x;

    x=y;

    y=t-a/b*y;

    return r;

}

int main()

{

    int a,b;

    cin>>a>>b;

    int x,y;

    int p=exgcd(a,b,x,y);

    cout<<(x+b)%b<<endl;

    return ;

}

对拍

@echo off

:loop

数据生成器.exe

快速排序.exe

优先队列.exe

fc 快速排序.out 优先队列.out

if not errorlevel  goto loop

pause

线段树

#include <stdio.h>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <algorithm>

#define maxn 100010

using namespace std;

struct point{

    int l,r;

    long long val,mark;

}tr[maxn*];

int m,n;

int a[maxn];

void buildtree(int x,int l,int r)

{

    tr[x].l=l;

    tr[x].r=r;

    if(l==r)

    {

        tr[x].val=a[l];

        return;

    }

    int lch=x*,rch=x*+;

    int mid=(l+r)/;

    buildtree(lch, l, mid);

    buildtree(rch, mid+, r);

    tr[x].val=tr[x*].val+tr[x*+].val;

}

void release(int x)

{

    if(tr[x].mark && tr[x].l<tr[x].r)

    {

        int lch=x*,rch=x*+;

        tr[lch].val+=tr[x].mark*((long long)tr[lch].r-tr[lch].l+);

        tr[lch].mark+=tr[x].mark;

        tr[rch].val+=tr[x].mark*((long long)tr[rch].r-tr[rch].l+);

        tr[rch].mark+=tr[x].mark;

    }

    tr[x].mark=;

}

void modify(int x,int l,int r,long long k)

{

    release(x);

    if(l<=tr[x].l && tr[x].r<=r)

    {

        tr[x].val+=k*((long long)tr[x].r-tr[x].l+);

        tr[x].mark+=k;

        return;

    }

    int mid=(tr[x].l+tr[x].r)/;

    if(l<=mid)

        modify(x*, l, r, k);

    if(mid<r)

        modify(x*+, l, r, k);

    tr[x].val=tr[x*].val+tr[x*+].val;

}

long long query(int x,int l,int r)

{

    release(x);

    if(l<=tr[x].l && tr[x].r<=r)

        return tr[x].val;

    int mid=(tr[x].l+tr[x].r)/;

    long long ans=;

    if(l<=mid)

        ans+=query(x*, l, r);

    if(r>mid)

        ans+=query(x*+, l, r);

    return ans;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

        scanf("%d",&a[i]);

    buildtree(, , n);

    for(int i=;i<=m;i++)

    {

        int op;

        scanf("%d",&op);

        if(op==)

        {

            int x,y;

            long long k;

            scanf("%d%d%lld",&x,&y,&k);

            modify(, x, y, k);

        }

        else

        {

            int x,y;

            scanf("%d%d",&x,&y);

            printf("%lld\n",query(, x, y));

        }

    }

}

树剖

#include<bits/stdc++.h>

#define inf 0x7fffffff

#define ll long long

using namespace std;

#define maxn  600009

int dfn[maxn],cnt,pos[maxn],son[maxn],en[maxn],top[maxn],size[maxn],fa[maxn],deep[maxn];

vector<int> v[maxn];

struct node{

    int l,r;

    int val,mark;

}tr[maxn*];

int n,m,r,mod;

int a[maxn];

void dfs(int rt)

{

    size[rt]=;

    for(int i=;i<v[rt].size();i++)

    {

        int to=v[rt][i];

        if(!size[to])

        {

            fa[to]=rt;

            deep[to]=deep[rt]+;

            dfs(to);

            size[rt]+=size[to];

            if(size[to]>size[son[rt]])son[rt]=to;

        }

    }

}

void dfs(int x,int tp)

{

    top[x]=tp;

    cnt++;

    pos[x]=cnt;

    dfn[cnt]=x;

    if(son[x]!=)dfs(son[x],tp);

    for(int i=;i<v[x].size();i++)

    {

        int to=v[x][i];

        if(!top[to])dfs(to,to);

    }

    en[x]=cnt;

}

void Build(int x,int l,int r)

{

    tr[x].l=l,tr[x].r=r;

    if(l==r)

    {

        tr[x].mark=;

        tr[x].val=a[dfn[l]];

        return;

    }

    int mid=(l+r)>>;

    Build(x*,l,mid);

    Build(x*+,mid+,r);

    tr[x].mark=;

    tr[x].val=tr[x*].val+tr[x*+].val;

    tr[x].val%=mod;

}

void relese(int x)

{

    if(tr[x].mark==||tr[x].l==tr[x].r)return;

    tr[x*].val+=(tr[x*].r-tr[x*].l+)*tr[x].mark;

    tr[x*].mark+=tr[x].mark;

    tr[x*+].val+=(tr[x*+].r-tr[x*+].l+)*tr[x].mark;

    tr[x*+].mark+=tr[x].mark;

    tr[x*].val%=mod;

    tr[x*].mark%=mod;

    tr[x*+].mark%=mod;

    tr[x*+].val%=mod;

    tr[x].mark=;

}

void Add(int x,int l,int r,int val)

{

    if(l<=tr[x].l&&tr[x].r<=r)

    {

        tr[x].val+=(tr[x].r-tr[x].l+)*val;

        tr[x].val%=mod;

        tr[x].mark+=val;

        tr[x].mark%=mod;

        return;

    }

    //cout<<x<<" "<<l<<" "<<r<<endl;

    relese(x);

    int mid=(tr[x].l+tr[x].r)>>;

    if(l<=mid)Add(x*,l,r,val);

    if(r>mid)Add(x*+,l,r,val);

    tr[x].val=tr[x*].val+tr[x*+].val;

    tr[x].val%=mod;

}

int Sum(int x,int l,int r)

{

    if(l<=tr[x].l&&tr[x].r<=r)

    {

        return tr[x].val;

    }

    relese(x);

    int mid=(tr[x].l+tr[x].r)>>;

    int ans=;

    if(l<=mid) ans+=Sum(x*,l,r);

    if(r>mid) ans+=Sum(x*+,l,r);

    ans%=mod;

    return ans;

}

void LCA_add(int x,int y,int val)

{

    while(top[x]!=top[y])

    {

        if(deep[top[x]]<deep[top[y]])swap(x,y);

        Add(,pos[top[x]],pos[x],val);

        x=fa[top[x]];

    }

    //if(x!=y)

    //{

        if(pos[x]>pos[y])swap(x,y);

        Add(,pos[x],pos[y],val);

//    }

}

int LCA_sum(int x,int y)

{

    int res=;

    while(top[x]!=top[y])

    {

        if(deep[top[x]]<deep[top[y]])swap(x,y);

        res+=Sum(,pos[top[x]],pos[x]);

        res%=mod;

        x=fa[top[x]];

    }

    if(pos[x]>pos[y])swap(x,y);

    res+=Sum(,pos[x],pos[y]);

    return res%mod;

}

signed main()

{

    scanf("%d%d%d%d",&n,&m,&r,&mod);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

    }

    for(int i=;i<n;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        v[x].push_back(y);

        v[y].push_back(x);

    }

    dfs(r);

    dfs(r,r);

    Build(,,n);

    while(m--)

    {

        int opt;

        scanf("%d",&opt);

        if(opt==)

        {

            int x,y,z;

            scanf("%d%d%d",&x,&y,&z);

            LCA_add(x,y,z);

        }else if(opt==)

        {

            int x,y;

            scanf("%d%d",&x,&y);

            printf("%d\n",LCA_sum(x,y));

        }else if(opt==)

        {

            int x,z;

            scanf("%d%d",&x,&z);

            Add(,pos[x],en[x],z);

        }else

        {

            int x;

            scanf("%d",&x);

            printf("%d\n",Sum(,pos[x],en[x]));

        }

    //    for(int i=1;i<=n;i++)

    //    {

    //        printf("%d: %d\n",i,Sum(1,pos[i],pos[i]));

    //    }

    }

    return ;

}

树状数组

#include<bits/stdc++.h>

using namespace std;

#define lowbit(x) x&-x

int n,m;

const int maxn=;

int c[maxn];

int a[maxn];

void Add(int x,int s)

{

    while(x<=n)

    {

        c[x]+=s;

        x+=lowbit(x);

    }

}

int Get(int x)

{

    int ans=;

    while(x)

    {

        ans+=c[x];

        x-=lowbit(x);

    }

    return ans;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        Add(i,a[i]);

    }

    while(m--)

    {

        int o,x,k;

        scanf("%d%d%d",&o,&x,&k);

        if(o==)

        {

            Add(x,k);

        }else

        {

            printf("%d\n",Get(k)-Get(x-));

        }

    }

    return ;

}

St表

#include<bits/stdc++.h>

#define ll long long

#define inf 0x7fffffff

using namespace std;

int n,m;

#define maxn 100008

int d[maxn][];

int a[maxn];

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

    }

    for(int i=;i<=n;i++)d[i][]=a[i];

    for(int j=;(<<j)<=n;j++)

    {

        for(int i=;i+(<<j)-<=n;i++)

        {

            d[i][j]=max(d[i][j-],d[i+(<<(j-))][j-]);

        }

    }

    for(int i=;i<=m;i++)

    {

        int k=;

        int l,r;

        scanf("%d%d",&l,&r);

        while(<<(k+)<=(r-l+))k++;

        printf("%d\n",max(d[l][k],d[r-(<<k)+][k]));

    }

    return ;

}

Dijkstra

#include<bits/stdc++.h>

#define inf 0x7fffffff

#define ll long long

#define maxn 500005

using namespace std;

struct node{

    int x,dis;

    bool operator < (const node &a)const

    {

        return dis>a.dis;

    }

};

int n,m;

vector<int> son[maxn],v[maxn];

void Set(int prt,int to,int d)

{

    son[prt].push_back(to);

    v[prt].push_back(d);

}

#define to son[rt.x][i]

int dis[maxn],tim=;

bool vis[maxn];

priority_queue<node> q;

void dijkstra(int s)

{

    for(int i=;i<=n;i++)

    {

        dis[i]=inf;

    }

    memset(vis,,sizeof(vis));

    q.push((node){s,});

    dis[s]=;

    while(!q.empty())

    {

        node rt=q.top();

        q.pop();

        if(vis[rt.x])

        {

            continue;

        }

        vis[rt.x]=;

        for(int i=;i<son[rt.x].size();i++)

        {

            if(dis[to]>dis[rt.x]+v[rt.x][i])

            {

                dis[to]=dis[rt.x]+v[rt.x][i];

                q.push((node){to,dis[to]});

            }

        }

    }

}

int main()

{

    int s;

    scanf("%d%d%d",&n,&m,&s);

    for(int i=;i<=m;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        Set(x,y,z);

    }

    dijkstra(s);

    for(int i=;i<=n;i++)

    {

        printf("%d ",dis[i]);

    }

    return ;

}

Spfa

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define inf 0x7fffffff

#define maxn 10009

int n,m,s;

vector<int> son[maxn],v[maxn];

void Add(int x,int y,int val)

{

    son[x].push_back(y);

    v[x].push_back(val);

}

struct node{

    int x;

    int dis;

};

int dis[maxn];

void spfa(int s)

{

    for(int i=;i<=n;i++)dis[i]=inf;

    queue<node> q;

    q.push((node){s,});

    dis[s]=;

    while(!q.empty())

    {

        node now=q.front();

        q.pop();

        for(int i=;i<son[now.x].size();i++)

        {

            int to=son[now.x][i];

            if(dis[to]>dis[now.x]+v[now.x][i])

            {

                dis[to]=dis[now.x]+v[now.x][i];

                q.push((node){to,dis[to]});

            }

        }

    }

}

signed main()

{

    scanf("%d%d%d",&n,&m,&s);

    for(int i=;i<=m;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        Add(x,y,z);

    }

    spfa(s);

    for(int i=;i<=n;i++)

    {

        printf("%d ",dis[i]);

    }

    return ;

}

Tarjan

int n,m;

#define maxn 10009

vector<int> son[maxn];

int tim,size[maxn],belong[maxn],scc_cnt,cnt;

bool bein[maxn];

int st[maxn];

int dfn[maxn],low[maxn];

void Tarjan(int rt)

{

    dfn[rt]=low[rt]=++tim;

    st[++cnt]=rt;

    for(int i=;i<son[rt].size();i++)

    {

        int to=son[rt][i];

        if(!dfn[to])//正向边

        {

            Tarjan(to);

            low[rt]=min(low[rt],low[to]);

        }else if(!belong[to])//反向边

        {

            low[rt]=min(low[rt],dfn[to]);//能不能取到一个更早的点

        }

    }

    if(dfn[rt]==low[rt])

    {

        //关键节点！！

        scc_cnt++;

        int k;

        do{

            k=st[cnt--];

            belong[k]=scc_cnt;

            size[scc_cnt]++;

        }while(k!=rt);

    }

}

二分图匹配

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define inf 0x7fffffff

int n,m,e;

#define maxn 3009

vector<int> son[maxn];

int hav[maxn];

int vis[maxn];

int timemark=;

bool dfs(int x)

{

    for(int i=;i<son[x].size();i++)

    {

        int to=son[x][i];

        if(vis[to]==timemark)continue;

        vis[to]=timemark;

        if(!hav[to]||dfs(hav[to]))

        {

            hav[to]=x;

            return ;

        }

    }

    return ;

}

signed main()

{

    scanf("%d%d%d",&n,&m,&e);

    while(e--)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        if(v>m||u>n)continue;

        v+=;//!!!

        son[u].push_back(v);

        son[v].push_back(u);

    }

    int s=n;

    for(int i=;i<=n;i++)

    {

        timemark++;

        if(!dfs(i))s--;

    }

    printf("%d\n",s);

    return ;

}

线性素数筛

#include<bits/stdc++.h>

#define inf 0x7fffffff

#define ll long long

using namespace std;

bool p[];

signed main()

{

    int n,m;

    memset(p,,sizeof(p));

    p[]=;

    scanf("%d%d",&n,&m);

    for(int i=;i<=sqrt();i++)

    {

        if(p[i])

        {

            for(int j=i*;j<=;j+=i)p[j]=;

        }

    }

    for(int i=;i<=m;i++)

    {

        int x;

        scanf("%d",&x);

        if(p[x])printf("Yes\n");

        else printf("No\n");

    }

    return ;

}

差分树状数组

#include<bits/stdc++.h>

using namespace std;

#define lowbit(x) x&-x

int n,m;

const int maxn=;

int c[maxn];

int a[maxn];

void Add(int x,int s)

{

    while(x<=n)

    {

        c[x]+=s;

        x+=lowbit(x);

    }

}

int Get(int x)

{

    int ans=;

    while(x)

    {

        ans+=c[x];

        x-=lowbit(x);

    }

    return ans;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        Add(i,a[i]);

        Add(i+,-a[i]);

    }

    while(m--)

    {

        int o;

        scanf("%d",&o);

        if(o==)

        {

            int x,y,k;

            scanf("%d%d%d",&x,&y,&k);

            Add(x,k);

            Add(y+,-k);

        }else

        {

            int k;

            scanf("%d",&k);

            printf("%d\n",Get(k));

        }

    }

    return ;

}

dinic

#include<bits/stdc++.h>

#define inf 0x7fffffff

#define ll long long

using namespace std;

#define maxn 10009

#define maxm 100009

struct node{

    int val,to;

    int rev;//rev表示反边在to的vector当中下标是几

    node(int _to,int _val,int _rev)

    {

        to=_to;

        val=_val;

        rev=_rev;

    }

};

vector<node> son[maxn];

int d[maxn];

int n,m,s,t;

void add(int x,int y,int w)

{

    son[x].push_back(node(y,w,son[y].size()));

    son[y].push_back(node(x,,son[x].size()-));

}

int ans=;

bool bfs()

{

    memset(d,-,sizeof(d));

    queue<int>  q;

    q.push(s);

    d[s]=;

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        for(int i=;i<son[x].size();i++)

        {

            int y=son[x][i].to;

            if(d[y]==- && son[x][i].val)

            {

                q.push(y);

                d[y]=d[x]+;

            }

        }

    }

    if(d[t]==-)return ;

    return ;

}

int dfs(int x,int low)//x 表示当前节点，low表示当前到x的最小参量

{

    if(x==t||low==) return low;

    int s=;

    for(int i=;i<son[x].size();i++)

    {

        int y=son[x][i].to;

        int rev=son[x][i].rev;

        if(d[y]==d[x]+&&son[x][i].val>)

        {

            int a=dfs(y,min(low,son[x][i].val));//当前

            son[x][i].val-=a;

            son[y][rev].val+=a;

            low-=a;

            s+=a;

            if(low==) return s;

        }

    }

    if(low!=)//流到x的流量会有冗余，在这一轮dfs之后就在不会到x了

    {

        d[x]=-;

    }

    return s;

}

void dinic()

{

    while(bfs())

    {

        ans+=dfs(s,inf);

    }

}

int main()

{

    scanf("%d%d%d%d",&n,&m,&s,&t);

    for(int i=;i<=m;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);

    }

    //dinic

    dinic();

    printf("%d\n",ans);

    return ;

}

快速幂取余

#include<bits/stdc++.h>

#define ll long long

ll d,p,k;

ll cal(ll x,ll y)

{

    ll ans=;

    for(;y;x=x*x%k,y>>=)

        if(y&)ans=ans*x%k;

    return ans;

}

using namespace std;

int main()

{

    cin>>d>>p>>k;

    cout<<d<<"^"<<p<<" mod "<<k<<"="<<cal(d,p)%k<<endl;

    return ;

}