Create New World!

常用模板

Posted on By Drelf

1.单源最短路(dijkstra)

#include <iostream>
#include <queue>
#include <cstdio>
#define tree true
using namespace std;

int n,m,s;
int dis[100005];
bool vis[100005];

struct Edge{
    int tar,nex,fir,cap;
}edge[500005];

int cnt=0;
void addedge(int a,int b,int c)
{
    edge[++cnt].tar=b;
    edge[cnt].cap=c;
    edge[cnt].nex=edge[a].fir;
    edge[a].fir=cnt;
}
struct Node
{
    int n,dist;
    Node(int a=0,int b=0):n(a),dist(b){}
    friend bool operator < (const Node &a,const Node &b) {return a.dist>b.dist;}
};
void dij()
{
    priority_queue <Node> q;
    dis[s]=0;
    int now=s;
    q.push(Node(s,0));
    while(!q.empty())
    {
        Node tmp = q.top();q.pop();
        now=tmp.n;
        if(!vis[now])vis[now]=tree;else continue;
        for(int i=edge[now].fir;i;i=edge[i].nex)
        {
            if(dis[now]+edge[i].cap<dis[edge[i].tar])
            {
                dis[edge[i].tar]=dis[now]+edge[i].cap;
                q.push(Node(edge[i].tar,dis[edge[i].tar]));
            }
        }
    }
}

int main()
{
    int a,b,c;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);addedge(a,b,c);}
    for(int i=1;i<=n;i++)dis[i]=2147483647;
    dij();
    for(int i=1;i<=n;i++)printf("%d ",dis[i]);
}

(SPFA)

#include <iostream>
#include <cstdio>
using namespace std;
const int inf=2147483647;
int n,m,s,cnt=0;
int head,tail;
bool v[10005];
int f[50005];
int dist[10005];

struct Edge{
    int tar;
    int nex;
    int fir;
    int cap;
}e[500005];

void add(int a,int b,int c)
{
    cnt++;
    e[cnt].tar=b;
    e[cnt].cap=c;
    e[cnt].nex=e[a].fir;
    e[a].fir=cnt;
}

void spfa()
{
    for(int i=1; i<=n; i++)dist[i]=inf,v[i]=false;
    dist[s]=0;
    v[s]=true;
    head=1;tail=2;f[head]=s;
    while(head<tail)
    {
        for(int tmp=e[f[head]].fir;tmp;tmp=e[tmp].nex)
        {
            if(dist[f[head]]+e[tmp].cap<dist[e[tmp].tar])
            {
                dist[e[tmp].tar]=dist[f[head]]+e[tmp].cap;
                if(!v[e[tmp].tar])
                {
                    f[tail]=e[tmp].tar;
                    v[e[tmp].tar]=true;
                    tail++;
                }
            }
        }
        v[f[head]]=false;
        head++;
    }
}

int main()
{
    int a,b,c;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    spfa();
    dist[s]=0;
    for(int i=1;i<=n;i++)printf("%d ",dist[i]);
    return 0;
}

2.并查集

#include <iostream>
#include <cstdio>
using namespace std;
int n,m,x,y,z;
int father[10005];

int find(int i)
{
    if(father[i]==i)return i;
    else return father[i]=find(father[i]);
}

void merge(int u,int v)
{
    int f1=find(u),f2=find(v);
    if(f1!=f2)father[f2]=f1;
    return ;
}

void judge(int u,int v)
{
    int f1=find(u),f2=find(v);
    if(f1==f2)printf("Y\n");
    else printf("N\n");
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)father[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&z,&x,&y);
        if(z==1)merge(x,y);
        else if(z==2)judge(x,y);
    }
    return 0;
}

3.树状数组(1、2)

#include <iostream>
#include <cstdio>
#define lowbit(k) (k&(-k))
using namespace std;
int n,m;
int a[500005],c[500005];
void add(int i,int k){while(i<=n){c[i]+=k;i+=lowbit(i);}}
int sum(int i){int ans=0;while(i!=0){ans+=c[i];i-=lowbit(i);}return ans;}
int main()
{
    int x,y,z;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){scanf("%d",&x);add(i,x);}
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        if(x==1)add(y,z);
        else {printf("%d\n",sum(z)-sum(y-1));} 
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#define lowbit(k) (k&(-k))
using namespace std;
int n,m;
int a[500005],c[500005];
void add(int i,int k){while(i<=n){c[i]+=k;i+=lowbit(i);}}
int sum(int i){int ans=0;while(i!=0){ans+=c[i];i-=lowbit(i);}return ans;}
int main()
{
    int a,x,y=0,z;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){scanf("%d",&x);add(i,x-y);y=x;}
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a);
        if(a==1)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,z);
            add(y+1,-z);
        }
        else {scanf("%d",&x);printf("%d\n",sum(x));} 
    }
    return 0;
}

