博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
算法竞赛进阶指南修习简记
阅读量：4665 次
发布时间：2019-06-09

本文共 27011 字，大约阅读时间需要 90 分钟。

【一些要要补的东西】

1.

2.20190922日的，虚树，概率（卑微……）

3.支配树，圆方树

0x00基本算法

0x01 位运算

1.补码

2.移位运算

快速幂

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}int a,b,p;int main(){    rd(a),rd(b),rd(p);    int ans=1%p;    for(;b;b>>=1)    {        if(b&1)ans=(long long)ans*a%p;        a=(long long)a*a%p;    }        printf("%d",ans);    re 0;}
View Code

龟速乘

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}typedef long long ll;ll a,b,p;int main(){    /*龟速乘 */    rd(a),rd(b),rd(p);    ll ans=0;    for(;b;b>>=1)    {        if(b&1)ans=(ans+a)%p;        a=(a<<1)%p;    }        printf("%lld",ans);    re 0;}
View Code

3.状压

4.成对变换

5.lowbit

 

0x02递推与递归

1.概论

在三的基础上搞四

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}int n,m,f[16],d[16]; int main(){    memset(f,0x3f,sizeof f);    f[1]=d[1]=1;    inc(i,2,12)    {        inc(j,1,i-1)        f[i]=min(f[i],2*f[j]+d[i-j]);        d[i]=d[i-1]<<1|1;    }    inc(i,1,12)    printf("%d\n",f[i]);    re 0;}
View Code

强势枚举第一层

暴力计算可行度

2.分治

3.分形

恶心的分治模拟

//一道模拟还要开longlong#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}typedef long long ll;struct nide{    ll x,y;}pa,pb; ll N,a,b;inline nide dfs(ll x,ll n){    if(!n)re (nide){
    0,0};     ll len=1ll<<(n-1);//2的n-1次方    ll cnt=1ll<<((n-1)<<1);//4^(n-1),城市数     ll pos=x/cnt;        nide ansnow=dfs(x%cnt,n-1);        if(!pos) re (nide){ansnow.y,ansnow.x};    if(pos==1) re (nide){ansnow.x,len+ansnow.y};    if(pos==2) re (nide){len+ansnow.x,ansnow.y+len};    if(pos==3) re (nide){
    2*len-ansnow.y-1,len-ansnow.x-1};}int main(){    freopen("in.txt","r",stdin);    int T;    rd(T);    while(T--)    {        rd(N),rd(a),rd(b);        pa=dfs(a-1,N);        pb=dfs(b-1,N);        double x=pa.x-pb.x;        double y=pa.y-pb.y;         double ans=sqrt(x*x+y*y);         printf("%.0lf\n",ans*10);    }        re 0;}
View Code

0x03前缀和与差分

1.二维前缀和计算

2.差分化区间修改为单点修改

话说这道题是紫题，您认真的吗

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}ll n,x,last,cnt1,cnt2; int main(){    rd(n);    rd(last);    inc(i,2,n)    {        rd(x);        if(x-last<0)cnt2+=last-x;        else cnt1+=x-last;        last=x;    }    printf("%lld\n",max(cnt1,cnt2));    printf("%lld",abs(cnt1-cnt2)+1);    re 0;}
View Code 

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}map
        
         
          ,bool>existed;int n,m,p,h,d[10010];int main(){    freopen("in.txt","r",stdin);    int x,y;    rd(n),rd(p),rd(h),rd(m);        inc(i,1,m)    {        rd(x),rd(y);        if(x>y)swap(x,y);        if(existed[make_pair(x,y)])continue;        d[x+1]--;        d[y]++;        existed[make_pair(x,y)]=1;    }        int ans=0;    inc(i,1,n)    {        ans+=d[i];        printf("%d\n",ans+h);    }        re 0;}
View Code

0x04二分

1.整数二分

2.实数二分

3.三分

4.二分答案化判定

我就是看到有一道交互题从乡下刚来城市什么见识，就去水了一道

