In mathematics you don't understand things, you just get used to them.

动态 书籍 杂项 关于 友链

标签 dp 下的文章

本文差不多算是翻译了一遍 CF blog?id=45223 就是抄了一遍，看不懂可以去原文。

当然我的翻译并不是完全遵从原文的。

Part. 1 Introduction

平时我们怎么求高维前缀和？容斥对吧，复杂度多少？O(nd×2d)\mathcal{O}(n^{d}\times2^{d})（nn 每维元素个数，默认同阶，dd 维度）。

这好吗？这不好。

Part. 2 Ying Wen

For 个 example，二维，容斥这么写对吧？

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

事实上我们还可以分维来前缀和：

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

复杂度多少？O(nd×d)\mathcal{O}(n^{d}\times d)，厉害吧。

对应到 SOS DP（sum over subsets），我们把每一维整到集合上去来求子集和。

形式化地定义子集和，即给定一个有 2n2^{n} 个元素的数组 AA，定义函数：

sub-sum(mask)=∑i⊆maskAi \text{sub-sum}(mask)=\sum_{i\subseteq mask}A_{i}

写成位运算的形式：

\text{sub-sum}(mask)=\sum_{mask\text{ & }i=i}A_{i}

学过 FWT 的巨佬可能发现了什么，可是这和我没关系。

看不懂？没关系，我们有严谨的代码定义：

for(int mask = 0;mask < (1<<N); ++mask){
    for(int i = 0;i < (1<<N); ++i){
        if((mask&i) == i){
            F[mask] += A[i];
        }
    }
}

这是什么垃圾复杂度，用高维前缀和可得以下代码：

for (int j = 0; j < n; ++j) {
  for (int i = 0; i < (1 << n); ++i) {
    if((i >> j) & 1)  f[i] += f[i ^ (1 << j)];
  }
}

Description

Link.

给定一个升序序列，问是否存在一种方法使得这个升序序列构成一棵 BST 并使一边相连的两点点权互质。

Solution

根据 BST 的性质可知对于一棵以 uu 为根的子树 subtree(u)\text{subtree}(u) 对应原序列中的一段区间，于是对于一个区间 [l,r][l,r]，如果我们选取 kk 作为根，那么 subtree(u)\text{subtree}(u) 的形态就固定下来了。

设 f(i,j,k)f(i,j,k) 为区间 [i,j][i,j] 中以 kk 为根是否能够构成一棵 BST。

这不好，这很差，考虑怎么优化。

观察发现 [l,r][l,r] 的父亲结点一定是 l−1l-1 或 r+1r+1，于是重新设 f(i,j,0 or 1)f(i,j,0\text{ or }1) 表示区间 [i,j−1][i,j-1] 的父结点为 jj 是否合法 / 区间 [i+1,j][i+1,j] 的父结点为 ii 是否合法。

转移即：

f(i−1,j,1)=f(i−1,j,1)∨f(i,k,0)∧f(k,j,1)∧(gcd⁡(ai−1,ak)≠1)f(i,j+1,0)=f(i,j+1,0)∨f(i,k,0)∧f(k,j,1)∧(gcd⁡(aj+1,ak)≠1) f(i-1,j,1)=f(i-1,j,1)\vee f(i,k,0)\wedge f(k,j,1)\wedge(\gcd(a_{i-1},a_{k})\neq1) \\ f(i,j+1,0)=f(i,j+1,0)\vee f(i,k,0)\wedge f(k,j,1)\wedge(\gcd(a_{j+1},a_{k})\neq1)

kk 是区间 DP 的中间点。于是就可以做了，边界与答案显然。

#include<bits/stdc++.h>
#define f(i,j,k) (f[i][j][k])
int n,a[710];
bool f[710][710][2],flag[710][710];
int GCD(int one,int ano)
{
    if(ano==0)    return one;
    else    return GCD(ano,one%ano);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)    scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)    f(i,i,1)=f(i,i,0)=1;
    for(int i=1;i<=n;++i)
    {
        flag[i][0]=1;
        for(int j=i;j<=n;++j)
        {
            flag[i][j]=flag[j][i]=(GCD(a[i],a[j])!=1);
            flag[0][j]=1;
        }
    }
    for(int i=n;i;--i)
    {
        for(int j=i;j<=n;++j)
        {
            for(int k=i;k<=j;++k)
            {
                f(i-1,j,1)|=(f(i,k,0)&f(k,j,1)&flag[i-1][k]);
                f(i,j+1,0)|=(f(i,k,0)&f(k,j,1)&flag[j+1][k]);
            }
        }
    }
    printf((f(1,n,0)|f(1,n,1))?"Yes\n":"No\n");
    return 0;
}

