板子

Create_Random · 2020-02-10 17:06:48 · 个人记录

快读:

int read()
{
    int x=0,ch=getchar();
    while(!isdigit(ch))
    {
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+ch-'0',ch=getchar();
    }
    return x;
}

快输:

void print(int x)
{
    if(x<0)
    {
       putchar('-');
       x=-x;
    }
    if(x>9)
    {
        print(x/10);
    }
    putchar(x%10+'0');
}

对拍:

:loop

makedata.exe

std.exe

baoli.exe

fc std.out baoli.out

if %errorlevel% == 1 pause

goto loop

floyd:

for(int k=1;k<=n;k++)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        }
    }
}

Dijkstra:

void dij(int s,int t)
{
    bool vis[maxn]={0};
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    for(int i=1;i<=n;i++)
    {
        int u;
        int maxu=inf;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&maxu>dis[j])
            {
                maxu=dis[j],u=j;
            }
        }   
        vis[u]=1;
        for(int j=0;j<g[u].size();j++)
        {
            int v=g[u][j].to,w=g[u][j].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
            }
        }
    }
}

SPFA:

void spfa(int s)
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push(s);
    inq[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i].to,w=g[u][i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!inq[v])
                {
                    q.push(v);
                    inq[v]=1;
                }   
            }
        }
    }
}

堆优化的Dijkstra:

struct node
{
    int to,dis,next;
}e[maxm];
int head[maxn],dis[maxn],cnt;
bool vis[maxn];
void add_edge(int u,int v,int w)
{
    cnt++;
    e[cnt].dis=w;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
struct point
{
    int dis;
    int pos;
    bool operator<(const point b)const
    {
        return dis>b.dis;
    }
};
void pri_dij(int s)
{
    priority_queue<point> q;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push((node){s,0});
    while(!q.empty())
    {
        node tmp=q.top();
        q.pop();
        int u=tmp.pos;
        if(vis[u])
        {
            continue;
        }
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to,w=e[i].dis;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    q.push((node){v,dis[v]});
                }
            }
        }
    }
}

prim:

void prim()
{
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    for(int i=1;i<=n;i++)
    {
        int next=0;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]<dis[next])
            {
                next=j;
            }
        }
        vis[next]=1;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]>g[next][j])
            {
                dis[j]=g[next][j];
            }
        }
        tot+=dis[next];
    }
}

ST表:

void build()
{
    for(int j=1;1<<j<=n;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
        }
    }
}
int query(int x,int y)
{
    int ans=log2(y-x+1);
    return max(f[x][ans],f[y-(1<<ans)+1][ans]);
}

并查集:

int fifa(int x)
{
    if(x==p[x])
    {
        return x;
    }
    int root=fifa(p[x]);
    return p[x]=root;
}
void join(int x,int y)
{
    int px=fifa(x);
    int py=fifa(y);
    if(px!=py)
    {
        p[px]=py;
    }
}
bool issame(int x,int y)
{
    int px=fifa(x);
    int py=fifa(y);
    if(px==py)
    {
        return 1;
    }
    return 0;
}

线段树:

void build_tree(int root,int l,int r)
{
    if(l==r)
    {
        tree[root]=a[l];
        return;
    }
    int mid=(l+r)/2;
    int lson=root*2;
    int rson=root*2+1;
    build_tree(lson,l,mid);
    build_tree(rson,mid+1,r);
    tree[root]=tree[lson]+tree[rson];
}
void fun(int root,int l,int r,int v)
{
    tree[root]+=(r-l+1)*v;
    lazy[root]+=v;
}
void pushdown(int root,int l,int r)
{
    int mid=(l+r)/2;
    int lson=root*2;
    int rson=root*2+1;
    fun(lson,l,mid,lazy[root]);
    fun(rson,mid+1,r,lazy[root]);
    lazy[root]=0;
}
void update(int root,int l,int r,int sp,int ep,int v)
{
    if(r<sp||ep<l)
    {
        return;
    }
    if(sp<=l&&r<=ep)
    {
        fun(root,l,r,v);
        return;
    }
    pushdown(root,l,r);
    int mid=(l+r)/2;
    int lson=root*2;
    int rson=root*2+1;
    update(lson,l,mid,sp,ep,v);
    update(rson,mid+1,r,sp,ep,v);
    tree[root]=tree[lson]+tree[rson];
}
int query(int root,int l,int r,int sp,int ep)
{
    if(r<sp||ep<l)
    {
        return 0;
    }
    if(sp<=l&&r<=ep)
    {
        return tree[root];
    }
    pushdown(root,l,r);
    int mid=(l+r)/2;
    int lson=2*root;
    int rson=2*root+1;
    int la=query(lson,l,mid,sp,ep);
    int ra=query(rson,mid+1,r,sp,ep);
    return la+ra;
}

树状数组:

int lowbit(int x)
{
    return x&-x;
}
void update(int x,int v)
{
    while(x<=n)
    {
        d[x]+=v;
        x+=lowbit(x);
    }
}
int query(int x)
{
    int res=0;
    while(x)
    {
        res+=d[x];
        x-=lowbit(x);
    }
    return res;
}

最近公共祖先(LCA):