真好玩~

// Forward declaration of compare API.// bool compare(int a, int b);// return bool means whether a is less than b.class Solution {public:    vector
      
        specialSort(int N) {        vector
       
        v;        v.push_back(1);        for(int i=2;i<=N;++i)        {            int l=0,r=v.size()-1;            while(l<=r)            {                int mid=(l+r)>>1;                if(compare(v[mid],i))l=mid+1;                else r=mid-1;            }            v.insert(v.begin()+l,i);        }        return v;    }};
View Code

0x05排序

1.离散化

2.中位数

奇数（n+1）>>1

偶数n/2~n/2+1

0x06倍增

1.基本

2.st算法

0x07贪心

总而言之，就是让你用一种简单的排序或复杂的推式子得到一种最优的贪心celue

 

0x10 基本数据结构

0x11 栈

1.对顶栈

请参见对顶堆，不过堆可能要维护大小之类的东西

2.与Catalan数的不解之缘

3.表达式求值

反正中缀转后缀O(n)

前后缀直接算

4.单调栈

rt

0x12 队列

1.

a.

模拟

b.蚯蚓 

维护3个单调递减的队列

c.双端队列 

从结果出发，排序，按原标号维持先递减后递增的最少块数

 

2.单调队列

最大子序和

0x13链表与邻接表

 

模拟维护存在性

#include
      
       #define re return#define dec(i,l,r) for(int i=l;i>=r;--i)#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9') x=x*10+(c^48);     if(f)x=-x;}const int maxn=100005;int n,hide[maxn],L[maxn],R[maxn],vis[maxn];struct ndoe{    int val,pos;}ans[maxn];struct node{    int val,id;    inline bool operator<(node a)const    {        re val
View Code

 

0x30 Math

其实数学只要就是推理过程

0x31质数

1.质数的判定（试除法||miller_robbin）

2.质数的筛选

eratosthenes筛法

线性筛法

2.质因数的分解

算术基本定理

试除法

0x32约数

1.算术基本定理推论

2.试除法推论

3.倍数法及其推论

见一本通

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}ll n,k,gx;ll ans;int main(){    rd(n);rd(k);    ans=n*k;    for(int x=1;x<=n;x=gx+1)    {        gx=k/x?min(k/(k/x),n):n;        ans-=(k/x)*(gx-x+1)*(x+gx)/2;    }        printf("%lld",ans);    re 0;}
View Code

4.最大公约数

5.更相减损术

6.欧几里得法

7.互质与欧拉函数

8.积性函数

0x33同余

1.同余类以及剩余类

2.费马小定理

