[DP]数位DP总结

2021-10-30 09:24:18

数位DP总结

By Wine93 2013.7

1.学习链接

[数位DP] Step by Step

http://blog.csdn.net/dslovemz/article/details/8540340

[总结] 数位统计模板

http://www.cnblogs.com/jffifa/archive/2012/08/17/2644847.html

2.各人总结领悟

数位DP关键在于状态的设计,设计状态时要考虑当前状态(如dp[pos][s1][s2]),一旦当前状态确定后,pos后面几位随便怎么填结果都一样.一旦达到这个,状态设计就正确了!

3.例题(已解决)

一. HDU 2089 不要62

http://acm.hdu.edu.cn/showproblem.php?pid=2089

题意:求区间[n,m]数字中不含62的数字个数（0<n≤m<1000000）

分析:简单数位DP (暴力也可以解决)

# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;

# define N 15
int dig[N],dp[N][5];

//statu 6:1 62:2 4:3
int dfs(int pos,int statu,int limit)
{
    int i,s,end,sum=0;
    if(pos==-1)
        return statu==2;
    if(!limit&&dp[pos][statu]!=-1)
        return dp[pos][statu];
    end=limit?dig[pos]:9;
    for(i=0;i<=end;i++)
    {
        s=statu;
        if(s==2||s==1&&i==2||i==4)
            s=2;
        else if(i==6)
            s=1;
        else 
            s=0;
        sum+=dfs(pos-1,s,limit&&i==end);
    }
    if(!limit)
        dp[pos][statu]=sum;
    return sum;
}

int calc(int n)
{
    int len=-1;
    memset(dp,-1,sizeof(dp));
    while(n)
    {
        dig[++len]=n%10;
        n/=10;
    }
    return dfs(len,0,1);
}

int main()
{
//    freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF&&(n+m))
        printf("%d\n",m-n+1-(calc(m)-calc(n-1)));
    return 0;
}

HDU 2089

二. HDU 3555 Bomb

http://acm.hdu.edu.cn/showproblem.php?pid=3555

题意:求[1,N]数字中不含49的数字个数N (1 <= N <= 2^63-1)

分析:简单数位DP

　　# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;

# define LL long long
# define N 20

int dig[N];
LL dp[N][5];

//statu 4:1 49:2
LL dfs(int pos,int statu,int limit)
{
    int i,end,s;
    LL sum=0;
    if(pos==-1)
        return statu==2;
    if(!limit&&dp[pos][statu]!=-1)
        return dp[pos][statu];
    end=limit?dig[pos]:9;
    for(i=0;i<=end;i++)
    {
        s=statu;
        if(s==2||s==1&&i==9)
            s=2;
        else if(i==4)
            s=1;
        else 
            s=0;
        sum+=dfs(pos-1,s,limit&&i==end);
    }
    if(!limit)
        dp[pos][statu]=sum;
    return sum;
}

void calc(LL n)
{
    int len=-1;
    memset(dp,-1,sizeof(dp));
    while(n)
    {
        dig[++len]=n%10;
        n/=10;
    }
    LL ans=dfs(len,0,1);
    printf("%I64d\n",ans);
}

int main()
{
    int t;
    LL n;
//    freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64d",&n);
        calc(n);
    }
    return 0;
　　}

HDU 3555

三. UESTC 1307 windy数

http://www.acm.uestc.edu.cn/code.php?sid=442734

题意:求区间[A,B]之间的windy数 (windy数:不含前导0，并且相邻2个数字之间差至少为2)1 <= A <= B <= 2000000000

分析:状态设计时多加一个前导0，并且记录当前选择的数字(pre)递归到下一位数字选择时利于判断是否相差2

　　　#include<cstdio>
# include<cmath>
# include<cstring>
using namespace std;

typedef long long ll;
# define N 15
ll dp[N][N][5],a,b;
int dig[N];

