基础知识检查·模板复习

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

基础知识检查·模板复习

作者：

銘权 , 2019-11-12 16:32:19 , 所有人可见 , 阅读 2968

38

87

写在前面 :

罗列了一些条目和模板,手打,有误轻喷
根据算法竞赛进阶指南来的，但可能有些不全 ~~我怎么会告诉你有些我也不会~~

基础

快速幂
64 位整数乘法
lowbit
1)整数二进制表示下所有是1的位
2)树状数组 (树状数组求逆序对)
前缀和
1)一维前缀和
2)二维前缀和
递归
1)1 ~ n 任意取数组合
2)全排
A ^ B 的所有约数之和
二分
离散化
1)整数离散化
2)区间离散化
归并排序 (归并排序求逆序对)
倍增
1)普通倍增
2)ST 算法

数据结构

栈
队列
邻接表
Hash
1)hash 表
2)字符串简单 hash (进制法直接储存)
3)字符串链表 hash (链表储存hash值)
字符串
1)KMP 算法(字符串匹配)
2)Trie
堆
并查集
1)路径压缩、按秩合并
2)扩展域与边带权
线段树
分块
二叉查找树 & 平衡树

搜索

树的深度优先遍历
1)dfs 序
2)树的深度
3)树的重心
树的广度优先遍历
拓扑排序
深度优先搜索
1)剪枝
2)迭代加深
3)双向搜索
广度优先搜索
1)双端队列BFS
2)优先队列BFS
3)双向BFS
A*
IDA*

图论

最短路
1)单源最短路
2)分层图最短路(有特殊边操作)
3)任意两点间最短路
最小生成树
树的直径
最近公共祖先(lca)
树上差分
基环树
差分约数系统
Tarjan
1)无向图连通性
2)有向图连通性
二分图匹配
二分图覆盖与独立集

动态规划

线性 DP 基础问题 : LIS\LCS\数字三角形
背包
1)0/1 背包
2)完全背包
3)多重背包
4)分组背包
区间 DP 模型
树形 DP 模型
状态压缩
1)二进制压缩
2)滚动数组
优化
1)倍增
2)数据结构
3)单调队列
4)斜率
5)四边形不等式
其他 DP
1)计数类 DP
2)数位统计 DP
后效性问题

数论

质数问题
1)质数的判定和筛选
2)质因数分解
约数
1)试除法
2)最大公约数
3)欧拉函数
同余
1)扩展欧几里得算法
2)同余方程
矩阵乘法与高斯消元
排列、组合、计数
概率与期望
博弈论

基础模板

快速幂

int power(int a,int b,int p)
{
    int ans=1%p;
    for(;b;b>>=1)
    {
        if(b&1) ans=(long long)ans*a%p;
        a=(long long)a*a%p;
    }
    return ans;
}

64 位整数乘法

ll mul(ll a,ll b,ll p)
{
    ll ans=0;
    for(;b;b>>=1)
    {
        if(b&1) ans=(ans+a)%p;
        a=(ll)a*2%p;
        //二进制拆分 
    }
    return ans;
}

lowbit

int lowbit(int x)
{
    return n&-n;
    //return n & (~ n + 1);
}

整数二进制表示下所有是1的位

    int H[37];
    for(int i=0;i<36;i++) H[(1ll<<i)%37]=i;
    while(cin>>n)
    {
        while(n>0)
        {
            cout<<H[(n&-n)%37]<<" ";
            n-=lowbit(n);
        }
    }

树状数组

int s[N];

void add(int x,int k)
{
    while(x<=n)
    {
        s[x]+=k;
        x+=lowbit(x);
    }
}

int sum(int x)
{
    //求 1 ~ x 的和 
    int ans=0;
    while(x!=0)
    {
        ans+=s[x];
        x-=lowbit(x);
    }
    return ans;
}

树状数组求逆序对

    for(int i=n;i;i--)
    {
        ans+=ask(a[i]-1);
        add(a[i],1);
    }

树状数组求逆序对扩展

//楼兰图腾 
inline int lowbit(int x) {return x&-x;}

inline void add_min(int x,int y)
{
    for(;x<=n;x+=lowbit(x)) minn[x]+=y;
}

inline void add_max(int x,int y)
{
    for(;x<=n;x+=lowbit(x)) maxn[x]+=y;
}

inline int ask_min(int x)
{
    int res=0;
    for(;x;x-=lowbit(x)) res+=minn[x];
    return res;
}

inline int ask_max(int x)
{
    int res=0;
    for(;x;x-=lowbit(x)) res+=maxn[x];
    return res;
}
//在主函数中 
    for(int i=1;i<=n;i++) add_min(a[i],1);
    add_min(a[1],-1);
    for(int i=1;i<=n;i++)
    {
        ans1+=(long long)(ask_max(n)-ask_max(a[i]))*(ask_min(n)-ask_min(a[i]));
        ans2+=(long long)ask_max(a[i])*ask_min(a[i]);
        add_max(a[i],1); if(i+1<=n) add_min(a[i+1],-1);
        //ask_min(x) 求 x 后面有几个数比它小   ask_max(x) 求 x 前面有几个数比它小 ( 相减求得前面有几个数比它大 ) 
    }

一维前缀和

    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

二维前缀和

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

1 ~ n 任意取数组合

vector<int> chosen

void calc(int x)
{
    if(x==n+1)
    {
        for(int i=1;i<chose.size();i++)
            printf("%d ",chose[i]);
        puts("");
        return ;
    }
    calc(x+1);
    chosen.push_back(x);
    calc(x+1);
    chosen.pop_back();
}

全排

int chosen[];
bool f[];

void calc(int k)
{
    if(k==n+1)
    {
        for(int i=1;i<=n;i++) printf("%d ",chosen[i]);
        puts("");
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(f[i]) continue;
        chosen[k]=i;
        f[i]=1;
        clac(k+1);
        f[i]=0;
    }
}

A ^ B 的所有约数之和

//分治法求 sum(p , c) = 1 + p + p ^ 2 + ...... + p ^ c

int sum(int p,int c)
{
    if(c==0) return 1;
    if(c%2==1) return (1+qpow(p,(c+1)/2))%sum(p,(c-1)/2);
    return (1+qpow(p,c/2))*sum(p,c/2-1)+qpow(p,c);
}

二分

    while(l<r)
    //>= x 中最小的一个 
    {
        int mid=(l+r)>>1;
        if(a[mid]>=x) r=mid;
        else l=mid+1;
    }
    ------------------------
    while(l<r)
    //<= x 中最大的一个 
    {
        int mid=(l+r+1)>>1;
        if(a[mid]<=x) l=mid;
        else r=mid-1;
    }
    ------------------------
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
        //else......
    }

离散化

整数离散化

void discrete()
{
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        if(i==1||a[i]!=a[i-1]) b[++m]=a[i];
}

int query(int x)
{
    return lower_bound(b+1,b+m+1,x)-b;
}

区间离散化

    for(int i=1;i<=n;i++)
    {
        v[++cnt]=a[i].l=read();
        v[++cnt]=a[i].r=read();
    }
    sort(v+1,v+cnt+1);
    int m=unique(v+1,v+cnt+1)-(v+1);

    for(int i=1;i<=n;i++)
    {
        a[i].l=lower_bound(v+1,v+m+1,a[i].l)-v;
        a[i].r=lower_bound(v+1,v+m+1,a[i].r)-v;
    }

归并排序

void msort(int l,int r)
{
    if(l==r) return ;

    int mid=(l+r)>>1,i=l,j=mid+1;

    msort(l,mid);
    msort(j,r);

    for(int k=l;k<=r;k++)
        if(j>r||i<=mid&&a[i]<=a[j]) b[k]=a[i++];
        else b[k]=a[j++]//,cnt+=mid-i+1;  cnt 为逆序对个数 

    for(int k=l;k<=r;k++) a[k]=b[k];
}

倍增

普通倍增

void work()
{
    int p=1,l=1,r=1;
    while(r<=n)
    {
        if(!p) end();
        else if(r+p<=n&&check())
        {
            r+=p;
            p<<=1;
            if(r==n) end();
        }
        else p>>=1;
    }
}

ST 算法

int lg2[N];
//lg2[i]=lg2[i/2]+1

