详见——

详见——

关注
发信
关注(28)粉丝(399)

CSP-S需备模板大全

CSP-S需备模板大全

谨以此文祝愿自己\(CSP-S\,\,2019\,\,\color{red}{RP++!!}\)

算法

二分

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

详见——二分写法详解

数学

快速幂

int qpow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)
            ret=(ret*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ret;
}

详见——浅谈快速幂/快速乘

GCD

int gcd(int x,int y)
{
    return y?gcd(y,x%y):x;
}

详见——求GCD的两种方式

LCM

int lcm(int x,int y)
{
    return (x*y)/gcd(x,y);
}

详见——浅谈最大公约数、最小公倍数

扩展GCD

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

详见——详解扩展GCD

判断质数

bool prime(int x)
{
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
            return 0;
    return 1;
}

详见——质数相关知识点详解

线性筛质数

void euler(int x)
{
    cnt=0;
    for(int i=2;i<=x;i++)
    {
        if(!v[i])
            prime[++cnt]=i;
        for(int j=1;j<=cnt && i*prime[j]<=x;j++)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}

详见——质数相关知识点详解

质因数分解

void divide(int x)
{
    cnt=0;
    for(int i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
            prime[++cnt]=i,c[cnt]=0;
        while(x%i==0)
            c[cnt]++,x/=i;
    }
    if(x>1)
        prime[++cnt]=x,c[cnt]=1;
}

详见——质数相关知识点详解

求一个数的约数

void factor(int x)
{
    cnt=0;
    for(int i=1;i<=sqrt(x);i++)
        if(x%i==0)
        {
            fac[++cnt]=i;
            if(i!=x/i)
                fac[++cnt]=x/i;
        }
}

详见——约数相关知识点详解

线性筛约数

vector<int> f;
void factors(int x)
{
    for(int i=1;i<=x;i++)
        for(int j=1;j<=x/i;j++)
            f[i*j].push_back(i);
}

详见——约数相关知识点详解

求一个数的欧拉函数

int Phi(int x)
{
    int ret=x;
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
        {
            ret=ret/i*(i-1);
            while(x%i==0)
                x/i;
        }
    if(x>1)
        ret=ret*x*(x-1);
    return ret;
}

详见——浅谈欧拉函数

线性筛欧拉函数

void euler(int x)
{
    cnt=0;
    for(int i=2;i<=x;i++)
    {
        if(!v[i])
            prime[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt && i*prime[j]<=x;j++)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
}

详见——浅谈欧拉函数

杨辉三角&组合数

void calc(int n)
{
    c[0][0]=1;
    c[1][0]=c[1][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
}

详见——详解组合数相关性质

图论

Floyd

void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(map[i][j]>map[i][k]+map[k][j])
                    map[i][j]=map[i][k]+map[k][j];
}

详见——最短路三算法及模板

Dijkstra+堆优化

void dijkstra(int s)
{
    memset(dist,0x3f,sizeof(dist));
    memset(v,0,sizeof(v));
    dist[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int x=q.top().second;
        if(v[x])
        {
            q.pop();
            continue;
        }
        x=q.top().second,q.pop();v[x]=1;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i];
            if(dist[y]>dist[x]+val[i])
                dist[y]=dist[x]+val[i],q.push(make_pair(-dist[y],y));
        }
    }
}

详见——详解DIJ堆优化

SPFA

void spfa(int s)
{
    memset(dist,0x3f,sizeof(dist));
    memset(v,0,sizeof(v));
    dist[s]=0;
    q.push(s);
    v[s]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        v[x]=0;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i];
            if(dist[y]>dist[x]+val[i])
            {
                dist[y]=dist[x]+val[i];
                if(!v[y])
                    q.push(y),v[y]=1;
            }
        }
    }
}

详见——最短路三算法及模板

SPFA + SLF优化

void spfa(int s)
{
    memset(dist,0x3f,sizeof(dist));
    memset(v,0,sizeof(v));
    dist[s]=0;
    q.push_back(s);
    v[s]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop_front();
        v[x]=0;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i];
            if(dist[y]>dist[x]+val[i])
            {
                dist[y]=dist[x]+val[i];
                if(!v[y])
                {
                    if(dist[y]>dist[q.front()])
                        q.push_back(y);
                    else
                        q.push_front(y);
                    v[y]=1;
                }
            }
        }
    }
}

详见——关于SPFA算法的优化形式

Kruskal

void kruskal()
{
    sort(e+1,e+tot+1,cmp);//cmp是自定义比较函数,e是边的结构体
    for(int i=1;i<=tot;i++)
    {
        int fx=find(e[i].x);//find是并查集查找函数
        int fy=find(e[i].y);
        if(fx!=fy)
        {
            fa[fx]=fy;
            ans+=e[i].z;
            cnt++;
        }
        if(cnt==n-1)
            break;
    }
}

详见——CSP-J/S图论总结

Prim