ll dfs(int pos,int pre,int statu,int limit)   //statu; 1:前面全部是0 2:满足条件 0:不满足条件
{
    int i,end,s;
    ll sum=0;
    if(pos==-1)
        return statu==2;
    if(!limit&&dp[pos][pre][statu]!=-1)
        return dp[pos][pre][statu];
    end=limit?dig[pos]:9;
    for(i=0;i<=end;i++)
    {
        if(statu==1&&i!=0)
            s=2;
        else if(statu==1&&i==0)
            s=1;
        else if(statu==2&&abs((double)(pre-i))>=2)
            s=2;
        else
            continue;
        sum+=dfs(pos-1,i,s,limit&&end==i);
    }
    if(!limit)
        dp[pos][pre][statu]=sum;
    return sum;
}

ll calc(ll n)
{
    int len=-1;
    memset(dp,-1,sizeof(dp));
    while(n)
    {
        dig[++len]=n%10;
        n/=10;
    }
    return dfs(len,0,1,1);
}

int main()
{
    while(scanf("%I64d%I64d",&a,&b)!=EOF)
        printf("%lld\n",calc(b)-calc(a-1));
    return 0;
}

UESTC 1307

四. HDU 3652 B-number

http://acm.hdu.edu.cn/showproblem.php?pid=3652

题意:求[1,n]数字中数字13并且能被13整除的数字个数(1 <= n <= 1000000000).

分析:多加一个状态,记录到当前位的数最后判断下这个数能否被13整除

　　# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;

# define N 15
# define LL long long
LL dp[N][N][N];
int dig[N];

// statu 0:什么都没有 1:含有1 2:含有13 
LL dfs(int pos,int pre,int statu,int limit)
{
    int i,s,end;
    LL res=0;
    if(pos==-1)
        return statu==2&&pre==0;
    if(!limit&&dp[pos][pre][statu]!=-1)
        return dp[pos][pre][statu];
    end=limit?dig[pos]:9;
    for(i=0;i<=end;i++)
    {
        s=statu;
        if(s==2||(s==1&&i==3))
            s=2;
        else if(i==1)
            s=1;
        else
            s=0;
        res+=dfs(pos-1,(pre*10+i)%13,s,limit&&i==end);
    }
    if(!limit)
        dp[pos][pre][statu]=res;
    return res;
}

LL calc(LL n)
{
    int len=-1;
    memset(dp,-1,sizeof(dp));
    while(n)
    {
        dig[++len]=n%10;
        n/=10;
    }
    return dfs(len,0,0,1);
}

int main()
{
    LL n;
    while(scanf("%I64d",&n)!=EOF)
        printf("%I64d\n",calc(n));
    return 0;
　　}

HDU 3652

五. HDU 3709 Balanced Number

http://acm.hdu.edu.cn/showproblem.php?pid=3709

题意:求一个区间[x,y]内是平衡数的数个数 (平衡数:如果一个数能找到一个平衡点,使这个平衡点2边的每个数字乘以这个数字到平衡点距离的积的和相等如 4139就是个平衡数因为4*2 + 1*1 = 9*1) (0 ≤ x ≤ y ≤ 1018)

分析:枚举平衡点,数位DP

# include<cstdio>
# include<cstring>
# include<cmath>
# include<algorithm>
using namespace std;

# define N 20 
# define LL long long

int dig[N];
LL dp[N][N][2005];

LL dfs(int pos,int central,int pre,int limit)
{
    int i,s,end;
    LL res=0;
    if(pos==-1)
        return pre==0;
    if(pre<0)
        return 0;
    if(!limit&&dp[pos][central][pre]!=-1)
        return dp[pos][central][pre];
    end=limit?dig[pos]:9;
    for(i=0;i<=end;i++)
        res+=dfs(pos-1,central,pre+(pos-central)*i,limit&&i==end);
    if(!limit)
        dp[pos][central][pre]=res;
    return res;
}

LL calc(LL n)
{
    if(n<0)
        return 0;
    int len=-1;
    LL res=0;
    while(n)
    {
        dig[++len]=n%10;
        n/=10;
    }
    for(int central=0;central<=len;central++)  //枚举平衡点
        res+=dfs(len,central,0,1);
    return res-len;
}