void st_prework()
{
    for(int i=1;i<=n;i++) f[i][0]=a[i];
    for(int j=1;j<22;j++)
        for(int i=1;i<=n-(1<<j)+1;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

int st_query(int l,int r)
{
    int k=lg2[r-l+1];
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

数据结构综合

栈

int stack[100000+10];
int top;

void push(int x)
{
    stack[++top]=x;
}

void pop()
{
    printf("%d\n",stack[top--]);
}

队列

int lis[1000+10];

int len,head,tail;

void push(int x)
{
    lis[tail]=x;
    ++tail;
    tail%=len;
}

void out()
{
    ++head;
    head%=len;
}

邻接表

int ver[],head[],nex[],edge[];

void add(int x,int y)
{
    ver[++tot]=y;
    edge[tot]=z;
    nex[tot]=head[x];
    head[x]=tot;
}

void visit(int x)
{
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i],z=edge[i];
        work();
    }
}

hash

hash 表

//统计数字出现个数 

const int p=1331,N=2000;

struct node
{
    int x;
    int num;
};

int m;

vector<node> Hash[N];

void add(int n)
{
    int x=n%p+1;
    bool flag=false;
    for(int i=0;i<Hash[x].size();i++)
    {
        if(Hash[x][i].x==n)
        {
            flag=true;
            Hash[x][i].num++;
            cout<<Hash[x][i].num<<endl;
            break;
        }
    }
    if(!flag)
    {
        node a;
        a.x=n;
        a.num=1;
        puts("1");
        Hash[x].push_back(a);
    }
}

字符串 hash

typedef unsigned long long ull;

const int N;
const ull p,mod,base;

ull hash[N];
char s[N];

ull get_hash(char ch[])
{
    int len=strlen(ch);
    ull res=0;

    for(int i=0;i<len;i++)
        ans=(ans*base+(ull)ch[i])%mod+p;
        //ans=(ans*base+(ull)ch[i])%mod 也行(转换为 base 进制) 
    return res;
}

链表 hash

int get_hash(char *a)
{
    gethash;
}

bool judge(char *a,char *b)
{
    work;
}

bool insert(char *a)
{
    int hash_num=get_hash(a);
    for(int i=head[hash_num];i;i=nex[i])
        if(judge(v[i],a)) return true;
    ++tot;
    memcpy(v[tot],a,strlen(a)*sizeof(int));
    nex[tot]=head[hash_num];
    head[hash_num]=tot;
    return false;
}

//Snowflake Snow Snowflakes POJ3349 

#include<bits/stdc++.h>
using namespace std;

const int N=100000+10,mod=99991;

int n,tot=0,snow[N][6],hea[N],nex[N];

int Hash(int *a)
{
    int sum=0,mul=1;
    for(int i=0;i<6;++i)
    {
        sum=(sum+a[i])%mod;
        mul=(long long)mul*a[i]%mod;
    }
    return (sum+mul)%mod;
}

bool equal(int *a,int *b)
{
    for(int i=0;i<6;++i)
        for(int j=0;j<6;++j)
        {
            bool flag=true;
            for(int k=0;k<6;++k)
                if(a[(i+k)%6]!=b[(j+k)%6]) flag=false;
            if(flag) return true;
            flag=true;
            for(int k=0;k<6;++k)
                if(a[(i+k)%6]!=b[(j-k+6)%6]) flag=false;
            if(flag) return true;
        }
    return false;
}

bool insert(int *a)
{
    int val=Hash(a);
    for(int i=hea[val];i;i=nex[i])
        if(equal(snow[i],a)) return true;
    ++tot;
    memcpy(snow[tot],a,6*sizeof(int));
    nex[tot]=hea[val];
    hea[val]=tot;
    return false;
}

int main()
{
    scanf("%d",&n);

    for(int i=1;i<=n;++i)
    {
        int a[6];
        for(int j=0;j<6;++j) scanf("%d",&a[j]);
        if(insert(a))
        {
            puts("Twin snowflakes found.");
            return 0;
        }
    }

    puts("No two snowflakes are alike.");

    return 0;
}

KMP

void prework()
{
    next[1]=0;

    for(int i=2,j=0;i<=n;i++)
    {
        while(j>0&&a[i]!=a[j+1]) j=next[j];
        if(a[i]==a[j+1]) j++;
        next[i]=j;
    }
}

void KMP()
{
    for(int i=1,j=0;i<=m;i++)
    {
        while(j>0&&(j==n||b[i]!=a[j+1])) j=next[j];
        if(b[i]==a[j+1]) j++;
        f[i]=j;
        //if(f[i]==n) 此时就是 A 在 B 中的某一次出现 
    }
}

Trie

int trie[N][27];
char s[N];
bool end[N];

int tot=1;

void insert(char *str)
{
    int len=strlen(str),p=1;
    for(int k=0;k<len;k++)
    {
        int ch=str[k]-'a';
        if(trie[p][ch]==0) trie[p][ch]=++tot;
        p=trie[p][ch];
    }
    end[p]=true;
}

bool search(char* str)
{
    int len=strlen(str),p=1;
    for(int k=0;k<len;k++)
    {
        p=trie[p][str[k]-'a'];
        if(p==0) return false;
    }
    return end[p];
}

堆

struct node{
    int val;
    friend bool operator <(node a,node b){
        return a.val > b.val;
        //小根堆 
        //return a.val < b.val;
    }
}u;
priority_queue<node> q;

//例 :  
struct WORK
{
    int n,a,t,l;
}a[N];

bool operator<(const WORK &a,const WORK &b)
{
    if(a.l==b.l) return a.a>b.a;
    return a.l<b.l;
}

并查集

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

void merge(int x,int y)
{
    fa[get(x)]=fa[y];
}

边带权(银河英雄传说)

int get(int x)
{
    if(x==fa[x]) return x;
    int root=get(fa[x]);
    d[x]+=d[fa[x]];
    return fa[x]=root;
}

void merge(int x,int y)
{
    x=get(x),y=get(y);
    fa[x]=y,d[x]=size[y];
    size[y]+=size[x];
}

线段树

//两种打法 
const int N=100000+10;

int n,m;
int a[N];
struct TREE
{
    int l,r;
    ll dat,tag;
}t[N*4];

void build(int rt,int l,int r)
{
    t[rt].l=l,t[rt].r=r;
    if(l==r)
    {
        t[rt].dat=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    t[rt].dat=t[rt<<1].dat+t[rt<<1|1].dat;
}

void spread(int rt)
{
    if(t[rt].tag)
    {
        int ls=rt<<1,rs=rt<<1|1,lazy=t[rt].tag;
        t[ls].dat+=lazy*(t[ls].r-t[ls].l+1),t[ls].tag+=lazy;
        t[rs].dat+=lazy*(t[rt].r-t[rs].l+1),t[rs].tag+=lazy;
        t[rt].tag=0;
    }
}

void change(int rt,int l,int r,int val)
{
    if(l<=t[rt].l&&r>=t[rt].r)
    {
        t[rt].dat+=(ll)val*(t[rt].r-t[rt].l+1);
        t[rt].tag+=val;
        return ;
    }
    spread(rt);
    int mid=(t[rt].l+t[rt].r)>>1;
    if(l<=mid) change(rt<<1,l,r,val);
    if(r>=mid+1) change(rt<<1|1,l,r,val);
    t[rt].dat=t[rt<<1].dat+t[rt<<1|1].dat;
}

ll query(int rt,int l,int r)
{
    if(l<=t[rt].l&&r>=t[rt].r) return t[rt].dat;
    spread(rt);
    int mid=(t[rt].l+t[rt].r)>>1;
    ll ans=0;
    if(l<=mid) ans+=query(rt<<1,l,r);
    if(r>=mid+1) ans+=query(rt<<1|1,l,r);
    return ans;
}


#define ll long long
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r

const int N=100000+10;

int a[N];
ll dat[N*4],add[N*4];

inline void build(int rt,int l,int r)
{
    if(l==r)
    {
        dat[rt]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    dat[rt]=dat[rt<<1]+dat[rt<<1|1];
}

inline void spread(int rt,int l,int r)
{
    //l,r 表示为 rt 的左右儿子
    if(add[rt])
    {
        int mid=(l+r)>>1;
        dat[rt<<1]+=(ll)add[rt]*(mid-l+1),add[rt<<1]+=add[rt];
        dat[rt<<1|1]+=(ll)add[rt]*(r-mid),add[rt<<1|1]+=add[rt];
        add[rt]=0;
    }
}

inline void change(int rt,int l,int r,int L,int R,int k)
{
    //l,r 表示为 rt 的左右儿子,下同
    if(L<=l&&R>=r)
    {
        dat[rt]+=(ll)k*(r-l+1);
        add[rt]+=k;
        return ;
    }
    spread(rt,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) change(lson,L,R,k);
    if(R>=mid+1) change(rson,L,R,k);
    dat[rt]=dat[rt<<1]+dat[rt<<1|1];
}

inline ll query(int rt,int l,int r,int L,int R)
{
    if(L<=l&&R>=r)
    {
        return dat[rt];
    }
    spread(rt,l,r);
    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid) ans+=query(lson,L,R);
    if(R>=mid+1) ans+=query(rson,L,R);
    return ans;
}

分块

 void change(int li,int ri,ll d)
{
    int p=pos[li],q=pos[ri];
    if(p==q)
    {
        for(int i=li;i<=ri;i++) a[i]+=d;
        sum[p]+=d*(ri-li+1);
    }
    else
    {
        for(int i=p+1;i<=q-1;i++) add[i]+=d;
        for(int i=li;i<=r[p];i++) a[i]+=d;
        sum[p]+=d*(r[p]-li+1);
        for(int i=l[q];i<=ri;i++) a[i]+=d;
        sum[q]+=d*(ri-l[q]+1);
    }
}

ll ask(int li,int ri)
{
    int p=pos[li],q=pos[ri];
    ll ans=0;
    if(p==q)
    {
        for(int i=li;i<=ri;i++) ans+=a[i];
        ans+=add[p]*(ri-li+1);
    }
    else
    {
        for(int i=p+1;i<=q-1;i++)
            ans+=sum[i]+add[i]*(r[i]-l[i]+1);
        for(int i=li;i<=r[p];i++) ans+=a[i];
        ans+=add[p]*(r[p]-li+1); 
        for(int i=l[q];i<=ri;i++) ans+=a[i];
        ans+=add[q]*(ri-l[q]+1);
    }
    return ans;
}

void prework()
{
    int t=sqrt(n);
    for(int i=1;i<=t;i++)
    {
        l[i]=(i-1)*t+1;
        r[i]=i*t;
    }
    if(r[t]<n)
    {
        t++;
        l[t]=r[t-1]+1;
        r[t]=n;
    }
    for(int i=1;i<=t;i++)
        for(int j=l[i];j<=r[i];j++)
        {
            pos[j]=i;
            sum[i]+=a[j];
        }
}

平衡树模板

#include<bits/stdc++.h>
using namespace std;

const int N=100000+10;

struct Treap
{
    int l,r;        //左右子节点在数组中的下标 
    int val,dat;        //节点关键码、权值 
    int cnt,size;       //副本数、子树大小 
}a[N];      //数组模拟链表 
int tot=0,root,n,INF=0x3fffffff;

int New(int val)
{
    a[++tot].val=val;
    a[tot].dat=rand();      //使用随机数，使 BST 趋于平衡 
    a[tot].cnt=a[tot].size=1;
    return tot;
}

void Update(int p)
{
    a[p].size=a[a[p].l].size+a[a[p].r].size+a[p].cnt;       //子树大小为数的多少 
}

void Build()
{
    New(-INF),New(INF);
    root=1,a[1].r=2;        //右节点关键码大于根节点关键码 
    Update(root);
}

int GetRankByVal(int p,int val)
{
    if(p==0) return 0;
    if(val==a[p].val) return a[a[p].l].size+1;
    if(val<a[p].val) return GetRankByVal(a[p].l,val);
    return GetRankByVal(a[p].r,val)+a[a[p].l].size+a[p].cnt;
}

int GetValByRank(int p,int rank)
{
    if(p==0) return INF;
    if(a[a[p].l].size>=rank) return GetValByRank(a[p].l,rank);
    if(a[a[p].l].size+a[p].cnt>=rank) return a[p].val;
    return GetValByRank(a[p].r,rank-a[a[p].l].size-a[p].cnt);
}

void zig(int &p)
{
    int q=a[p].l;
    a[p].l=a[q].r,a[q].r=p,p=q;
    Update(a[p].r),Update(p);
}

void zag(int &p)
{
    int q=a[p].r;
    a[p].r=a[q].l,a[q].l=p,p=q;
    Update(a[p].l),Update(p);
}

void Insert(int &p,int val)
{
    if(p==0)        //树中没有点就新建点 
    {
        p=New(val);
        return ;
    }
    if(val==a[p].val)
    {
        a[p].cnt++,Update(p);
        return ;
    }
    if(val<a[p].val)
    {
        Insert(a[p].l,val);
        if(a[p].dat<a[a[p].l].dat) zig(p);      //右旋 
    }
    else
    {
        Insert(a[p].r,val);
        if(a[p].dat<a[a[p].r].dat) zag(p);      //左旋 
    }
    Update(p);
}

int GetPre(int val)
{
    int ans=1;
    int p=root;
    while(p)
    {
        if(val==a[p].val)
        {
            if(a[p].l>0)
            {
                p=a[p].l;
                while(a[p].r>0) p=a[p].r;       //左子树上一直往右走 
                ans=p;
            }
            break;
        }
        if(a[p].val<val&&a[p].val>a[ans].val) ans=p;
        p=val<a[p].val?a[p].l:a[p].r;
    }
    return a[ans].val;
}

int GetNext(int val)
{
    int ans=2;
    int p=root;
    while(p)
    {
        if(val==a[p].val)
        {
            if(a[p].r>0)
            {
                p=a[p].r;
                while(a[p].l>0) p=a[p].l;       //右子树上一直往左走 
                ans=p;
            }
            break;
        }
        if(a[p].val>val&&a[p].val<a[ans].val) ans=p;
        p=val<a[p].val?a[p].l:a[p].r;
    }
    return a[ans].val;
}

void Remove(int &p,int val)
{
    if(p==0) return ;
    if(val==a[p].val)       //检索到 val 
    {
        if(a[p].cnt>1)      //有副本  
        {
            a[p].cnt--,Update(p);
            return ;
        }
        if(a[p].l||a[p].r)      //不是叶子节点，向下旋转 
        {
            if(a[p].r==0||a[a[p].l].dat>a[a[p].r].dat)
                zig(p),Remove(a[p].r,val);
            else zag(p),Remove(a[p].l,val);
            Update(p);
        }
        else p=0;       //使叶子结点，删除 
        return ;
    }
    val<a[p].val?Remove(a[p].l,val):Remove(a[p].r,val);
    Update(p);
}

int main()
{
    Build();
    scanf("%d",&n);

    while(n--)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        switch(opt)
        {
            case 1:
                Insert(root,x);
                break;
            case 2:
                Remove(root,x);
                break;
            case 3:
                printf("%d\n",GetRankByVal(root,x)-1);
                break;
            case 4:
                printf("%d\n",GetValByRank(root,x+1));
                break;
            case 5:
                printf("%d\n",GetPre(x));
                break;
            case 6:
                printf("%d\n",GetNext(x));
                break;
        }
    }

    return 0;
}

可持久化数据结构

//留坑

搜索模型

树的遍历

深度优先遍历

void dfs(int x)
{
    v[x]=1;
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(v[y]) continue;
        dfs(y);
    }
}

