浅说——数位DP

老子听懂了！！！！！

好感动！！！

不说多了：Keywords: 数位DP，二进制，异或。

“在信息学竞赛中，有一类与数位有关的区间统计问题。这类问题往往具有比较浓厚的数学味道，无法暴力求解，需要在数位上进行递推等操作。”——刘聪《浅谈数位类统计问题》

这类问题往往需要一些预处理，这就用到了数位DP。

例题：不要62

需要统计区间[l,r]的满足题意的数的个数，这往往可以转换成求[0,r]-[0,l)

基本思想与方法

有了上述性质，我们就可以从高到低枚举第一次<n对应位是哪一位。

这样之前的位确定了，之后的位就不受n的限制即从00...0~99...9，可以先预处理，然后这时就可以直接统计答案。

预处理F数组。

F[i,st] 代表位数为i（可能允许前导0。如00058也是个5位数），状态为st的方案数。这里st根据题目需要确定。

如i=4,f[i,st]也就是0000~9999的符合条件的数的个数（十进制)

决策第i位是多少(such as 0~9)

F[i,st] = F[i,st] + f[i–1,st']

st'为相对应的状态

参照刚刚所说的基本思路。预处理f数组，然后统计[0,m] - [0,n).

f[i,j]代表开头是j的i位数中不含"62"或"4"的数有几个。

如f[2,6]包含60,61,63,65,66,67,68,69

for(i=;i<=;i++)//因为数据为1000000，所以预处理7位

for(j=;j<=;j++)//第i位

for(k=;k<=;k++)//第i-1位

if(j!=&&!(j==&&k==))f[i][j]+=f[i-][k];

接下来，怎么算出0-n和0-m区间的答案数呢？

用一个通用函数（Cal)：

如456=f[][]+f[][]+f[][]+f[][]+f[][]//(为什么不枚举到5呢？因为再下一位枚举了）

           +f[][]+f[][]+f[][]+f[][]+f[][]//（就是这一位）

           +f[][]+f[][]+f[][]+f[][]+f[][]+f[][]+f[][].
具体代码如下：

#include<cstdio>//最右边是第一位

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

int f[][];

int Cal(int k)//求1~k中有多少符合的数.

{

    int len,digit[],i,j,ans=;

    memset(digit,,sizeof(digit)),len=;//digit[i]为当前的某个数从右到左第i个位置的数是多少.

    while(k>){digit[++len]=k%;k/=;}

    for(i=len;i>=;i--)

    {

        for(j=;j<=digit[i]-;j++)//每一位只能到k的下一位,所以计算的数实际只能到k-1.所以Cal()中传数要加1.

        {

            if(j!=&&!(j==&&digit[i+]==))ans+=f[i][j];

        }

        if(digit[i]==||(digit[i]==&&digit[i+]==))break; //如果这一位本来就没法，则后面的情况报废

    }

    return ans;

}

int main()

{

    int n,m,i,j,k;

    memset(f,,sizeof(f));//f[i][j]为以j开始的且不含"62"和"4"位数为i的个数.

        f[][]=;

        for(i=;i<=;i++)

        {

            for(j=;j<=;j++)//第i位

            {

                for(k=;k<=;k++)//第i-1位

                {

                    if(j!=&&!(j==&&k==))f[i][j]+=f[i-][k];

                }

            }

        }

    while()

    {

        scanf("%d %d",&n,&m);

        if(n==&&m==)break;

        printf("%d\n",Cal(m+)-Cal(n));//因为当前的Cal(k)是计算出从1到k-1的符合条件的数的个数，所以要计算n~m的个数要用Cal(m+1)-Cal(n).

    }

    return ;

}

变式模板题_P2657 [SCOI2009]windy数

这题还是很简单的啦（差点没做出来

个位打表大佬请离开（包括记搜），我这里讲的是DP!!!

首先Cal(b+1)-Cal(a)，大家都懂吧（算了，复制一遍吧<<((因为当前的Cal(k)是计算出从1到k-1的符合条件的数的个数，所以要计算a~b的个数要用Cal(b+1)-Cal(a).))>>）

f[i][j]定义一样，以j开始的且符合条件的总位数为i的答案个数.（好绕啊）

预处理转移不用讲吧：f[i][j]+=f[i-1][k];（还是复制了）

有个小细节，每个一位数答案都为1，所以分f[1][j]=0.

重点讲讲不同之处（Cal函数）：

显然位数比x要小的数字都是合法的都在[1,x）区间内，直接统计就行.(第一次加ans)

位数和x一样最高位的数字比x小的数字都是合法的都在[1,x）区间内直接统计就行(第二次加ans)

位数和x一样，最高位又和x一样我们从左到右扫一遍x各个位子上的数字大小然后枚举合法的该位子上的数[0,9]判断是否合法就行。(第三次加ans)

#include<bits/stdc++.h>

using namespace std;

int f[][];

int a,b;

int digit[],cnt,ans;

void init ()

{

    for (int i=;i<=;i++) f[][i]=;

    for (int i=;i<=;i++)

    for (int j=;j<=;j++)

    for (int k=;k<=;k++)

    if(abs(j-k)>=)

    f[i][j]+=f[i-][k];

}

int Cal(int x)

{

    //freopen("a.in", "r", stdin);

    memset(digit,,sizeof(digit));

    ans=;

    cnt=;

    while(x)

    {

        digit[++cnt]=x%;

        x/=;

    }

    //三种情况

    for (int i=;i<cnt;i++)

    for (int j=;j<=;j++)

    ans+=f[i][j];        //在不到x位数前，所有情况符合。

    for (int i=;i<digit[cnt];i++)  ans+=f[cnt][i];      //x位数，最高位未到digit[cnt]。

    for (int i=cnt-;i>=;i--)//x位数，最高位到digit[cnt]

    {

        for (int j=;j<digit[i];j++)

        if(abs(j-digit[i+])>=)

        ans+=f[i][j];

        if(abs(digit[i]-digit[i+])<)

        break;

    }

    //printf("%d\n",ans);

    return ans;

}

void work()

{

    cin>>a>>b;

    cout<<Cal(b+)-Cal(a)<<'\n';

}

int main()

{

    init();

    work();

    return ;

}

练习：P2602 [ZJOI2010]数字计数

同步题解

加油……

巴特西

浅说——数位DP

最新文章

热门文章