Description

Link.

给定三个数 n,d,modn,d,mod，求有多少种 nn 个点的不同构的树满足：除了度数为 11 的结点外，其余结点的度数均为 dd。答案对质数 modmod 取模。

Solution

感觉这个题好神啊，看 Editorial 看了半天。

先考虑 rooted 情况。设 f(i,j,k)f(i,j,k) 为有 ii 个结点，当前根有 jj 棵 subtree，最大的子树大小不超过 kk 的答案，字数内的结点的度数皆为 given dd（除了当前根本身）。

转移即：

f(i,j,k)=f(i,j,k−1)+(∑l=1l≤d,k×l<if(i−k×l,j−l,k−1)×(f(k,d−1,k−1)+l−1l)) f(i,j,k)=f(i,j,k-1)+\left(\sum_{l=1}^{l\le d,k\times l<i}f(i-k\times l,j-l,k-1)\times\binom{f(k,d-1,k-1)+l-1}{l}\right)

意义我就直接 copy CSDN@forever_shi 了：

　解释一下这个式子，就是你子树大小不超过 kk 的可以从都不超过 k−1k−1 的转移过来，然后我们可以之前子树都是不超过 k−1k−1，现在开始是不超过 kk 的了，也就是在当前选了若干个大小是 kk 的子树，而这几个是一个可重组合，于是乘那个组合数。
#include<bits/stdc++.h>
typedef long long LL;
int n,d,MOD,far[1010],exfar[1010],f[1010][20][1010];
void exGCD(int one,int ano,int &x,int &y)
{
    if(ano==0)
    {
        x=1;
        y=0;
    }
    else
    {
        exGCD(ano,one%ano,y,x);
        y-=(one/ano)*x;
    }
}
int inv(int val)
{
    int res,w;
    exGCD(val,MOD,res,w);
    return (res%MOD+MOD)%MOD;
}
int C(int n,int k) 
{
    if(n<k)    return 0;
    else
    {
        int res=1;
        for(int i=1;i<=k;++i)    res=LL(res)*(n-i+1)%MOD;
        return LL(res)*exfar[k]%MOD;
    }
}
int main()
{
    scanf("%d %d %d",&n,&d,&MOD);
    if(n<=2)
    {
        printf("1\n");
        return 0;
    }
    far[0]=exfar[0]=1;
    for(int i=1;i<=d;++i)    far[i]=LL(far[i-1])*i%MOD;
    for(int i=1;i<=d;++i)    exfar[i]=inv(far[i]);
    for(int i=0;i<=n;++i)    f[1][0][i]=1;
    for(int i=2;i<=n;++i)
    {
        for(int j=1;j<i && j<=d;++j)
        {
            for(int k=1;k<=n;++k)
            {
                f[i][j][k]=f[i][j][k-1];
                for(int l=1;l*k<i && l<=j;++l)
                {
                    if(k>1)    f[i][j][k]=(f[i][j][k]+LL(f[i-k*l][j-l][k-1])*C(f[k][d-1][k-1]+l-1,l)%MOD)%MOD;
                    else    f[i][j][k]=(f[i][j][k]+LL(f[i-k*l][j-l][k-1])*C(f[k][0][k-1]+l-1,l)%MOD)%MOD;
                }
            }
        }
    }
    if(n&1)    printf("%d\n",f[n][d][n>>1]);
    else    printf("%d\n",(f[n][d][n>>1]-C(f[n>>1][d-1][n>>1],2)+MOD)%MOD);
    return 0;
}

Description

Link.

有一棵 nn 个节点的树，其中一个简单路径的集合被称为 kk 合法当且仅当：树的每个节点至多属于其中一条路径，且每条路径恰好包含 kk 个点。