dfs序

void dfs(int x)
{
    df[++cnt]=x;
    v[x]=1;
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(v[y]) continue;
        dfs(y);
    }
    df[++cnt]=x;
}

树的深度

void dfs(int x)
{
    v[x]=1;
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(v[y]) continue;
        d[y]=d[x]+1;
        dfs(y);
    }
}

树的重心

void dfs(int x)
{
    v[x]=1;
    size[x]=1;
    int max_part=0;
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(v[y]) continue;
        dfs(y);
        size[x]+=size[y];
        max_part=max(max_part,size[y]);
    }
    max_part=max(max_part,n-size[x]);
    if(max_part<ans)
    {
        ans=max_part;
        pos=x;
    }
}

树的宽度优先遍历

void bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    q.push(1);
    d[1]=1;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nex[i])
        {
            int y=ver[i];
            if(d[y]) continue;
            d[y]=d[x]+1;
            q.push(y);
        }
    }
}

拓扑排序

void topsort()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(deg[i]==0) q.push(i);
    while(q.size())
    {
        int x=q.top();
        q.pop();
        a[++cnt]=x; //排序好的序列 
        for(int i=head[x];i;i=nex[i])
        {
            int y=ver[i];
            if(!(--deg[y])) q.push(y); 
        }
    }
}

深度优先搜索

深搜模型

void dfs(int deep)
{
    if(check) return ;
    //边界判定 

    for(;;)     //枚举情况 
    {
        prework();
        //更改 
        dfs(deep+1);
        //搜索 
        recover();
        //还原 
    }
}

剪枝 :

1.优化搜索顺序
2.排除等效冗余
3.可行性剪枝
4.最优性剪枝
5.记忆化

例题：小木棍

//Sticks

#include<bits/stdc++.h>
using namespace std;

const int N=60;

int read()
{
    static int x;x=0;
    char ch;ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x;
}

int n,sum,len,maxn;
int t[N];

void clear() {sum=0;len=0;maxn=0;memset(t,0,sizeof(t));}

bool dfs(int rest,int now,int po)
{
    if(rest==0) return true;
    if(now==len) return dfs(rest-1,0,maxn);
    for(int i=po;i>=0;--i)
        if(t[i]&&now+i<=len)
        {
            --t[i];
            if(dfs(rest,now+i,i)) return true;
            ++t[i];
            if(now==0||now+i==len) return false;
        }
}

int main()
{
    while(1)
    {
        n=read();
        if(n==0) break;
        clear();
        for(int i=1,x;i<=n;i++)
        {
            x=read();
            if(x>50) --i,--n;
            else ++t[x],sum+=x,maxn=max(x,maxn);
        }
        for(int i=maxn;i<=sum;i++)
        {
            if(i*2>sum) {printf("%d\n",sum); break;}
            if(sum%i) continue;
            len=i;
            if(dfs(sum/i,0,maxn)) {printf("%d\n",len); break;}
        }
    }

    return 0;
}

迭代加深

//Addition Chains

    while(cin>>n,n)
    {
        int k=1;
        while(!dfs(1,k)) k++;
        //迭代加深思想的体现，k为范围 
        out_ans;
        //for(int i=0;i<k;i++) cout<<ans[i]<<" ";
        //cout<<endl;
    }

双向搜索

//送礼物
/*1 ~ N 个数取任意个，使总和尽量接近 W
*/ 

const int N=1<<24,M=50;

ll g[N],wei[N];
int n,m,k,len,cnt=0;
ll w,ans=0;

void dfs1(int po,int weight)
{
    if(po==k+1)
    {
        //k=n/2+2 
        wei[++cnt]=weight;
        return ;
    }
    if(weight+g[po]<=w) dfs1(po+1,weight+g[po]);
    dfs1(po+1,weight);
}
//将 1 ~ N 分成两段，前一段处理出可能的数和，后一段中任取数和加入前一段数列生成的数和，来找到最接近数 
//将 wei 数组中的数排序后去重 
void dfs2(int po,int weight)
{
    if(po==n+1)
    {
        int l=1,r=len;
        while(l<r)
        //二分查找 
        {
            int mid=l+r+1>>1;
            if(wei[mid]+weight<=w) l=mid; else r=mid-1;
            //寻找能加入的最大数 
        }
        if(wei[l]+weight<=w) ans=max(ans,wei[l]+weight);
        //l==r 
        return ;
    }
    if(weight+g[po]<=w) dfs2(po+1,weight+g[po]);
    dfs2(po+1,weight);
}

广度优先搜索