int main()
{
    int t;
    LL l,r;
     memset(dp,-1,sizeof(dp));
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64d%I64d",&l,&r);
        printf("%I64d\n",calc(r)-calc(l-1));
    }

    return 0;
　　}

HDU 3709

六. HDU 4507吉哥系列故事——恨7不成妻

http://acm.hdu.edu.cn/showproblem.php?pid=4507

题意:求区间[L,R]数字中不满足下列3个条件的数的平方和 (1 <= L <= R <= 10^18)

1、整数中某一位是7；

2、整数的每一位加起来的和是7的整数倍

3、这个整数是7的整数倍；

分析:若求不满足上面条件的数字,简单的数位DP可以解决!但是我们我们要求平方和,则需要维护3个值 (不满足条件的数的个数，这些数的和，这些数的平方和)

如何来求平方和:如果我们求(ab)^2 则求(a*10+b)^2

(ab)^2=(a*10+b)^2

令x=a*10,y=b

则 (x+y)^2=x^2+y^2+2^x^y;

假设枚举到当前pos位时，我们选择的是数8(即x=8),再假设8带头的后面有12,13,是满足条件的,即812,813，那么我们要计算 812^2+813^2

812^2+813^2=(8*100+12)^2+(8*100+13)^2=2*800^2+12^2+13^3+2*800*(12+13)

2*800^2可以直接计算，而12^2+13^2已经通过递归维护好了，而12+13就是我们维护的这些数的和所以，枚举到当前位的平方和=2*当前这个数*以该位开始满足条件的数的个数+以该位开始满足条件的那些数的平方和+2*当前数*以该位开始满足条件的数的和(而这些数的和又可以通过类似的方法进行维护)

所以一次得返回3个值，可以用返回一个存储3个值的节点(起初我用3个数位DP分别维护3个值)

# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;

# define N 20
# define LL long long
# define MOD 1000000007

struct node
{
    LL c,s1,s2;   //个数  连续和 连续平方和 
};

node dp[N][N][N];
LL base[N];
int dig[N];

LL mul(LL a,LL b)
{
    return ((a%MOD)*(b%MOD))%MOD;
}

node dfs(int pos,int pre1,int pre2,int limit)
{
    int i,s,end;
    node cnt,next;
    if(pos==-1)
    {
        cnt.c=(!pre1||!pre2)?0:1;
        cnt.s1=cnt.s2=0;
        return cnt;
    }
    if(!limit&&dp[pos][pre1][pre2].c!=-1)
        return dp[pos][pre1][pre2];
    end=limit?dig[pos]:9;
    cnt.c=cnt.s1=cnt.s2=0;
    for(i=0;i<=end;i++)
    {
        if(i==7)
            continue;
        next=dfs(pos-1,(pre1+i)%7,(pre2*10+i)%7,limit&&i==end);
        cnt.c=(cnt.c+next.c)%MOD;
        cnt.s1=(cnt.s1+mul(mul(i,base[pos]),next.c)+next.s1)%MOD;
        LL a=mul(i,base[pos]),x=mul(a,a);
        cnt.s2=(cnt.s2+mul(x,next.c)+next.s2+2*mul(a,next.s1))%MOD;
    }
    if(!limit)
        dp[pos][pre1][pre2]=cnt;
    return cnt;
}

void init()
{
    int i,j,k;
    base[0]=1;    
    for(i=1;i<N;i++)
        base[i]=(base[i-1]*10)%MOD;
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
            for(k=0;k<N;k++)
                dp[i][j][k].c=-1;
}

LL calc(LL n)
{
    int len=-1;
    while(n)
    {
        dig[++len]=n%10;
        n/=10;
    }
    return dfs(len,0,0,1).s2;
}

int main()
{
    init();
    int t;
    LL l,r,ans;    
//    freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
//    freopen("C:\\Users\\Administrator\\Desktop\\out.txt","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64d%I64d",&l,&r);
        ans=calc(r)-calc(l-1);
        printf("%I64d\n",(ans%MOD+MOD)%MOD);
    }
    return 0;
　　}

HDU 4507

七. SPOJ 10606 Balanced Numbers

http://www.spoj.com/problems/BALNUM/