3.欧拉定理及推论

 

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(ll i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}ll n;inline int gcd(ll a ,ll b){re b?gcd(b,a%b):a;}inline int Get_phi(ll x){    ll ans=x;    ll largest=sqrt(x);    for(int i=2;i<=largest;++i)    if(x%i==0)    {        ans=ans*(i-1)/i;        while(x%i==0)        x=x/i;     }    if(x!=1)    ans=(ans)*(x-1)/x;     re (ll)ans;}inline ll pow(ll a,ll x,ll mod){    ll ret=1;    while(x)    {        if(x&1)ret=(ret*a)%mod;        a=(a*a)%mod;        x>>=1;    }    re ret;}int main(){//    freopen("in.txt","r",stdin);    int cnt=0;    while(2333)    {        ++cnt;        rd(n);        if(!n)break;                ll mod=n*9/gcd(8,n);                if(gcd(mod,10)!=1){            printf("Case %d: 0\n",cnt);            continue;        }                ll ol=Get_phi(mod);        ll ans=9999999999999999;        inc(i,1,sqrt(ol))        {            if(ol%i)continue;            if(pow(10,i,mod)==1)ans=min(ans,i);            if(pow(10,ol/i,mod)==1)ans=min(ans,ol/i);        }        printf("Case %d: %lld\n",cnt,ans);    }    re 0;}
View Code

4.扩展欧几里得

5.裴蜀定理

6.乘法逆元

7.线性同余方程

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}inline ll exgcd(ll a,ll b,ll &x,ll &y){    if(!b)    {        x=1;y=0;//小心越界         re a;    }        ll d=exgcd(b,a%b,x,y);    ll z=x;    x=y;    y=z-(a/b)*y;    re d;}int main(){    ll a,b,x,y;    rd(a),rd(b);    exgcd(a,b,x,y);        printf("%lld",(x%b+b)%b);    re 0;}
View Code

8.中国剩余定理

表达整数的奇怪方式

9.高次同余方程（大步小步算法）

0x34矩阵乘法

将线性式横摆

若状态矩阵中第x个数对下一单位时间状态矩阵中的第y个数有影响，

则转移矩阵中的第x行第y列要赋予恰当的系数

 

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=65;ll n,m,act,t,ym;ll opt[10][10],num[10][10],f[65];char s[10][10];struct node{    ll a[65][65];    inline void pre()    {        inc(i,0,ym)inc(j,0,ym)        a[i][j]=0;    }    inline void Identity()    {        inc(i,0,ym)a[i][i]=1;     }    inline node operator*(node c)    {        node d;        d.pre();        inc(i,0,ym)inc(j,0,ym)inc(k,0,ym)        d.a[i][j]+=a[i][k]*c.a[k][j];        re d;    }    }J[61],B;inline void muls(ll u[65],node L){    ll w[65];memset(w,0,sizeof(w));    for(int j=0;j<=ym;j++)        for(int k=0;k<=ym;k++)            w[j]+=u[k]*L.a[k][j];    memcpy(u,w,sizeof(w));}inline void mul(ll x){    while(x)    {        if(x&1)muls(f,B);        B=B*B;        x>>=1;    }}int main(){    //freopen("in.txt","r",stdin);    scanf("%lld%lld%lld%lld",&n,&m,&t,&act);    ym=n*m;    char c;    inc(i,1,n)inc(j,1,m)    {        while((c=getchar())<'0'||c>'9');        opt[i][j]=c-48;        num[i][j]=(i-1)*m+j;    }    inc(i,1,act)    scanf("%s",s[i-1]+1);        inc(i,1,n)inc(j,1,m)    {        ll now=opt[i][j],nowx=0,len=strlen(s[now]+1);        inc(k,1,60)        {            J[k].a[0][0]=1;            if(++nowx>len)nowx=1;            switch(s[now][nowx])            {                case 'N':if(i>1)J[k].a[num[i][j]][num[i-1][j]]=1;break;                case 'S':if(i
        
         1)J[k].a[num[i][j]][num[i][j-1]]=1;break;                case 'E':if(j
View Code

 0x35高斯消元与线性空间

1.高斯消元

2.线性空间

0x36组合计数

1.加法原理

2.乘法原理

3.排列与组合数

4.二项式定理

二项式定理

5.多重集的排列与组合

神神奇奇的转化+莫名其妙的多重集组合数

6.lucas定理

欧拉定理+卢卡斯+crt

好题（虽然很基础）

7.catalan数列

0x38 概率与数学期望

大致就是让你找到一个期望值位1的状态，然后推到每一维状态

已知枚举区间的总期望值为1

可知你每次选的了l,r本身就是概率

又由于位运算没有进位的限制

所以我们针对每一位运算，每次O(n)枚举右区间r

#include
      
       #define re return#define dec(i,l,r) for(int i=l;i>=r;--i)#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=100005;int n,a[maxn],b[maxn],last[2];#define D doubleD ans_or,ans_xor,ans_and;inline void work(int k){    D sum=1<
        
         >k)&1;        if(b[i])ans_now+=sum*1.0/n/n;        //区间为1的答案对于三个ans都有贡献        //我就是懒~    }    ans_or+=ans_now;    ans_xor+=ans_now;    ans_and+=ans_now;    last[0]=last[1]=0;    //上一次0,1,出现位置    int c1=0,c2=0;    //出现1的个数和为对当前有贡献的个数c2    //无贡献的个数c1    inc(i,1,n)    {        if(!b[i])//如果这位不是1        ans_or+=sum*last[1]*2.0/n/n;        //异或和才有值=》第一位到最后一次出现1的位子为左边界        else //如果是1        {            ans_or+=sum*(i-1)*2.0/n/n;//左边界任意            ans_and+=sum*(i-1-last[0])*2.0/n/n;//必须是连续的一段1的左边界        }        ans_xor+=sum*2.0*(b[i]?c1:c2)/n/n;        //当前数要异或偶数个1，还是奇数个1才能使当前值为1        ++c1;//累加当前数统计异或数（当前数与当前数异或肯定为0）        if(b[i])swap(c1,c2);//如果当前数为1，要异或个数的1就要轮转        last[b[i]]=i;    }}int main(){    //freopen("in.txt","r",stdin);    rd(n);    inc(i,1,n)rd(a[i]);    inc(i,0,30)//最多只有26位，但反正又不超，保险    work(i);    printf("%.3lf %.3lf %.3lf",ans_xor,ans_and,ans_or);    re 0;}
View Code

只说了1可以到达任意位置，又没说1一定达到n

不如设到达n的期望为一

反向建图

#include
      
       #define re return#define dec(i,l,r) for(int i=l;i>=r;--i)#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}typedef double D;const int maxn=100005;D f[maxn];int n,m,k,in[maxn],hd[maxn],son[maxn];struct node{    int to,nt;    D val;}e[maxn<<1];inline void add(int x,int y,int z){    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;e[k].val=z;} inline void topo(){    queue
        
         q;    q.push(n);        f[n]=0;        while(!q.empty())    {        int x=q.front();        if(x==1)re;        q.pop();                for(int i=hd[x];i;i=e[i].nt)        {            int v=e[i].to;            f[v]+=1.0*(f[x]+e[i].val)/son[v];            --in[v];            if(!in[v])            q.push(v);        }    }}int main(){//    freopen("in.txt","r",stdin);        int x,y,z;    rd(n),rd(m);    inc(i,1,m)    {        rd(x),rd(y),rd(z);        add(y,x,z);        ++in[x];        ++son[x];    }        topo();        printf("%.2lf",f[1]);        re 0;}
View Code

 

0x40 数据结构的膜法变身

0x41 曾经，我也只是一只单纯的并查集

1.路径压缩与按秩合并

如果你学过并查集的话，那么你一定感慨曾见过只穿了路径压缩的冰茶姬

所谓按秩合并就是启发式（小入大）

题：程序自动分析

2.扩展域与边带权

所谓扩展域，也可以理解为一种容易实现的边带权

（以带权的奇偶性来表示是否在同一集合）

不过看来，边带权的可运用性更加广泛

看书，有笔记

0x41 震惊！线段树竟然有一个血缘关系高达99%

的亲戚——短小精悍的树状数组

1.单点修改，区间求和

2.求逆序对

常规做法

3.in combination with 查分

区间修改，单点查询

区间修改，区间查询

你要推一波式子

4.else

首先想到模拟，然后用二分或倍增优化

0x42 你从未见过的船新版本

明明就只是弄个差分，取个绝对值，在球球gcd

为什么我kao了2天

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template 
       
         inline void rd(T &s) {    s = 0;     T w = 1, ch = getchar();     while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }    while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }    s *= w; }#define ll long long#define lowbit(x) (x&(-x))const long long maxn=5e5+5;ll n,m;ll a[maxn],c[maxn],b[maxn];inline void add(int pos,ll x){    for(;pos<=n;pos+=lowbit(pos))        c[pos]+=x;}inline ll sum(int pos){    ll ret=0;    for(;pos;pos-=lowbit(pos))    ret+=c[pos];    re ret;}struct tree {    ll l,r,val;}t[maxn<<2];#define ls rt<<1#define rs rt<<1|1ll gcd(ll a,ll b){b?gcd(b,a%b):a;}inline void build(int rt,int l,int r){    t[rt].l=l;t[rt].r=r;    if(l==r)    {        t[rt].val=b[l];        re;    }        int mid=(l+r)>>1;    build(ls,l,mid);    build(rs,mid+1,r);    t[rt].val=gcd(t[ls].val,t[rs].val);}inline void addt(ll rt,ll pos,ll x){    if(t[rt].l==t[rt].r)    {        t[rt].val+=x;        re ;    }        ll mid=(t[rt].l+t[rt].r)>>1;    if(pos<=mid)addt(ls,pos,x);    else addt(rs,pos,x);    t[rt].val=gcd(t[ls].val,t[rs].val);}inline ll query(ll rt,ll x,ll y){    if(x<=t[rt].l&&t[rt].r<=y)    re abs(t[rt].val);    ll mid=(t[rt].l+t[rt].r)>>1;    ll ans1=0,ans2=0;    if(x<=mid)ans1=query(ls,x,y);    if(y>mid) ans2=query(rs,x,y);    re abs(gcd(ans1,ans2));}int main(){    cin>>n>>m;    inc(i,1,n)    {        scanf("%lld",&a[i]);        b[i]=a[i]-a[i-1];    }    build(1,1,n);        ll x,y,z;    char opt[4];    inc(i,1,m)    {        scanf("%s",opt);        scanf("%lld%lld",&x,&y);        if(opt[0]=='C')        {            scanf("%lld\n",&z);            if(y