矩阵距离 (模型)

    while(q.size())
    {
        pair<int ,int > now=q.front();q.pop();
        for(int k=0;k<4;k++)
        {
            pair<int ,int > nex(now.first+dx[k],now.second+dy[k]);
            if(nex.first<1||nex.second<1||nex.first>n||nex.second>m) continue;
            //边界问题 
            if(!f[nex.first][nex.second])
            {
                f[nex.first][nex.second]=true;
                d[nex.first][nex.second]=d[now.first][now.second]+1;
                q.push(nex);
            }
        }
    }

双端队列 BFS

//电路维修 
int bfs()
{
    memset(st,0,sizeof(st));
    memset(d,63,sizeof(d));

    deque<pair<int ,int > > q;
    //相当于堆优化 
    q.push_back({0,0});d[0][0]=0;

    int dx[4]={-1,-1,1,1},dy[4]={-1,1,1,-1};
    int ix[4]={-1,-1,0,0},iy[4]={-1,0,0,-1};
    char cs[]="\\/\\/";

    while(q.size())
    {
        pair<int,int> nex=q.front();q.pop_front();
        int x=nex.first,y=nex.second;
        if(st[x][y]) continue;
        st[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i],j=x+ix[i],k=y+iy[i];
            if(a<0||b<0||a>n||b>m) continue;
            int w=(s[j][k]!=cs[i]);
            if(d[a][b]>d[x][y]+w)
            {
                d[a][b]=d[x][y]+w;
                //最短路
                if(w) q.push_back({a,b});
                else q.push_front({a,b});
                //边权为 0 可以立即更新
            }
        }
    }
    if(d[n][m]==d[n+1][m+1]) return -1;
    return d[n][m];
}

优先队列BFS

//堆优化
//取负加入得小根堆 
priority_queue<pair<int,int> > q;

//双向BFS

//Nightmare II
int bfs()
{
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    memset(st,0,sizeof st);
    int cnt=0;
    PII boy,girl;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            if (g[i][j]=='M') boy={i, j};
            else if (g[i][j]=='G') girl={i,j};
            else if (g[i][j]=='Z') ghost[cnt++ ]={i, j};
    queue<PII> qb,qg;
    qb.push(boy);
    qg.push(girl);
    int step=0;
    while(qb.size()||qg.size())
    {
        //两处轮流广搜 
        step++;
        for(int i =0;i<3;i++)
            for(int j=0,len=qb.size();j<len;j++)
            {
                auto t=qb.front();
                qb.pop();
                int x=t.first,y=t.second;
                if(!check(x,y,step)) continue;
                for(int k=0;k<4;k++)
                {
                    int a=x+dx[k],b=y+dy[k];
                    if(check(a,b,step))
                    {
                        if(st[a][b]==2) return step;
                        if(!st[a][b]) st[a][b]=1,qb.push({a,b});
                    }
                }
            }
        for(int i=0;i<1;i++)
            for(int j=0,len=qg.size();j<len;j++)
            {
                auto t=qg.front();
                qg.pop();
                int x=t.first,y=t.second;
                if (!check(x,y,step)) continue;
                for (int k=0;k<4;k++)
                {
                    int a=x+dx[k],b=y+dy[k];
                    if(check(a,b,step))
                    {
                        if(st[a][b]==1) return step;
                        if(!st[a][b]) st[a][b]=2,qg.push({a,b});
                    }
                }
            }
    }
    return -1;
}

A*

//留坑

IDA*

//留坑

图论基础及扩展

最短路

单源最短路

Dijkstra 算法

#include<bits/stdc++.h>
using namespace std;

const int N=100000+10,M=1000000+10;

struct EDGE {int ver,nex,edge;} e[M]; int head[N];
int dis[N]; bool v[N];

int n,m,str,tot;

priority_queue<pair<int,int> > q;
//堆优化

void add(int x,int y,int z) {e[++tot].ver=y;e[tot].edge=z;e[tot].nex=head[x];head[x]=tot;}

void dijkstra(int str)
{
    //str 是出发点
    memset(dis,63,sizeof(dis));
    memset(v,0,sizeof(v));
    dis[str]=0;
    q.push(make_pair(0,str));
    while(q.size())
    {
        int x=q.top().second;q.pop();
        if(v[x]) continue;
        v[x]=1;
        //每个点只入队一次 
        for(int i=head[x];i;i=e[i].nex)
        {
            int y=e[i].ver,z=e[i].edge;
            if(dis[y]>dis[x]+z)
            {
                dis[y]=dis[x]+z;
                q.push(make_pair(-dis[y],y));
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&str);
    for(int i=1,x,y,z;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    dijkstra(str);

    for(int i=1;i<=n;i++) printf("%d ",dis[i]);

    return 0;
}

spfa

void spfa(int str)
{
    memset(dis,63,sizeof(dis));
    memset(v,0,sizeof(v));
    dis[str]=0;v[1]=1;
    q.push(1);
    while(q.size())
    {
        int x=q.front();q.pop();
        v[x]=0;
        for(int i=head[x];i;i=e[i].nex)
        {
            int y=e[i].ver,z=e[i].edge;
            if(dis[y]>dis[x]+z)
            {
                dis[y]=dis[x]+z;
                if(!v[y]) q.push(y),v[y]=1;
            }
        }
    }
}

分层图最短路

//将特殊操作转化为零边进入下一层
//除建图外，求最短路操作相同 

    for(int i=0,x,y,z;i<m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);
        for(int j=1,z1=0;j<=k;j++)
        {
            add(x+(j-1)*n,y+j*n,z1);
            add(y+(j-1)*n,x+j*n,z1);
            add(x+j*n,y+j*n,z);
            add(y+j*n,x+j*n,z);
        }
    }
    for(int i=0,x,y,z;i<m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,z);
        //第一层建边
        for(int j=1,z1=0;j<=k;j++)
        //k 次特殊操作，每次进入下一层 
        {
            //一层 n 个点 
            add(x+(j-1)*n,y+j*n,z1);
            add(y+j*n,x+(j-1)*n,z1);
            //j 层和 j + 1 层的连边
            add(x+j*n,y+j*n,z1);
            add(y+j*n,x+j*n,z1);
            //j + 1 层的连边 
        } 
    }

    for(int i=1,z=0;i<=k;i++)
        add(t+(i-1)*n,t+i*n,z);
    //防止 k 次特殊操作还没用完就结束，在终点处往下建边 

    dijkstra(s);

    printf("%d",dis[t+k*n]);

任意两点间的最短路

Floyd

    memset(dis,63,sizeof(dis));
    for(int i=1;i<=n;i++) dis[i][i]=0;
    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]);

圆方树

定义 : 任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌

//求一棵仙人掌中任意两点的最短距离

#include<bits/stdc++.h>
using namespace std;

const int N=40000+10;

struct node{int ver,nex,edge;}e[N*2],ne[N*2]; int head[N],nhead[N];

int wson[N],size[N],fa[N],dep[N],top[N];
//重连剖分 
int po[N],dis[N],sum[N];
//  点权 树间距 路径长
//树间距就是在生成的树中,点到 root 的距离
//路径长是环上从最初点到当前点的路径权值和 
int dfn[N],low[N];
//e-dcc

int n,m,q,tot,num,ext,ans,ntot;

int read() {static int x;x=0;char ch;ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x;}

void add(int x,int y,int z) {e[++tot].ver=y;e[tot].edge=z;e[tot].nex=head[x];head[x]=tot;}
void nadd(int x,int y,int z) {ne[++ntot].ver=y;ne[ntot].edge=z;ne[ntot].nex=nhead[x];nhead[x]=ntot;}

void dfs1(int x)
{
    size[x]=1;dep[x]=dep[fa[x]]+1;
    for(int i=nhead[x];i;i=ne[i].nex)
    {
        int y=ne[i].ver;
        if(y!=fa[x]) {fa[y]=x; dis[y]=dis[x]+ne[i].edge; dfs1(y); size[x]+=size[y];    if(size[y]>size[wson[x]]) wson[x]=y;}
    }
}

void dfs2(int x,int nowtop)
{
    top[x]=nowtop;    if(wson[x]) dfs2(wson[x],nowtop);
    for(int i=nhead[x];i;i=ne[i].nex) {int y=ne[i].ver;    if(y!=fa[x]&&y!=wson[x]) dfs2(y,y);}
}

int lca(int x,int y) {while(top[x]!=top[y]) {if(dep[top[x]]<dep[top[y]]) swap(x,y); x=fa[top[x]];}return dep[x]<dep[y]?x:y;}

//构建菊花图~~ 
void build(int x,int y,int z)
//非树边 
//非树边就是在搜索中刚好成环的那条边
//非树边将树变成了仙人掌，除去非树边，仙人掌会退化为树，所以叫非树边
{
    ++ext; int nz,len=z,i=y;
    while(i!=fa[x]) {sum[i]=len; len+=po[i]; i=fa[i];}
    sum[ext]=sum[x]; sum[x]=0; i=y;
    while(i!=fa[x]) {nz=min(sum[i],sum[ext]-sum[i]); nadd(ext,i,nz); nadd(i,ext,nz);i=fa[i];}
                        //环中的最短路       圆点到方点的距离意为圆点到父节点的最短距离
}