void prim()
{
    memset(f,0x3f,sizeof(f));
    memset(v,0,sizeof(v));
    f[1]=0;v[1]=1;
    for(int i=1;i<=n;i++)
    {
        int temp=1<<30,k;
        for(int j=1;j<=n;j++)
            if(!v[j]&&f[j]<temp)
                temp=f[j],k=j;
        v[k]=1;
        ans+=f[k];
        for(int j=head[k];j;j=nxt[j])
        {
            int y=to[j];
            if(val[j] && !v[j] && f[j]>val[j])
                f[j]=val[j];
        }
    }
}

详见——CSP-J/S图论总结

拓扑排序

void topsort()
{
    for(int i=1;i<=n;i++)
        if(!out_degree[i])
            q.push(i);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i];
            if(y==fa[x])
                continue;
            out_degree[y]--;
            if(!out_degree[y])
                q.push(y);
        }
    }
}

详见——CSP-J/S图论讲解

倍增求LCA

int lca(int x,int y)
{
    int ret;
    if(deep[x]<deep[y])
        swap(x,y);
    for(int i=20;i>=0;i--)
        if(deep[fa[x][i]]>=deep[y])
            x=fa[x][i];
    if(x==y)
        return y;
    for(int i=20;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
        else
            ret=fa[x][i];
    }
    return ret;
}

详见——求LCA的几种方式

数据结构

并查集

int find()
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

字符串hash

int hash(char s[])
{
    int ret=0;
    int len=strlen(s);
    for(int i=0;i<=len;i++)
    {
        ret*=p;
        ret+=s[i]-'a';
        ret%=mod;//p是乘数，我常取31，mod是模数，需要模大质数
    }
    return ret%mod;
}

详见——详解字符串Hash

树状数组

void update(int x,int k)
{
    for(int i=x;i<=n;i+=i&-i)
        c[i]+=k;//c为树状数组
}
void query(int x)
{
    int ret=0;
    for(int i=x;i;i-=i&-i)
        ret+=c[i];
    return ret;
}

详见——树状数组知识点详解

线段树

巨长无比...

#define lson pos<<1
#define rson pos<<1|1
void pushup(int pos,int l,int r)
{
    tree[pos]=tree[lson]+tree[rson];//这里只给出求和的pushup，维护其他的线段树类比即可。
}
void build(int pos,int l,int r)
{
    int mid=(l+r)>>1;
    if(l==r)
    {
        tree[pos]=a[l];//a[l]为原数列，tree[]为线段树数组
        return;
    }
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(pos,l,r);
}
void mark(int pos,int l,int r,int k)
{
    tree[pos]+=(r-l+1)*k;
    lazy[pos]+=k;//同样只演示了维护和的线段树，lazy数组是lazy标记数组
}
void pushdown(int pos,int l,int r)
{
    int mid=(l+r)>>1;
    mark(lson,l,mid,lazy[pos]);
    mark(rson,mid+1,r,lazy[pos]);
    lazy[pos]=0;
}
void update(int pos,int l,int r,int x,int y,int k)
{
    int mid=(l+r)>>1;
    if(x<=l && r<=y)
    {
        mark(pos,l,r,k);
        return;
    }
    pushdown(pos,l,r);
    if(x<=mid)
        update(lson,l,mid,x,y,k);
    if(y>mid)
        update(rson,mid+1,r,x,y,k);
    pushup();
}
int query(int pos,int l,int r,int x,int y)
{
    int ret=0;
    int mid=(l+r)>>1;
    if(x<=l && r<=y)
        return tree[pos];
    pushdown(pos,l,r);
    if(x<=mid)
        ret+=query(lson,l,mid,x,y);
    if(y>mid)
        ret+=query(rson,mid+1,r,x,y);
    return ret;
}

详见——简单线段树知识点详解

树链剖分

只写了两次深搜的预处理，和修改、查询线段树部分请看上面...

void dfs1(int x,int f)
{
    deep[x]=deep[f]+1;
    fa[x]=f;
    size[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(y==f)
            continue;
        dfs1(y,x);
        size[x]+=size[y];
        if(!son[x]||size[y]>size[son[x]])
            son[x]=y;
    }
}
void dfs2(int x,int t)
{
    top[x]=t;
    id[x]=++cnt;
    w[cnt]=a[x];
    if(!son[x])
        return;
    dfs2(son[x],t);
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(y==fa[x]||y==son[x])
            continue;
        dfs2(y,y);
    }
}
void upd_chain(int x,int y,int k)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])
            swap(x,y);
        update(1,1,n,id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(deep[x]<deep[y])
        swap(x,y);
    update(1,1,n,id[y],id[x],k);
}
void upd_subtree(int x,int k)
{
    update(1,1,n,id[x],id[x]+size[x]-1,k);
}
int q_chain(int x,int y)
{
    int ret=0;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])
            swap(x,y);
        ret+=query(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(deep[x]<deep[y])
        swap(x,y);
    ret+=query(1,1,n,id[y],id[x]);
    return ret;
}
int q_subtree(int x)
{
    return query(1,1,n,id[x],id[x]+size[x]-1);
}

详见——浅谈树链剖分

01-11 14:29
Powered by LMLPHP ©2024 详见—— 0.065846