void dfs(int s,int t)
{
    a[s]=a[t]+1;
    f[s][0]=t;
    for(int i=1;(1<<i)<=a[s];i++)
    {
        f[s][i]=f[f[s][i-1]][i-1];
    }
    for(int i=head[s];i;i=g[i].w)
    {
        if(g[i].to!=t)
        {
            dfs(g[i].to,s);
        }
    }
}
int lca(int x,int y)
{
    if(a[x]>a[y])
    {
        swap(x,y);
    }
    int p=a[y]-a[x];
    for(int i=20;i>=0;i--)
    {
        if((p>>i)&1)
        {
            y=f[y][i];
        }
    }
    if(x==y)
    {
        return x;
    }
    for(int i=20;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}

哈希:

int Hash(string &a)
{
    int res=0;
    for(int i=0;i<a.length();i++)
    {
        res+=res*base+a[i];
    }
    return res;
}

快速幂：

int pow(int a,int b,int p)
{
    int ans=1;
    while(b>0)
    {
        if(b%2)
        {
            ans=(ans*a)%p;
        }
        a=a*a%p;
        b/=2;
    }
    return ans%p;
}

龟速乘：

int pow(int a,int b,int p)
{
    int ans=1;
    while(b>0)
    {
        if(b%2)
        {
            ans=(ans+a)%p;
        }
        a=a+a%p;
        b/=2;
    }
    return ans%p;
}

矩阵快速幂:

struct mat
{
    int a[110][110];
    mat(){memset(a,0,sizeof(a));}
    mat operator* (mat b)const
    {
        mat c;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int k=1;k<=n;k++)
                {
                    c.a[i][j]+=(a[i][k]*b.a[k][j])%mod;
                    c.a[i][j]%=mod;
                }
            }
        }
        return c;
    }
}b;
mat matpow(mat b,int t)
{
    mat ans;
    for(int i=1;i<=n;i++)
    {
        ans.a[i][i]=1;
    }
    while(t)
    {
        if(t%2)
        {
            ans=ans*b;

        }
        b=b*b;
            t>>=1;
    }
    return ans;
}

扩展中国剩余定理(EXCRT):

ll gsmul(ll a,ll b,ll p)
{
    ll ans=0;
    while(b)
    {
        if(b&1)
        {
            ans+=a;
            ans%=p;
        }
        a+=a;
        a%=p;
        b>>=1;
    }
    return ans;
}
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    else
    {
        int x2,y2;
        int gcd=exgcd(b,a%b,x2,y2);
        x=y2;
        y=x2-(a/b)*y2;
        return gcd;
    }
}
void exchina()
{
    for(int i=2;i<=n;i++)
    {
        int a=A[i-1],b=A[i],d=B[i]-B[i-1];
        int x,y;
        int gcd=exgcd(a,b,x,y);
        int m=b/gcd;
        x=(x%m+m)%m;
        x=gsmul(x,(d/gcd%m+m)%m,m);
        A[i]=b/gcd*a,B[i]=B[i-1]+a*x;
    }
    cout<<B[n];
}

严格次小生成树:

struct node
{
    int u,v,w,tag;
}g[300010],a[300010];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int p[300010];
int n,m;
int fifa(int x)
{
    if(x==p[x])
    {
        return x;
    }
    return p[x]=fifa(p[x]);
}
int bz[300010][20],deep[300010];
int head[300010],tot;
void add(int u,int v,int w)
{
    g[++tot].u=u,g[tot].v=v,g[tot].w=w,g[tot].tag=head[u],head[u]=tot;
    g[++tot].u=v,g[tot].v=u,g[tot].w=w,g[tot].tag=head[v],head[v]=tot;
}
int maxi[300010][20];
int mini[300010][20];
void dfs(int u,int fa)
{
    bz[u][0]=fa;
    for(int i=head[u];i;i=g[i].tag)
    {
        int v=g[i].v;
        if(v==fa)
        {
            continue;
        }
        deep[v]=deep[u]+1ll;
        maxi[v][0]=g[i].w;
        mini[v][0]=-1e15;
        dfs(v,u);
    }
}
int lca(int x,int y)
{
    if(deep[x]<deep[y])
    {
        swap(x,y);
    }
    for(int i=18;i>=0;i--)
    {
        if(deep[bz[x][i]]>=deep[y])
        {
            x=bz[x][i];
        }
    }
    if(x==y)
    {
        return x;
    }
    for(int i=18;i>=0;i--)
    {
        if(bz[x][i]^bz[y][i])
        {
            x=bz[x][i],y=bz[y][i];
        }
    }
    return bz[x][0];
}
int qmax(int u,int v,int maxx)
{
    int ans=-1e15;
    for(int i=18;i>=0;i--)
    {
        if(deep[bz[u][i]]>=deep[v])
        {
            if(maxx!=maxi[u][i])
            {
                ans=max(ans,maxi[u][i]);
            }
            else
            {
                ans=max(ans,mini[u][i]);
            }
            u=bz[u][i];
        }
    }
    return ans;
void cal()
{
    for(int i=1;i<=18;i++)
    {
        for(int j=1;j<=n;j++)
        {
            bz[j][i]=bz[bz[j][i-1]][i-1];
            maxi[j][i]=max(maxi[j][i-1],maxi[bz[j][i-1]][i-1]);
            mini[j][i]=max(mini[j][i-1],mini[bz[j][i-1]][i-1]);
            if(maxi[j][i-1]>maxi[bz[j][i-1]][i-1])
            {
                mini[j][i]=max(mini[j][i],maxi[bz[j][i-1]][i-1]);
            }
            else if(maxi[j][i-1]<maxi[bz[j][i-1]][i-1])
            {
                mini[j][i]=max(mini[j][i],maxi[j][i-1]);
            }
        }
    }
}

扩展欧几里得(乘法逆元):

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    else
    {
        int x2,y2;
        int d=exgcd(b,a%b,x2,y2);
        x=y2;
        y=x2-(a/b)*y2;
        return d;
    }
}

八聚氧:

#define fastcall __attribute__((optimize("-O3")))
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

高精度:

高精度板子