View Code

 

0x50 DP大法吼啊

0x51 线性dp

我就是个lj

都是基础的dp+一些小优化

 

还有一些

自己跳过去看吧

0x52 背包

1.0/1背包

滚动数组

倒序

2.完全背包

0/1正序就是

3.多重背包

朴素不如二进制 ，二进制不如单调队列

4.分组背包

某种形式上的0/1

多维0/1背包，考虑适当优化

0x53 区间dp

1.石子合并 欧阳举了无数次例子的题

比较常规的区间dp了

要注意转移时负负得正等运算

#include
      
       #define re  return#define inc(i,l,r) for(int i=l;i<=r;++i) using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x; }const int maxn=105;int n,f[101][101][2],opt[maxn],a[maxn];inline void swup(int &x,int &y){    x^=y^=x^=y;}int main(){//    freopen("in.txt","r",stdin);        rd(n);        inc(i,1,n<<1)inc(j,1,n<<1)    {        f[i][j][1]=-6666666;        f[i][j][0]=77777777;    }    char op[5];    inc(i,1,n)    {        scanf("%s",op);        rd(a[i]);        a[i+n]=a[i];        f[i][i][0]=f[i][i][1]=a[i];         f[i+n][i+n][0]=f[i+n][i+n][1]=a[i];         opt[i]=(op[0]=='t');//为加是true         opt[i+n]=opt[i];    }    int max1,min1,max2,min2;     inc(L,1,n-1)    inc(i,1,n+n-L)    {        int j=i+L;        inc(k,i+1,j)        if(opt[k])//加         {            f[i][j][1]=max(f[i][j][1],f[i][k-1][1]+f[k][j][1]);            f[i][j][0]=min(f[i][j][0],f[i][k-1][0]+f[k][j][0]);        }        else         {            max1=f[i][k-1][1]*f[k][j][1],min1=f[i][k-1][0]*f[k][j][0];            if(max1
        
         ans)    {        ans=f[i][i+n-1][1];        q[cnt=1]=i;    }    else if(ans==f[i][i+n-1][1])    q[++cnt]=i;        printf("%d\n",ans);    inc(i,1,cnt)    printf("%d ",q[i]);    re 0;}