//点双缩点这部分最重要 
void tarjan(int x,int fro)
{
    dfn[x]=low[x]=++num;
    for(int i=head[x];i;i=e[i].nex)
    {
        if(e[i].ver==fro) continue;    int y=e[i].ver; int z=e[i].edge;
        if(!dfn[y]){fa[y]=x,po[y]=z;   tarjan(y,x);    low[x]=min(low[x],low[y]);} else low[x]=min(low[x],dfn[y]);
        //时刻保存父节点，一旦成点双就建方点
        //po[y] 为 y 的点权(将边权转化为点权)
        if(low[y]<=dfn[x]) continue;   nadd(x,y,z);    nadd(y,x,z);
    }                           //如果不是割点，就是圆点和圆点之间的连线
    for(int i=head[x];i;i=e[i].nex) {int y=e[i].ver;    if(fa[y]==x||dfn[y]<dfn[x]) continue;build(x,y,e[i].edge);}
                                                        //判断是否成环(找割点)                   //非树边
}

int find(int x,int father) {int res; while(top[x]!=top[father]) {res=top[x]; x=fa[top[x]];} return x==father?res:wson[father];}
    //模仿查找lca过程 

void init() {n=read(); m=read(); q=read(); ext=n; for(int i=1,x,y,z;i<=m;i++) {x=read(); y=read(); z=read(); add(x,y,z); add(y,x,z);}}

void prework() {tarjan(1,0); dfs1(1); dfs2(1,1);}

int main()
{
    init(); prework();

    int u,v,far,s1,s2;
    while(q--)
    {
        u=read();v=read(); far=lca(u,v);
        if(far<=n) ans=dis[u]+dis[v]-(dis[far]<<1);
        //第一种情况 
        else
        {
            s1=find(u,far);s2=find(v,far);ans=dis[u]+dis[v]-dis[s1]-dis[s2];
            if(sum[s1]<sum[s2]) swap(s1,s2); ans+=min(sum[s1]-sum[s2],sum[far]+sum[s2]-sum[s1]);
                                                    //环上最短路径 
        }
        //第二种情况 
        printf("%d\n",ans);
    }

    return 0;
}

最小生成树

kruskal 算法

const int N=100000+10,M=500000+10; 

struct EDGE{int x,y,z;}e[M]; 

int fa[N];
int n,m,ans;

bool cmp(EDGE a,EDGE b)
{
    return a.z<b.z;
}

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

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);

    sort(e+1,e+n+1,cmp);

    for(int i=1;i<=n;i++) fa[i]=i;

    for(int i=1;i<=m;i++)
    {
        int x=get(e[i].x),y=get(e[i].y);
        if(x==y) continue;
        fa[x]=y;
        ans+=e[i].z;
    }

    return 0;
}

严格次小生成树

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=4e5+10;

struct rec
{
    int x,y,z,id;
}e[N];      int fa[N];

struct EDGE
{
    int ver,nex,edge;
}E[N<<1];   int head[N];

struct DP
{
    int fa,max1,max2;
}f[N][25];  int dep[N];

int n,m,tot,t;
ll res=0,ANS=1e16;
bool v[N];

queue<int> q;

inline int read()
{
    static int x;x=0;char ch;ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x;
}

bool cmp(rec a,rec b)
{
    return a.z<b.z;
}

inline void add(int x,int y,int z)
{
    E[++tot].ver=y;E[tot].edge=z;E[tot].nex=head[x];head[x]=tot;
}

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

inline DP adde(int far,int maxn1,int maxn2)
{
    DP a;a.fa=far;a.max1=maxn1;a.max2=maxn2;return a;
}

inline void kruskal()
{
    for(int i=1;i<=n;i++) fa[i]=i;

    sort(e+1,e+m+1,cmp);

    for(int i=1;i<=m;i++)
    {
        int x=get(e[i].x),y=get(e[i].y);
        if(x==y) continue;
        fa[x]=y;res+=e[i].z;v[i]=1;
        add(e[i].x,e[i].y,e[i].z); add(e[i].y,e[i].x,e[i].z);
    }
}

inline DP MAX(DP a,DP b)
{
    if(a.max1>b.max1) b.max2=b.max1,b.max1=a.max1;
    if(a.max1>b.max2&&a.max1<b.max1) b.max2=a.max1;
    return b;
}

inline void bfs()
{
    for(int i=1;i<=n;i++)
        for(int j=0;j<=t;j++) f[i][j]=adde(-1,-1,-1);
    dep[1]=1;q.push(1);
    while(q.size())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=E[i].nex)
        {
            int y=E[i].ver;
            if(dep[y]) continue;
            dep[y]=dep[x]+1;
            f[y][0]=adde(x,E[i].edge,-1);
            for(int j=1;j<=t;j++)
            {
                int far=f[y][j-1].fa;
                if(far==-1) break;
                f[y][j]=MAX(f[y][j-1],f[far][j-1]); 
            }
            q.push(y);
        }
    }
}

inline DP quiry(int x,int y)
{
    DP tmp=adde(-1,-1,-1);
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=t;i>=0;i--)
        if(dep[f[x][i].fa]>=dep[y]) tmp=MAX(tmp,f[x][i]),x=f[x][i].fa;
    if(x==y) return tmp;
    for(int i=t;i>=0;i--)
        if(f[x][i].fa!=f[y][i].fa)
            tmp=MAX(tmp,MAX(f[x][i],f[y][i])),x=f[x][i].fa,y=f[y][i].fa;
    return MAX(tmp,MAX(f[x][0],f[y][0]));
}

int main()
{
    n=read();m=read();

    t=(int)(log(n)/log(2))+1;

    for(int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].z=read(),e[i].id=i;

    kruskal();
    bfs();

    for(int i=1;i<=m;i++)
        if(!v[i])
        {
            DP tmp=quiry(e[i].x,e[i].y);
            if(tmp.max1==e[i].z&&tmp.max2!=-1) ANS=min(ANS,res-tmp.max2+e[i].z);
            if(e[i].z>tmp.max1) ANS=min(ANS,res-tmp.max1+e[i].z);
        }

    printf("%lld",ANS);

    return 0;
}

最小 K 度生成树模板

#include<bits/stdc++.h>
using namespace std;

const int N=210,inf=1e9;

struct EDGE {int x,y,z;}e[N*N],maxn[N];

int n,k,m=0,tot=1,ans=0;
int fa[N],minn[N],po[N];
int mp1[N][N],mp2[N][N];

inline void init()
{
    scanf("%d%d%d",&n,&m,&k);
    memset(mp1,-1,sizeof(mp1));
    for(int i=1,x,y,z;i<=m;i++)
    {
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
        if(mp1[e[i].x][e[i].y]==-1) mp1[e[i].x][e[i].y]=mp1[e[i].y][e[i].x]=z;
        else mp1[e[i].x][e[i].y]=mp1[e[i].y][e[i].x]=min(mp1[e[i].x][e[i].y],z);
    }
}

bool cmp(EDGE a,EDGE b) {return a.z<b.z;}
int get(int x) {return fa[x]==x?x:fa[x]=get(fa[x]);}

inline void solve1()
{
    for(int i=1;i<=tot;i++) fa[i]=i;
    sort(e+1,e+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(e[i].x==1||e[i].y==1) continue;
        int x=get(e[i].x),y=get(e[i].y);
        if(x!=y)
        {
            mp2[e[i].x][e[i].y]=mp2[e[i].y][e[i].x]=1;
            fa[y]=x;ans+=e[i].z; 
        }
    }
}

inline void solve2()
{
    memset(minn,63,sizeof(minn));
    for(int i=2;i<=tot;i++)
        if(mp1[i][1]!=-1)
        {
            int rt=get(i);
            if(mp1[i][1]<minn[rt])
            {
                po[rt]=i;
                minn[rt]=mp1[i][1];
            }
        }
    for(int i=1;i<=tot;i++)
        if(minn[i]!=minn[0])
        {
            ++m;
            mp2[1][po[i]]=mp2[po[i]][1]=1;
            ans+=mp1[1][po[i]];
        }
}

void dfs(int x,int fro)
{
    for(int i=2;i<=tot;i++)
        if(mp2[x][i]&&i!=fro)
        {
            if(maxn[i].z==-1)
            {
                if(mp1[x][i]<maxn[x].z) maxn[i]=maxn[x];
                else maxn[i].x=x,maxn[i].y=i,maxn[i].z=mp1[x][i];
            }
            dfs(i,x);
        }
}

inline void solve3()
{
    for(int i=m+1;i<=k;i++)
    {
        memset(maxn,-1,sizeof(maxn)); maxn[1].z=-inf;
        for(int j=2;j<=tot;j++)
            if(mp2[1][j]) maxn[j].z=-inf;
        dfs(1,0);
        int num=0,res=inf;
        for(int j=2;j<=n;j++)
            if(mp1[1][j]!=-1&&mp1[1][j]-maxn[j].z<res)
            {
                res=mp1[1][j]-maxn[j].z;
                num=j;
            }
        if(res>=0) break;
        mp2[1][num]=mp2[num][1]=1;
        mp2[maxn[num].x][maxn[num].y]=mp2[maxn[num].y][maxn[num].x]=0;
        ans+=res; 
    }
}

int main()
{
    init();
    solve1();
    solve2();
    solve3();
    printf("%d",ans);
    return 0;
}

prim 算法

const int N=3000+10;

int e[N][N],dis[N]; bool v[N];
int n,m,ans;

void prim()
{
    memset(dis,63,sizeof(dis));
    memset(v,0,sizeof(v));
    dis[1]=0;
    for(int i=1;i<n;i++)
    {
        int x=0;
        for(int j=1;j<=n;j++)
            if(!v[j]&&(x==0||dis[j]<dis[x])) x=j;
            //找到两集合最短距 
        v[x]=1;
        for(int y=1;y<=n;y++)
            if(!v[y]) dis[y]=min(dis[y],e[x][y]);
            //更新两集合最短距 
    }
}