题意：求区间[A,B]数字中每个偶数数字出现奇数次，每个奇数数字出现偶数次的数的个数1 <= A <= B <= 1019

分析:用3进制表示当前状态,对于0-9的每个数字,0:没出现过，1:出现奇数次 2：出现偶数次则每个状态都可以表示成一个3进制数(注意前导0)

# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;

# define LL long long
# define N 25
LL dp[N][60005];
int dig[N],vis[N],base[N];

bool check()
{
    int i;
    for(int i=0;i<=9;i++)
        if(vis[i])
        {
            if(i&1&&vis[i]&1)
                return 0;
            else if(!(i&1)&&!(vis[i]&1))
                return 0;
        }
    return 1;
}

LL dfs(int pos,int add,int statu,int limit)
{
    int i,s,end,X;
    LL res=0;
    if(pos==-1)
        return check()&&statu;
    if(!limit&&dp[pos][add]!=-1)
        return dp[pos][add];
    end=limit?dig[pos]:9;
    for(i=0;i<=end;i++)
    {
        s=statu;
        if(s==0&&i==0)
            s=0;
        else
            s=1;
        int  flag=0;
        X=add;
        if(s)
        {
            if(vis[i]==0)
                flag=0,vis[i]=1,X=add+base[i];
            else if(vis[i]==1)
                flag=1,vis[i]=2,X=add+base[i];
            else
                flag=2,vis[i]=1,X=add-base[i];
        }
        res+=dfs(pos-1,X,s,limit&&i==end);
        if(s)
            vis[i]=flag;
    }
    if(!limit)    
        dp[pos][add]=res;
    return res;
}

LL calc(LL n)
{
    int len=-1;
    memset(vis,0,sizeof(vis));
    while(n)
    {
        dig[++len]=n%10;
        n/=10;
    }
    return dfs(len,0,0,1);
}

int main()
{
    int i,t;
    LL l,r;
    base[0]=1;
    for(i=1;i<=10;i++)
        base[i]=base[i-1]*3;
    memset(dp,-1,sizeof(dp));
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",calc(r)-calc(l-1));
    }
    return 0;
　　}

SPOJ 10606

八. URAL 1057 Amount of Degrees

题意:求区间[x,y]内，有多少个数可以分解成K个不同B的次方 (1 ≤ X ≤ Y ≤ 231?1).

(1 ≤ K ≤ 20; 2 ≤ B ≤ 10).

分析:先将数字表示成B进制, 然后数位DP，枚举每一位的时候注意不是0就是1,因为要要求k个不同的B进制相加最后判断下是否刚好有k个即可

# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;

# define LL __int64
# define N 100
int dig[N];
int dp[N][N];

int dfs(int pos,int statu,int k,int limit)
{
    int i,s,end,res=0;
    if(pos==-1)
        return statu==k;
    if(!limit&&dp[pos][statu]!=-1)
        return dp[pos][statu];
    end=limit?dig[pos]:9;
    for(i=0;i<=end;i++)
    {
        if(i>1)
            break;
        res+=dfs(pos-1,statu+i,k,limit&&i==end);
    }
    if(!limit)
        dp[pos][statu]=res;
    return res;
}

int calc(int n,int k,int b)
{
    int len=-1;
    while(n)
    {
        dig[++len]=n%b;
        n/=b;
    }
    return dfs(len,0,k,1);
}

int main()
{
//    freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
//    freopen("C:\\Users\\Administrator\\Desktop\\out.txt","w",stdout);
    int x,y,k,b;
    while(scanf("%d%d%d%d",&x,&y,&k,&b)!=EOF)
    {
        memset(dp,-1,sizeof(dp));
        printf("%d\n",calc(y,k,b)-calc(x-1,k,b));
    }
    return 0;
　　}

ural 1057

4.更多题目(未解决)

1. codeforces 55d / SPOJ JZPEXT

2. HDU 4352

3. SGU 258

4. SPOJ 1182 Sorted bit sequence

5. HDU 3271 SNIBB

6. SPOJ 2319 Sequence

7. SGU 390 Tickets

[DP]数位DP总结

码农公寓

相关文章