View Code

3.金字塔

要判断每棵子树进出点应该是同一个数，才行

#include
      
       #define ll long long#define re  return#define inc(i,l,r) for(int i=l;i<=r;++i) using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x; }ll n,f[305][305],mod=1000000000;char s[305];//为什么只用枚举第一棵子树呢，一个是防重，也方便统计 inline ll dfs(int l,int r){    if(s[l]!=s[r])re 0;    if(l==r)re 1;    if(f[l][r]!=-1)re f[l][r];        f[l][r]=0;    inc(k,l+2,r)    f[l][r]=(f[l][r]+dfs(l+1,k-1)*dfs(k,r)%mod)%mod;        re f[l][r];}int main(){//    freopen("in.txt","r",stdin);    memset(f,-1,sizeof f);    scanf("%s",s+1);    printf("%lld",dfs(1,strlen(s+1)));     re 0;}
View Code

 0x54 树形dp

1.基础dp

由根分为左右子树两部分情况 

树的最长链

树的最大独立子集

普通树的dp

跟他的儿子与父亲有着不可告人的关系

2.背包类树形dp

分组背包

3.换根与二次扫描法

对于不定根求解

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=200005;int n,m,k,hd[maxn],in[maxn],D[maxn],f[maxn];struct node{    int to,nt,val;}e[maxn<<1];inline void add(int x,int y,int z){    ++in[x];++in[y];    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;e[k].val=z;    e[++k].to=x;e[k].nt=hd[y];hd[y]=k;e[k].val=z;}inline void dfs(int x,int fa){    for(int i=hd[x];i;i=e[i].nt)    {        int v=e[i].to;        if(v==fa)continue;        dfs(v,x);        if(in[v]==1)D[x]+=e[i].val;        else D[x]+=min(D[v],e[i].val);    }}inline void dfs1(int x,int fa){    for(int i=hd[x];i;i=e[i].nt)    {        int v=e[i].to;        if(v==fa)continue;        if(in[x]==1)f[v]=D[v]+e[i].val;        else f[v]=D[v]+min(f[x]-min(D[v],e[i].val),e[i].val);        dfs1(v,x);    }}int main(){    //freopen("in.txt","r",stdin);     int T,x,y,z;    rd(T);    while(T--)    {        rd(n);        k=0;        inc(i,1,n)hd[i]=D[i]=f[i]=in[i]=0;        inc(i,2,n)        {            rd(x),rd(y),rd(z);            add(x,y,z);        }        dfs(1,1);        f[1]=D[1];        dfs1(1,1);                int ans=0;        inc(i,1,n)        if(f[i]>f[ans])        ans=i;        printf("%d\n",f[ans]);    }    re 0;}
View Code

0x55 环形与后效性处理

1.环形

要么开二倍拆链

要么强制选或不选

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x; }const int maxn=4000;int n,m,b,ans,f[maxn][maxn][2],val[maxn];inline void dp(){    inc(now,2,n)    {        int i=now&1;        inc(j,0,min(now-1,m))        {                        f[i][j][0]=max(f[i^1][j][0],f[i^1][j][1]);            if(j)f[i][j][1]=max(f[i^1][j-1][0],f[i^1][j-1][1]+val[now]);        }    }    }inline void pre(){    inc(i,0,1)    inc(j,0,m)    f[i][j][0]=f[i][j][1]=-1147483647;}int main(){    //freopen("in.txt","r",stdin);    rd(n),rd(m);    inc(i,1,n)rd(val[i]);        pre();        f[1][0][0]=f[1][1][1]=0;    dp();    ans=max(f[n&1][m][1],f[n&1][m][0]);         pre();    f[1][1][1]=val[1];//因为会强制不选    dp();    ans=max(ans,f[n&1][m][1]);        printf("%d",ans);    re 0;}
View Code

 

也可以不拆，但拆了更简单

单调队列

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x; }const int maxn=1e6+5;int n,a[maxn<<1],ans;int q[maxn<<1];int main(){    freopen("in.txt","r",stdin);    rd(n);    inc(i,1,n)    {        rd(a[i]);        a[i+n]=a[i];    }        int nn=n/2;    int tail=0,head=1;    inc(i,1,n<<1)    {        if(head<=tail&&i-q[head]>nn)++head;        ans=max(ans,a[q[head]]+a[i]+i-q[head]);        while(head<=tail&&a[i]-i>=a[q[tail]]-q[tail])--tail;        q[++tail]=i;    }         printf("%d",ans);    re 0;}
View Code