树的直径

宽搜求直径

int bfs(int s)
{
    int i,x,y,z;
    memset(dis,63,sizeof(dis));
    q.push(s);dis[s]=pre[s]=0;
    while(q.size())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].nex)
        {
            y=e[i].ver,z=e[i].edge;
            if(dis[y]==dis[0])
            {
                dis[y]=dis[x]+z;
                pre[y]=i;
                q.push(y);
            }
        }
    }
    for(x=y=1;x<=n;x++)
        if(dis[x]>dis[y]) y=x;
    return y;
}

int get()
{
    p=bfs(1);p=bfs(p);
    return dis[p];
}

dp 求直径

void dp(int x)
{
    v[x]=true;
    for(int i=head[x];i;i=e[i].nex)
    {
        int y=e[i].ver;
        if(v[y]) continue;
        dp(y);
        ans=max(ans,dis1[x]+dis1[y]+e[i].edge);
        dis1[x]=max(dis1[x],dis1[y]+e[i].edge);
    }
}

最近公共祖先 lca

倍增求 lca

#include<bits/stdc++.h>
using namespace std;

const int N=500000+10;

int n,m,rt,tot=0;

int read()
{
    static int x;x=0;char ch;ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x;
}

struct node
{
    int ver,nex;
}e[N<<1];
int head[N],dep[N],fa[N][25],lg[N];
//f[i][j] 表示 2 的 j 次级祖先 

void add(int x,int y)
{
    e[++tot].ver=y;
    e[tot].nex=head[x];
    head[x]=tot;
}

void dfs(int x)
{
    dep[x]=dep[fa[x][0]]+1;
    for(int i=1;i<=lg[dep[x]];i++) fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i;i=e[i].nex)
    {
        int y=e[i].ver;
        if(y==fa[x][0]) continue;
        fa[y][0]=x; dfs(y);
    }
}

int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]!=dep[y]) x=fa[x][lg[dep[x]-dep[y]]-1];
    //使 x 和 y 深度相同 
    if(x==y) return x;
    for(int k=lg[dep[x]]-1;k>=0;--k)
        if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k];
    return fa[x][0];
}

int main()
{
    n=read();m=read();rt=read();
    for(int i=1,x,y;i<n;i++)
    {
        x=read();y=read();
        add(x,y);add(y,x);
    }
    for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
    //lg[i]=log2(i)+1 
    dfs(rt);
    for(int i=1,u,v;i<=m;i++)
    {
        u=read();v=read();
        printf("%d\n",lca(u,v));
    }
    return 0;
}

重链剖分求 lca

#include<bits/stdc++.h>
using namespace std;

const int N=500000+10;

int wson[N],size[N],fa[N],dep[N],top[N];
int head[N],ver[N*2],nex[N*2];
int n,m,tot=0,root=1;           //一般根节点为 1  

void add(int x,int y)
{
    ver[++tot]=y;
    nex[tot]=head[x];
    head[x]=tot;
}

void dfs1(int x)
{
    size[x]=1;
    dep[x]=dep[fa[x]]+1;
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(y!=fa[x])
        {
            fa[y]=x;
            dfs1(y);
            size[x]+=size[y];
            if(size[y]>size[wson[x]]) wson[x]=y;
        }
    }
}

void dfs2(int x,int nowtop)
{
    top[x]=nowtop;
    if(wson[x]) dfs2(wson[x],nowtop);
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(y!=fa[x]&&y!=wson[x]) dfs2(y,y);
    }
}

int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
        //将所在链的链头更深的点跳到链头的父节点 
    }
    return dep[x]<dep[y]?x:y;
    //返回深度更浅的点 
}

int main()
{
    scanf("%d%d%d",&n,&m,&root);
    //scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }

    dfs1(root);
    dfs2(root,root);
    //根节点为最长长链的链头

    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }

    return 0;
}

树上差分

void dfs1(int x,int fro)
{
    for(int i=head[x];i;i=e[i].nex)
    {
        int y=e[i].ver;
        if(y==fro) continue;
        dfs1(y,x);
        temp[x]+=temp[y];
    }
}
//主函数中 
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        temp[x]++,temp[y]++,temp[lca(x,y)]-=2;
    }

    dfs1(1,0);

Tarjan 算法

求割边

const int N=100000+10;

int head[N],ver[N*2],nex[N*2];
int dfn[N],low[N];
int n,m,tot=1,num;
//成对变换 
bool bridge[N*2];

void add(int x,int y)

void tarjan(int x,int in_edge)
{
    dfn[x]=lwo[x]=++num;
    //搜索序
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            //搜索树中的点 
            if(low[y]>dfn[x]) bridge[i]=bridge[i^1]=true;
        }
        else if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);
        //通过不在搜索树上的边能到达 x  
    }
}

求割点

const int N=100000+10;

int head[N],ver[N*2],nex[N*2];
int dfn[N],low[N],stack[N];
bool cut[N];

int n,m,tot,num,root;

void add()

void tarjan(int x)
{
    dfn[x]=low[x]=++num;
    int flag=0;
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[x]>=low[y])
            {
                flag++;
                if(x!=root||flag>1) cut[x]=true;
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}

e-dcc

int c[N],dcc;

void dfs(int x)
{
    c[x]=dcc;
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(c[y]||bridge[i]) continue;
        dfs(y);
    }
}
int main()
{

    for(int i=1;i<=n;i++)
        if(!c[i])
        {
            ++dcc;
            dfs(i);
        }

}

e-dcc缩点

int hc[N],vc[N*2],nc[N*2],tc;
void add_c(int x,int y)
{
    vc[++tc]=y;nc[tc]=hc[x];hc[x]=tc;
}
int main()
{

    tc=1;
    for(int i=2;i<=tot;i++)
    {
        int x=ver[i^1],y=ver[i];
        if(c[x]==c[y]) continue;
        add_c(c[x],c[y]);
    }

}

v-dcc

void tarjan(int x)
{
    dfn[x]=low[x]=++num;
    stack[++top]=x;
    if(x==root&&head[x]==0)
    {
        dcc[++cnt].push_back(x);
        return ;
    }
}

有向图连通性

有向图强联通分量 SCC

const int N=100000+10,M=1000000+10;

struct EDGE
{
    int ver,nex;
}e[M];  int head[N],dfn[N],low[N];
int stack[N],ins[N],c[N];

vector<int> scc[N];
int n,m,tot,num,top,cnt;

void add(int x,int y)
{
    e[++tot].ver=y;e[tot].nex=head[x];head[x]=tot;
}