对于 k∈[1,n]k\in [1,n]，求出 kk 合法路径集合的最多路径数。

即：设 kk 合法路径集合为 SS，求最大的 ∣S∣|S|。

Solution

设 f(i)f(i) 为 k=ik=i 时的答案，因为限定了每条路径的结点数，所以 f(i)≤⌊ni⌋f(i)\le\lfloor\frac{n}{i}\rfloor，差不多可以看出 f(i)f(i) 是单调不增的。

然后仔细看这个形式，是不是长得很像数论分块？所以连续 f(i)f(i) 相同的值的块长为至少 n\sqrt{n}。

然后枚举左端点，二分找右端点，求解 f(i)f(i) 应该是常见 trick。

听说直接二分常数很大，所以要写整体二分。我也不会卡常，所以就写整体二分叭。

#include<bits/stdc++.h>
int n,ans[100010],delta,f[100010];
int head[100010],nxt[200010],to[200010],cntot;
void addEdge(int one,int ano) {
    to[++cntot]=ano;
    nxt[cntot]=head[one];
    head[one]=cntot;
}
void dfs(int x,int las,int rule) {
    int fs=0,sc=0;
    for(int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if(y^las) {
            dfs(y,x,rule);
            if(f[y]>=fs) {
                sc=fs;
                fs=f[y];
            }
            else if(f[y]>=sc)    sc=f[y];
        }
    }
    if(fs+sc+1>=rule) {
        f[x]=0;
        ++delta;
    }
    else    f[x]=fs+1;
}
void rawGrass(int l,int r,int fr,int ba) {
    if(l>r || fr>ba)    return;
    if(l^r) {
        int mid=(fr+ba)>>1;
        delta=0;
        dfs(1,0,mid);
        ans[mid]=delta;
        rawGrass(delta,r,fr,mid-1);
        rawGrass(l,delta,mid+1,ba);
    }
    else {
        for(int i=fr;i<=ba;++i)    ans[i]=l;
    }
}
void read(int &hhh) {
    int x=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9')    c=getchar();
    while(c>='0' && c<='9') {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    hhh=x;
}
void write(int x,char las='\n') {
    static int stack[100],top=0;
    do {
        stack[++top]=x%10;
        x/=10;
    }while(x);
    while(top)    putchar(stack[top--]^'0');
    putchar(las);
}
int main() {
    read(n);
    for(int i=1,x,y;i<n;++i) {
        read(x);
        read(y);
        addEdge(x,y);
        addEdge(y,x);
    }
    rawGrass(0,n,1,n);
    for(int i=1;i<=n;++i)    write(ans[i]);
    return 0;
}

「ABC 197A」Rotate

Link.

略。

#include<bits/stdc++.h>
using namespace std;
int main(){
    char a,b,c;cin>>a>>b>>c;cout<<b<<c<<a;
    return 0;
}

「ABC 197B」Visibility

Link.

扫。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int h,w,x,y;cin>>h>>w>>x>>y;vector<string> a(h);--x,--y;
    for(string &i:a)cin>>i;
    int ans=0;
    for(int i=x;~i;--i)if(a[i][y]=='.')++ans;/*,printf("(%d %d)\n",i+1,y+1);*/else break;
    for(int i=x;i<h;++i)if(a[i][y]=='.')++ans;/*,printf("(%d %d)\n",i+1,y+1);*/else break;
    for(int i=y;~i;--i)if(a[x][i]=='.')++ans;/*,printf("(%d %d)\n",x+1,i+1);*/else break;
    for(int i=y;i<w;++i)if(a[x][i]=='.')++ans;/*,printf("(%d %d)\n",x+1,i+1);*/else break;
    cout<<ans-3;
    return 0;
}

「ABC 197C」ORXOR

Link.

二进制枚举暴力算。

#include<bits/stdc++.h>
using namespace std;
long long n,a[30],b[30];
int main(){
    scanf("%lld",&n);for(long long i=1;i<=n;++i){scanf("%lld",&a[i]);}
    long long up=(1<<n),ans=1e18;
    for(long long i=0;i<=up;++i){
        long long ct=1;
        b[ct]=a[1];
        for(long long j=2;j<=n;++j)if(((i>>(j-1))&1)^((i>>(j-2))&1))b[++ct]=a[j];else b[ct]|=a[j];
        long long tmp=0;
        for(long long j=1;j<=ct;++j)tmp^=b[j];
        ans=min(ans,tmp);
    }
    printf("%lld\n",ans);
    return 0;
}