4.ST表

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int c,n,m,l,r;
int a[100005];
int f[100005][19];


int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i),f[i][0]=a[i];
    for(int i=1;i<=18;i++)
        for(int j=1;j+(1<<i)<=n+1;j++)
            f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        c=log2(r-l+1);
        printf("%d\n",max(f[l][c],f[r-(1<<c)+1][c]));
    }
    return 0;
}

5.快速幂

#include <iostream>
using namespace std;

inline int mih(int a,int b,int mod)
{
    int ans=1;
    a%=mod;
    while (b)
    {
        if (b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int main()
{
    long long int n,m,k,x;
    cin>>n>>m>>k;
    int mi=(mih(n,m,k)+k)%k;
	cout<<n<<"^"<<m<<" mod "<<k<<"="<<mi;
}

6.线性筛素数

#include <iostream>
#include <cstdio> 
#include <cstring>
#define atz(n,m) memset(n,m,sizeof(n))
using namespace std;
int prime[5000005];
bool vis[10000005];
int Euler(int N,int prime[],int limit)  
{ 
    if(N==0)N=(2<<16)-1; 
    int cnt=0;
    
    atz(vis,false);atz(prime,0);
    for(int i=2;i<=N;i++)
    {
        if(limit>=0&&cnt>=limit)return cnt;
        if(!vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt,i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
    return cnt;
} 

int main()
{
    int N,M,tmp;
    cin>>N>>M;
    Euler(N,prime,-1);
    for(int i=1;i<=M;i++)
    {
        cin>>tmp;
        if(tmp==1)cout<<"No"<<endl;
        else if(vis[tmp])cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}

7.乘法逆元

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int r[20000530];

int main()
{
    long long int n,p,k,tr;
    r[1]=1;
    scanf("%lld%lld",&n,&p);
    for(int i=2;i<=n;i++)
    {
        k=p/i;
        tr=p%i;
        r[i]=(((-k*r[tr])%p)+p)%p;
    }
    for(int i=1;i<=n;i++)printf("%d\n",r[i]);
}

8.最小生成树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int ans=0,cnt=0,n,m;
int fa[5005];

struct Edge{
    int fro,tar,cap;
}e[200005];

bool cam(Edge a,Edge b)
{
    return a.cap<b.cap;
}

int find(int x)
{
    while(x!=fa[x]) x=fa[x]=fa[fa[x]];
    return x;
}

void kruskal()
{
    int f1,f2;
    sort(e,e+m,cam);
    for(int i=1;i<=m;i++)
    {
        f1=find(e[i].fro);
        f2=find(e[i].tar);
        if(f1==f2) continue;
        ans+=e[i].cap;
        fa[f2]=f1;
        cnt++;
        if(cnt==(n-1))break;
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].fro,&e[i].tar,&e[i].cap);
    kruskal();
    printf("%d",ans);
}

9.最近公共祖先

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n,m,s,cnt=0;
int deep[500005];
int fa[500005][25];
int lg[500005];

struct Edge{
    int tar,nex,fir;
}e[500005*2];

void add(int x,int y)
{
    cnt++;
    //e[++cnt]=(Edge){y,e[x].fir,0};
    e[cnt].tar=y;
    e[cnt].nex=e[x].fir;
    e[x].fir=cnt;
}

void dfs(int o,int f)
{
    deep[o]=deep[f]+1;
    fa[o][0]=f;
    for(int i=1;(1<<i)<=deep[o];i++)fa[o][i]=fa[fa[o][i-1]][i-1];
    for(int i=e[o].fir;i;i=e[i].nex)if(e[i].tar!=f)dfs(e[i].tar,o);
}

int LCA(int u,int v)
{
    if(deep[u]<deep[v])swap(u,v);
    while(deep[u]>deep[v])u=fa[u][lg[deep[u]-deep[v]]-1];
    if(u==v)return u;
    else {
        for(int i=lg[deep[u]];i>=0;i--)
        if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}

int main()
{
    int a,b;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n-1;i++){scanf("%d%d",&a,&b);add(a,b);add(b,a);}
    dfs(s,0);
    
    for(int i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",LCA(a,b));
    }
}

10.同余方程

#include <iostream>
using namespace std;

int gcd(int a,int b,int &x,int &y)
{
    if(b==0){x=1;y=0;return a;}
    else
    {
        int tmp=gcd(b,a%b,y,x);
        y-=(a/b)*x;
        return tmp;
    }
}

int main()
{
    int a,b,x,y;
    cin>>a>>b;
    gcd(a,b,x,y);
    cout<<(x+b)%b;
}