2.有后效性

 

0x57 倍增优化dp

1.预处理

数据小，易处理

2.倍增

常数极大

3.求解

为什么这道题不能有scanf读入

#include
      
       #define re return#define ll long long#define dec(i,l,r) for(ll i=l;i>=r;--i) #define inc(i,l,r) for(ll i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=105;ll n1,n2,l1,l2,f[maxn][32];char s1[105],s2[105];int main(){//    freopen("in.txt","r",stdin);    while(cin>>s2>>n2>>s1>>n1)    {        l1=strlen(s1);        l2=strlen(s2);        //PRE        int flag=0;        inc(i,0,l1-1)        {            f[i][0]=0;            ll pos=i;            inc(j,0,l2-1)            {                ll cnt=0;                while(s1[pos]!=s2[j])                {                    pos=(1+pos)%l1;                        if(++cnt>l1+1)                    {                        flag=1;                        break;                    }                }                if(flag) break;                pos=(1+pos)%l1;//下一位开始                                 f[i][0]+=cnt+1;//往后累加一位             }            if(flag)break;        }                if(flag)        printf("0\n");        else         {            //倍增            inc(i,0,30)            inc(j,0,l1-1)            f[j][i+1]=f[j][i]+f[(j+f[j][i])%l1][i];                        ll m=0;        /*    inc(j,0,l1-1)            {
     */                ll pos=0,cnt=0;                dec(i,31,0)                if(pos+f[pos%l1][i]<=n1*l1)                {                    pos+=f[pos%l1][i];                    cnt+=1<
View Code

 

0x60  tulun

0x61 最短路

1.单源最短路

dijkstra+spfa+bellman-ford

正反两遍spfa

分开处理

2.floyd

任意两点最短路

传递闭包

传递关系

 

longlong memset赋0x3f3f3f3f(八位字节会爆）

 

矩阵最短路？？？

0x62最小生成树kuskal+prim

由于最小生成树太水了，所以总要结合一些奇奇怪怪的算法

累和型dp

强制选择型dp

0/1分数型dp

计数型dp

0x63 树的直径与最近公共祖先

1.树的直径

竟然恶心的要用2次dfs（无法求负权）与树形dp（无法求路径）

分别求一次树的直径

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x; }const int maxn=200005;int n,m,k=1,ans,total,K,hd[maxn],d[maxn],deep,fa[maxn];struct node{    int to,nt,val;}e[maxn<<1];inline void add(int x,int y){    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;e[k].val=1;    e[++k].to=x;e[k].nt=hd[y];hd[y]=k;e[k].val=1;}inline void dfs(int x){    for(int i=hd[x];i;i=e[i].nt)    {        int v=e[i].to;        if(v==fa[x])continue;        fa[v]=x;        d[v]=d[x]+e[i].val;        if(d[deep]
View Code

noip n=500的数据之水,n^3都阔以

#include
      
       #define re return#define Min(a,b) (a)<(b)?(a):(b)#define Max(a,b) (a)>(b)?(a):(b)#define inc(i,l,r) for(register int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x; }const int maxn=500005;int n,m,S,k,ans=0x3f3f3f3f,deep;int hd[maxn],dis[maxn],d[maxn],fa[maxn],vis[maxn];struct node{    int to,nt,val;}e[maxn<<1];inline void add(int x,int y,int z){    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;e[k].val=z;    e[++k].to=x;e[k].nt=hd[y];hd[y]=k;e[k].val=z;}inline void dfs(int x){    if(d[deep]
View Code

你看看bzoj n=500000

我巨大的常数都卡不了

#include
      
       #define re return#define Min(a,b) (a)<(b)?(a):(b)#define Max(a,b) (a)>(b)?(a):(b)#define inc(i,l,r) for(register int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x; }const int maxn=500005;int n,m,S,k,ans=0x3f3f3f3f,deep;int hd[maxn],dis[maxn],d[maxn],fa[maxn],vis[maxn];struct node{    int to,nt,val;}e[maxn<<1];inline void add(int x,int y,int z){    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;e[k].val=z;    e[++k].to=x;e[k].nt=hd[y];hd[y]=k;e[k].val=z;}inline void dfs(int x){    if(d[deep]
View Code

2.lca 

3.差分

暗的连锁

附加边产生环

对附加边差分（塞到两点里）

代表从他父亲到他的主要边被几个环覆盖

0个环任意切第二刀

1环绑定切一刀

其他不成立

#include
      
       #define re return#define dec(i,l,r) for(int i=l;i>=r;--i)#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);}const int maxn=1e5+5;int n,m,k,hd[maxn<<1],d[maxn],ans,fa[maxn][25],deep[maxn];struct node{    int to,nt;}e[maxn<<1];inline void add(int x,int y){    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;    e[++k].to=x;e[k].nt=hd[y];hd[y]=k;}inline void dfs(int x,int pre){    deep[x]=deep[pre]+1;     for(int i=0;fa[fa[x][i]][i];++i)        fa[x][i+1]=fa[fa[x][i]][i];        for(int i=hd[x];i;i=e[i].nt)    {        int v=e[i].to;        if(v==pre)continue;        fa[v][0]=x;        dfs(v,x);    }}inline int LCA(int x,int y){    if(deep[x]
        
         =deep[y])        x=fa[x][i];        if(x==y)re x;    dec(i,20,0)    if(fa[x][i]!=fa[y][i])    {        x=fa[x][i];        y=fa[y][i];    }    re fa[x][0];}inline void Get_ans(int x,int pre){    for(int i=hd[x];i;i=e[i].nt)    {        int v=e[i].to;        if(v==pre)continue;        Get_ans(v,x);        d[x]+=d[v];    }    if(!pre)re ;    if(d[x]==1)++ans;    if(!d[x])ans+=m;}int main(){        //freopen("in.txt","r",stdin);    int x,y;    rd(n),rd(m);    inc(i,2,n)    {        rd(x),rd(y);        add(x,y);    }        dfs(1,0);    inc(i,1,m)    {        rd(x),rd(y);        int v=LCA(x,y);        ++d[x];        ++d[y];        d[v]-=2;    }        Get_ans(1,0);        printf("%d",ans);     re 0;}
View Code

 4.lca的综合应用

set应用

dp，dp还是dp

stl,dp

0x65负环与差分约束

1.负环

熟悉的味道，熟悉的配方

是的，0/1分数规划

2.差分约束

转载于:https://www.cnblogs.com/lsyyy/p/11446537.html

你可能感兴趣的文章
how to control project
查看>>
转 python新手容易犯的6个错误
查看>>
第四节 -- 列表
查看>>
Python入门学习笔记4：他人的博客及他人的学习思路
查看>>
webstorm里直接调用命令行
查看>>
关联规则算法之FP growth算法
查看>>
对数组序列进行洗牌
查看>>
决策树
查看>>
团队作业
查看>>
如何避免在简单业务逻辑上面的细节上面出错
查看>>
win7，Ubuntu 12.04 双系统修改启动项顺序三方法
查看>>
python--列表推导式和生成表达式
查看>>
P - Psychos in a Line 单调队列
查看>>
POJ 2653 Pick-up sticks（计算几何）
查看>>
大型网站高并发的架构演变图-摘自网络
查看>>
8丶运行及总结
查看>>
Unity获取手机的电量时间
查看>>
Spring框架：Spring容器具体解释
查看>>
一个完美的世界 访问
查看>>
【PLSQL】package包的使用
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-10-22 04:51:55   当前IP: 3.142.136.177   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我