void tarjan(int x)
{
    dfn[x]=low[x]=++num;
    stack[++top]=x,ins[x]=1;
    for(int i=head[x];i;i=e[i].nex)
        if(!dfn[e[i].ver])
        {
            tarjan(e[i].ver);
            low[x]=min(low[x],low[e[i].ver]);
        }
        else if(ins[e[i].ver]) low[x]=min(low[x],dfn[e[i].ver]);
    if(dfn[x]==low[x])
    {
        ++cnt;
        int y;
        do{
            y=stack[top--],ins[y]=0;
            c[y]=cnt,scc[cnt].push_back(y);
        }while(x!=y);
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
}

e-DCC

void add_c(int x,int y)
{
    vc[++tc]=y;nc[tc]=hc[x],hc[x]=tc;
}
//主函数中
    for(int x=1;x<=n;x++)
        for(int i=head[x];i;i=e[i].nex)
        {
            int y=e[i].ver;
            if(c[x]==c[y]) continue;
            add_c(c[x],c[y]);
        }

2-SAT 模板

#include<bits/stdc++.h>
using namespace std;

const int N=2000000+10;

inline int read()
{
    static int x;
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}

int n,m,tot,num,cnt,top;
int ver[N*2],nex[N*2],head[N],dfn[N],low[N];
int st[N],ins[N],c[N];

void add(int x,int y)
{
    ver[++tot]=y,nex[tot]=head[x],head[x]=tot;
}

void tarjan(int x)
{
    dfn[x]=low[x]=++num;
    st[++top]=x,ins[x]=1;
    for(int i=head[x];i;i=nex[i])
        if(!dfn[ver[i]])
        {
            tarjan(ver[i]);
            low[x]=min(low[x],low[ver[i]]);
        }
        else if(ins[ver[i]]) low[x]=min(low[x],dfn[ver[i]]);
    if(dfn[x]==low[x])
    {
        cnt++;
        int y;
        do{
            y=st[top--],ins[y]=0;
            c[y]=cnt;
        }while(x!=y);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,a,va,b,vb;i<=m;i++)
    {
        scanf("%d%d%d%d",&a,&va,&b,&vb);
        add(a+!va*n,b+vb*n); 
        add(b+!vb*n,a+va*n);
    }
    for(int i=1;i<=n*2;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
    {
        if(c[i]==c[n+i])
        {
            puts("IMPOSSIBLE");
            return 0;
        }
    }
    puts("POSSIBLE");
    for(int i=1;i<=n;i++) printf("%d ",c[i]>c[i+n]);
    return 0;
}

二分图

//留坑

动态规划的一些基本模板

线性 DP

LIS 最长上升子序列

    f[i]=max(f[j]+1)    (j>=0&&j<i,a[j]<a[i])

LCS 最长公共子序列 f[i][j] 表示 a[1~i] 和 b[1~j] 的最长公共子序列

    f[i][j]=max(max(f[i-1][j],f[i][j-1]),f[i-1][j-1]+1(a[i]=b[j]))

数字三角形

    f[i][j]=a[i][j]+max(f[i-1][j],f[i-1][j-1](j>1))

LCIS 最长公共上升子序列

//最优决策集只增不减 

    for(int i=1;i<=n;i++)
    {
        int maxv=1;
        for(int j=1;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            if(a[i]==b[j]) f[i][j]=max(f[i][j],maxv);
            if(b[j]<a[i]) maxv=max(maxv,f[i][j]+1);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);
    printf("%d\n",res);

动态规划难点在于 DP 转移的方法和优化手段，提高的方法就是多做题

背包

0/1 背包

#include<bits/stdc++.h>
using namespace std;

const int N=1010;

int n,v;
int vi[N],wi[N],f[N];

int main()
{
    scanf("%d%d",&n,&v);

    for(int i=1;i<=n;i++) scanf("%d%d",&vi[i],&wi[i]);

    for(int i=1;i<=n;i++)
        for(int j=v;j>=vi[i];j--) f[j]=max(f[j],f[j-vi[i]]+wi[i]);

    printf("%d",f[v]);

    return 0;
}

完全背包

#include<bits/stdc++.h>
using namespace std;

const int N=1010;

int v[N],w[N],f[N]={0};
int n,V;

int main()
{

    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);

    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=V;j++)//从右到左计算
            f[j]=max(f[j],f[j-v[i]]+w[i]);

    printf("%d",f[V]);

    return 0;
}

多重背包

#include<bits/stdc++.h>
using namespace std;

int N,V;
int f[110],vi[110],wi[110],si[110];

int main()
{
    scanf("%d%d",&N,&V);
    for(int i=1;i<=N;i++) scanf("%d%d%d",&vi[i],&wi[i],&si[i]);

    for(int i=1;i<=N;i++)
        for(int j=V;j>=vi[i];j--)
            for(int k=1;k<=si[i];k++)
                if(k*vi[i]<=j) f[j]=max(f[j],f[j-k*vi[i]]+k*wi[i]);

    printf("%d",f[V]);

    return 0;
}

//二进制优化
#include<bits/stdc++.h>
using namespace std;

int N,V,num=1;
int v,w,s;
int vi[25000],wi[25000],f[2000+10];

int main()
{
    scanf("%d%d",&N,&V);

    for(int i=1;i<=N;i++)
    {
        scanf("%d%d%d",&v,&w,&s);
        for(int j=1;j<s;j*=2) {vi[num]=v*j;wi[num++]=w*j;s-=j;}
        if(s) {vi[num]=v*s;wi[num++]=w*s;}
    }
    for(int i=1;i<num;i++)
        for(int j=V;j>=vi[i];j--) f[j]=max(f[j],f[j-vi[i]]+wi[i]); 

    printf("%d",f[V]);

    return 0;
}

分组背包

#include<bits/stdc++.h>
using namespace std;

int n,v,s;
int vi[110],wi[110],f[110];

int main()
{
    scanf("%d%d",&n,&v);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s);
        for(int j=1;j<=s;j++) scanf("%d%d",&vi[j],&wi[j]);

        for(int j=v;j;j--)
            for(int k=1;k<=s;k++)
                if(j>=vi[k]) f[j]=max(f[j],f[j-vi[k]]+wi[k]);
    }

    printf("%d",f[v]);

    return 0;
}

区间 DP 对于给定的区间进行 DP 再一步步扩大区间，得到答案

石子合并 (模型)

#include<bits/stdc++.h>
using namespace std;

const int N=220,inf=1000000;

int a[N],s[N];
int f1[N][N],f2[N][N];
int n;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i+n]=a[i];
    for(int i=1;i<=n*2;i++) s[i]=s[i-1]+a[i];

    for(int l=1;l<n;l++)
        for(int i=1,j=i+l;j<n*2&&i<n*2;i++,j=i+l)       //区间 dp ，先枚举区间长度，再是首尾，再是中间
        {
            f2[i][j]=inf;
            for(int k=i;k<j;k++) 
            {
                f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+s[j]-s[i-1]);
                f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+s[j]-s[i-1]);
            }
        } 

    int maxn=0,minn=inf;
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,f1[i][i+n-1]);
        minn=min(minn,f2[i][i+n-1]);
    }

    printf("%d\n%d",minn,maxn);

    return 0;
}

树形 DP DP 的结构为一棵树

没有上司的舞会 (模型)

int ri[N],v[N];
vector<int> son[N];
int n,f[N][2];
// f[i][0]表示第i个人不参加，f[i][1]表示参加 
void dp(int m)
{
    f[m][0]=0;f[m][1]=ri[m];  //初始化，参加为ri[m],不参加为0 
    for(int i=0;i<son[m].size();i++)
    {  //枚举所有儿子 
        int ni=son[m][i];
        dp(ni);  //把儿子的两种情况dp出来 
        f[m][0]+=max(f[ni][0],f[ni][1]);   
        f[m][1]+=f[ni][0];
        //dp
    }
}

状态压缩

蒙德里安的梦想二进制压缩模型

#include<bits/stdc++.h>
using namespace std;

const int N=15;

int n,m,w;
//w : 兼容方式总数

long long f[N][1<<15];
//f [i][x] 表示第i行且该行的二进制表示为 x 时，共有多少种摆放骨牌的方式。
int path[5000000][2];
//path [j][0] 与 path[j][1] 分别指兼容的两个二进制

//path [10][0] 表示第11种(从 0 计数)兼容方式的前一行二进制形式对应的的值
//path [10][1] 表示第11种(从 0 计数)兼容方式的后一行二进制形式对应的的值
//一共可能有(1<<11)*(1<<11)种兼容方式

//定义如下这种填充表示方式：如果一个骨牌是横着放的，那么它所在的两个方格都填充 1.如果它是竖着放的，那么它所在的两个格子中，上面的那个填 0，下面的这个填 1
void get(int c,int pre,int now)
//得到具有m列的矩阵的所有对应兼容方式存入path中
{
    if(c>m) return ;
    else if(c==m)
    {
        path[w][0]=pre;
        path[w++][1]=now;
        return ;
    }
    get(c+1,(pre<<1)|1,now<<1);
    get(c+1,(pre<<1),(now<<1)|1);
    get(c+2,(pre<<2)|3,(now<<2)|3);
    //当前位不放，则前行的当前位必定为1才能兼容且后行为0：c=c+1，(pre<<1)|1,now<<1
    //当前位上方，则前行的当前位必定为0才能兼容且后行为1：c=c+1，(pre<<1),(now<<1)|1
    //当前位右方，则前行的当前2位必定为1才能兼容且后行当前2位为1：c=c+2，(pre<<1)|3,(now<<1)|3
}

int main()
{
    while(scanf("%d%d",&n,&m)==2&&n&&m)
    {
        w=0;
        if(m>n) swap(m,n);
        get(0,0,0);
        memset(f,0,sizeof(f));
        f[0][(1<<m)-1]=1;
        //假想的第 0 行且二进制形式为全 1 时 出现 1 次
        for(int i=0;i<n;i++)
            for(int j=0;j<w;j++) f[i+1][path[j][1]]+=f[i][path[j][0]];

        printf("%I64d\n",f[n][(1<<m)-1]);
    }

    return 0;
}
//算法竞赛进阶指南代码 :  
int n,m;
long long f[12][1<<11];
bool in_s[1<<11];
int main()
{
    while(cin>>n>>m&&n)
    {
        for(int i=0;i<1<<m;i++)
        {
            bool cnt=0,has_odd=0;
            for(int j=0;j<m;j++)
                if(1>>j&1) has_odd|=cnt,cnt=0;
                else cnt^=1;
            in_s[i]=has_odd|cnt?0:1;
        }
        f[0][0]=1;
        for(int i=1;i<=n;i++)
            for(int j=0;j<1<<m;j++)
            {
                f[i][j]=0;
                for(int k=0;k<1<<m;k++)
                    if((j&k)==0&&in_s[j|k]) f[i][j]+=f[i-1][k];
            }
        cout<<f[n][0]<<endl;
    }
}

传纸条滚动数组优化滚动数组可以节省空间

    for(int i=2;i<=n+m;i++) 
    {
        for(int p=1;i<=i-1;p++)
        {
            if(p>m) break;
            for(int q=1;q<=i-1;q++)
            {
                if(q>m) break;
                int k=(i-1)&1;
                dp[i&1][p][q]=max(max(dp[k][p][q-1],dp[k][p-1][q]),max(dp[k][p-1][q-1],dp[k][p][q]))+f[p][i-p]+f[q][i-q];
                if(p==q) dp[i&1][p][q]-=f[p][i-p];
            }
        }
    }

优化

倍增用 2 的整数次幂进行快速的，跳跃性的状态转移

大部分倍增优化都与 ST 算法相似或相同

开车旅行

void make_st()
{
    int i,j;
    for(j=1;j<=19;j++)
    {
        for(i=1;i<=n;i++)
        {
            f[i][j]=f[f[i][j-1]][j-1];
            stA[i][j]=stA[i][j-1]+stA[f[i][j-1]][j-1];
            stB[i][j]=stB[i][j-1]+stB[f[i][j-1]][j-1];
        }
    }
}

数据结构用之前学的数据结构 (树状数组、线段树等) 优化 DP 过程

单调队列优化

单调队列优化多重背包 + 滚动数组

const int N=20000+10;

int n,m;
int f[N],q[N],g[N];