「ABC 197D」Opposite

Link.

数学题，不会，而且读不太懂题。

// Oops, something went wrong.

「ABC 197E」Traveler

Link.

这个题看起来就很 关路灯。

对于每一种颜色（这里的颜色是指我们已经收集完了上一种颜色，正在收集的颜色），我们不可能走过而不拾。

于是收完一种颜色后，我们一定是这种颜色的的最左 / 右边。

然后就可以 DP 了；设 fi,0 or 1f_{i,0\text{ or }1} 为拾 ii-th 颜色，在左 / 右，转移显然。

/*
Denote f[i][0/1] for the minimum time, that we finish collecting the i-th color and we're at the left/right (0/1) endpoint.
f[i][0]=min( f[las][0]+Dist( R[las],L[i] ),f[las][1]+Dist( L[las],L[i] ) )+R[i]-L[i];
f[i][1]=min( f[las][0]+Dist( R[las],R[i] ),f[las][1]+Dist( L[las],R[i] ) )+R[i]-L[i];
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=1e18;
int n;
LL f[200010][2],L[200010],R[200010];
int main()
{
    scanf("%d",&n);
    for( int i=1;i<=n;++i )    L[i]=INF,R[i]=-INF;
    for( int i=1;i<=n;++i )
    {
        LL pos;
        int color;
        scanf( "%lld %d",&pos,&color );
        L[color]=min( pos,L[color] );
        R[color]=max( pos,R[color] );
    }
    #define Dist( x,y ) ( LL( abs( ( x )-( y ) ) ) )
    for( int i=1,las=0;i<=n+1;++i )
    {
        if( L[i]!=INF )
        {
            f[i][0]=min( f[las][0]+Dist( R[las],L[i] ),f[las][1]+Dist( L[las],L[i] ) )+R[i]-L[i];
            f[i][1]=min( f[las][0]+Dist( R[las],R[i] ),f[las][1]+Dist( L[las],R[i] ) )+R[i]-L[i];
            las=i;
        }
    }
    printf( "%lld\n",f[n+1][1] );
    return 0;
}

「ABC 197F」Construct a Palindrome

Link.

相当于是从 11 和 nn 同时走，每次走字母一样的边，直接双向 BFS 即可。

#include<bits/stdc++.h>
using namespace std;
#define turn(c) ((c)-'a')
#define fs first
#define sc second
const int INF=1e9;
vector<int> suf[1010][26];
int n,m,ans=INF,vis[1010][1010];
struct node
{
    int fs,sc,val;
    node(int A=0,int B=0,int C=0){fs=A,sc=B,val=C;}
};
queue<node> q;
int main()
{
    // freopen("in.in","r",stdin);
    // freopen("my.out","w",stdout);
    scanf("%d %d",&n,&m);
    vis[1][n]=1;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        char c=getchar();
        while(c<'a' || c>'z')    c=getchar();
        suf[x][turn(c)].emplace_back(y);
        suf[y][turn(c)].emplace_back(x);
    }
    q.emplace(node(1,n,0));
    while(!q.empty())
    {
        int one=q.front().fs,ano=q.front().sc,lav=q.front().val;
        q.pop();
        if(lav==ans)    return printf("%d\n",ans<<1),0;
        for(int i=0;i<26;++i)
        {
            for(int exone:suf[one][i])
            {
                for(int exano:suf[ano][i])
                {
                    if(exone==ano || exano==one)    return printf("%d\n",lav<<1|1),0;
                    if(exone==exano)    ans=lav+1;
                    if(!vis[exone][exano])
                    {
                        vis[exone][exano]=1;
                        q.emplace(node(exone,exano,lav+1));
                    }
                }
            }
        }
    }
    printf("-1\n");
    return 0;
}

  1. 1
  2. ...
  3. 8
  4. 9
  5. 10
  6. 11
  7. 12
  8. 13
  9. 14
  10. 15