int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1,v,w,s;i<=n;i++)
    {
        scanf("%d%d%d",&v,&w,&s);
        memcpy(g,f,sizeof(f));
        //滚动数组优化空间，g[]即f[i-1][];
        for(int j=0;j<v;j++)
        {
            int hh=0,tt=-1;
            for(int k=j;k<=m;k+=v)
            {
                f[k]=g[k];
                if(hh<=tt && k-s*v>q[hh]) hh++;
                //如果当前窗口的内容超过了s个;
                if(hh<=tt) f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);
                //max(f[i-1][k],f[i-1][能转移里最大]+个数*v[i]);
                while(hh<=tt && g[q[tt]]-(q[tt]-j)/v*w <= g[k]-(k-j)/v*w) tt--;
                q[++tt]=k;
            }
        }
    }

    printf("%d",f[m]);

    return 0;
}

斜率优化将转移方程看成直线 y=kx+b 根据单调性比较斜率来更新

任务安排 2 (模型)

    for(int i=1;i<=n;i++)
    {
        while(l<r&&(f[q[l+1]]-f[q[l]])<=(s+sumt[i])*(sum[q[l+1]]-sumc[q[l]])) l++;          // k1、k2 
        f[i]=f[q[l]]-(s+sumt[i])*sumc[q[l]]+sumt[i]*sumc[i]+s*sumc[n];
        while(l<r&&(f[q[r]]-f[q[r-1]])*(sumc[i]-sumc[q[r]])>=(f[i]-f[q[r]])*(sumc[q[r]]-sumc[q[r-1]])) r--;
        q[++r]=i;
    }

四边形不等式

如果对于任意的a1≤a2 b1≤b2,有m[a1,b1]+m[a2,b2]≤m[a1,b2]+m[a2,b1],那么m[i,j]满足四边形不等式。

else

//留坑 qwq

最困难的数论

判定质数

bool judge(int x)
{
    if(x<2) return false;
    for(int i=2;i<=sqrt(x);i++)
        if(n%i==0) return false;
    return true;
}

质数的筛选

Eratosthenes 筛选

void primes(int x)
{
    memset(v,0,sizeof(v));
    for(int i=2;i<=x;i++)
    {
        if(v[i]) continue;
        cout<<i<<endl;      //i是质数 
        for(int j=i;j<=x/i;j++) v[i*j]=1;
    }
}

线性筛

int v[N],prime[N];
void primes(int n)
//就是把数拆分成最小质因子相乘
{
    memset(v,0,sizeof(v));
    m=0;
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0)
        {
            v[i]=i;
            prime[++m]=i;
        }
        for(int j=1;j<=m;j++)
        {
            if(prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
        }
    }
    for(int i=1;i<=m;i++) cout<<prime[i]<<endl;
}

质因数分解

void divide(int n)
{
    m=0;
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        //i 是质数 
        {
            p[++m]=i,c[m]=0;
            while(n%i==0) n/=i,c[m]++;  //除掉所有的 i 
        }
    }
    if(n>1) p[++m]=n,c[m]=1;    //n 是质数 
    for(int i=1;i<=m;i++) cout<<p[i]<<'^'<<c[i]<<endl;
}

约数

试除法求 N 的正约数集合

    int factor[],m=0;
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            factor[++m]=i;
            if(i!=n/i) factor[++m]=n/i;
         }
    }
    for(int i=1;i<=m;i++) cout<<factor[i]<<endl;

扩展-倍数法求 1~N 每个数的正约数集合

    vector<int> factor[];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n/i;j++)
            factor[i*j].push_back(i);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<factor[i].size();j++)
            printf("%d ",factor[i][j]);
        puts("");
    }

最大公约数

int gcd(int a,int b) {return b?gcd(a,a%b):a;}

欧拉函数

int phi(int n)
{
    ans=n;
    for(int i=2;i<=sqrt(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 exgcd(int a,int b,int &x,int &y)
{
    if(b==0) {x=1,y=0;return a;}
    int d=exgcd(b,a%b,x,y);
    int z=x;x=y;y=z-y*(a/b);
    return d;
}

乘法逆元

b，m 互质，并且 b | a ，则存在一个整数 x ，使得 a/b,a*x 模 m 同余 ，称 x 为 b 的模 m 乘法逆元

模板

    n=read();p=read();
    inv[1]=1;puts("1");
    for(int i=2;i<=n;i++)
    {
        inv[i]=(ll)(p-p/i)*inv[p%i]%p;
        printf("%d\n",inv[i]);
    }

同余方程求关于 x 的同余方程 a*x,b 模等于 1 的最小正整数解

#define ll long long

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

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

高次同余方程

int baby_step_giant_step(int a,int b,int p)
{
    map<int,int> hash;hash.clear();
    b%=p;
    int t=(int)sqrt(p)+1;
    for(int j=0;j<t;j++)
    {
        int val=(ll)b*power(a,j,p)%p;   //快速幂 
        hash[val]=j;
    }
    a=power(a,t,p);
    if(a==0) return b==0?1:-1;
    for(int i=0;i<=t;i++)
    {
        int val=power(a,i,p);
        int j=hash.find(val)==hash.end()?-1:hash[val];
        if(j>=0&&i*t-j>=0) return i*t-j;
    }
    return -1;
}

矩阵乘法

    int res=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<p;j++)
            for(int k=0;k<m;k++) ans+=a[i][k]*b[k][j];

高斯消元

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=110;

double a[N][N];
int n;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n+1;++j)
            scanf("%lf",&a[i][j]);
    for(int i=1;i<=n;++i)
    {
        int maxn=i;
        for(int j=i+1;j<=n;++j)
            if(fabs(a[j][i])>fabs(a[maxn][i])) maxn=j;
        for(int j=1;j<=n+1;++j) swap(a[i][j],a[maxn][j]);
        if(!a[i][i]){ puts("No Solution"); return 0;}
        for(int j=1;j<=n;++j)
        {
            if(j!=i)
            {
                double x=a[j][i]/a[i][i];
                for(int k=i+1;k<=n+1;++k) a[j][k]-=a[i][k]*x;
            }
        }
    }
    for(int i=1;i<=n;++i) printf("%.2lf\n",a[i][n+1]/a[i][i]);
    return 0;
}

略略略

//留坑 qwq

写在后面 :

~~可能是废话~~
个人认为对知识的的熟练掌握是比较重要的，所以 CPS 考前列了些知识点

最后

祝大家 CPS 2019 RP++ ！！

15 评论

林小胖 2021-10-07 11:05

int lowbit(int x)
{
    return n&-n;
    //return n & (~ n + 1);
}

不太懂这个

Apprentice_lb 2021-11-23 01:44

这个是仅留下x的最低位的1和其之后的0，比如n = 10110000时，-n = 01010000，则有n & -n 结果为00010000。这样就保留最低位的1和其之后的所有0。如果你是不懂为什么(~n + 1)等于-n的话，可以去看一下计算机补码的规则。

啊哈哈HQ 2020-12-30 13:53

###dalao求带

koishi_offical 2020-12-10 20:19

射射你

kyz 2020-10-16 17:07

tql

红色OI再临 2019-11-14 10:12

CPS 2019 RP++ !!!

秦淮岸灯火阑珊 2019-11-12 19:52

大佬省一稳了。大佬分我点RP呗。

銘权 2019-11-12 20:34

qwq

秦淮岸灯火阑珊 2019-11-12 21:00 回复了銘权的评论

QAQ

墨染空 2019-11-12 18:42

墨染空 2019-11-12 18:43

CPS 可还行难道不是SCP收容器吗

秦淮岸灯火阑珊 2019-11-12 19:51 回复了墨染空的评论

ZYzzz 2019-11-12 18:39

美丽！

卐浪天卍 2019-11-12 17:44

大佬省一稳了

Empty 2019-11-12 16:51

大佬！！！

App 内打开

基础知识检查·模板复习

写在前面 :

目录 :

基础

数据结构

搜索

图论

动态规划

数论

基础模板

快速幂

64 位整数乘法

lowbit

整数二进制表示下所有是1的位

树状数组

树状数组求逆序对

树状数组求逆序对扩展

一维前缀和

二维前缀和

1 ~ n 任意取数组合

全排

A ^ B 的所有约数之和

二分

离散化

整数离散化

区间离散化

归并排序

倍增

普通倍增

ST 算法

数据结构综合

栈

队列

邻接表

hash

hash 表

字符串 hash

链表 hash

KMP

Trie

堆

并查集

边带权(银河英雄传说)

线段树

分块

平衡树模板

可持久化数据结构

搜索模型

树的遍历

深度优先遍历

dfs序

树的深度

树的重心

树的宽度优先遍历

拓扑排序

深度优先搜索

深搜模型

剪枝 :

例题：小木棍

迭代加深

双向搜索

广度优先搜索

矩阵距离 (模型)

双端队列 BFS

优先队列BFS

A*

IDA*

图论基础及扩展

最短路

单源最短路

Dijkstra 算法

spfa

分层图最短路

任意两点间的最短路

Floyd

圆方树

定义 : 任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌

最小生成树

kruskal 算法

严格次小生成树

最小 K 度生成树模板

蒙德里安的梦想二进制压缩模型

传纸条滚动数组优化滚动数组可以节省空间

倍增用 2 的整数次幂进行快速的，跳跃性的状态转移

数据结构用之前学的数据结构 (树状数组、线段树等) 优化 DP 过程

斜率优化将转移方程看成直线 y=kx+b 根据单调性比较斜率来更新

试除法求 N 的正约数集合

扩展-倍数法求 1~N 每个数的正约数集合

同余方程求关于 x 的同余方程 a*x,b 模等于 1 的最小正整数解