登录后台

还没有账号?注册一个吧(>ω・*)ノ

页面导航

本文编写于 93 天前,最后修改于 90 天前,其中某些信息可能已经过时。

$$ \huge{数位dp学习笔记} $$

考前才开始认真学数位dp然后发现windy数都写不来

数位dp是一类按照数位上的各种要求统计合法数字个数的dp。(大概目前见过的题就是这样

从最经典的例子讲起。

[SCOI2009] windy 数

不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 windy 数。windy 想知道,在 $a$ 和 $b$ 之间,包括 $a$ 和 $b$,总共有多少个 windy 数?($1 \leq a \leq b \leq 2 \times 10^9$)

这道题基本可以说是数位dp的板子题了,许多数位dp的板子和windy数基本一致,要改的只有核心部分。

首先运用差分(纠正一下是前缀和)的思想,先求出 $[0,a-1]$ 的数的总数,然后用 $[0,b]$ 的数的总数来减。这样就只用考虑上界的问题了。

怎么分别求解两部分区间的总数呢?

int work(int x){
    memset(dp,-1,sizeof(dp));cnt=0;
    while(x){num[++cnt]=x%10;x/=10;}
    return dfs(cnt,-114,1,1);
}

int main(){
    scanf("%d%d",&a,&b);
    printf("%d\n",work(b)-work(a-1));
    return 0;
}

work函数的主要用处:把要求的数(也就是上界)按十进制位分拆至num数组中,完成预处理之后调用dfs函数通过记忆化搜索解决求个数的问题。

下面看一下dfs函数:

/*
pos  当前枚举到pos位置
pre  上一位数字为pre
flag 上一位是否卡上界
lim  是否有前导零 
*/
int dfs(int pos,int pre,bool flag,bool lim){
    if(pos==0)return 1;//一路合法枚举到了最末尾,答案+1
    if(dp[pos][pre]!=-1&&!lim&&!flag)return dp[pos][pre];//记忆化搜索,不包含卡上界的情况哦,因为卡上界和不卡显然答案是不一样的
    int p,res=0,up=(flag?num[pos]:9);//如果卡上界,我们要枚举到的最高位显然就是上界,否则为9
    for(register int i=0;i<=up;i++){
        if(abs(i-pre)<2)continue;//这是题目要求判断的条件
        p=i;if(p==0&&lim)p=-114;//如果有前导0(即目前为止只出现过0),设为-114不影响对上一句的判断
        res+=dfs(pos-1,p,flag&&(p==up),p==-114);//继续搜索下一位,判断前导0,必须一直卡上界才叫卡上界(
    }
    if(!flag&&!lim)dp[pos][pre]=res;//对于前导0和卡上界的情况是没法记忆化的
    return res;
}

没看懂之前一直觉得这玩意儿好复杂不如写递推的版本,但是后来发现这个样子确实要方便许多...

解释一下什么是卡上界以及在哪些情况下卡上界,我就是因为没看懂这个结果多花了一个晚上...

114514这个数来举例。

比如我们枚举到第二位,此时为10????

那么显然后面的数即使取0-9也不会有任何问题。

如果为11????

那么显然,对于下一位我们只能取0-4(不考虑后续条件),如果再取大些我们就超出了要求的范围,即0-114514

所以必须要开一个变量记录当前是否卡上界,而且卡上界必须一直卡,如果之前没有卡那后面就算再大也是不可能超出上限的。

举例,104???114???是不一样的,两者虽然上一位都达到了上限但是显然前者不卡上界。

然后这题就没了。

那么我们继续下一题。

[AHOI2009]同类分布

给出两个数 $a,b$,求出 $[a,b]$ 中各位数字之和能整除原数的数的个数。对于所有的数据,$1 \leq a \leq b \leq 10^{18}$

题很简短,但是不太好写。

这道题和上一道基本差不多,结构照着板子来就可以了。

虽然各种细节还是靠了mjy帮我才写出来

嗯,这道题的一个关键是读题可能只有我这种屑才会把题意理解错

下午刚起床来写这道题,脑子都是昏的,各位数字之和显然小于原数,那么题意显然求 $number\%sum=0$ 的数。

对,我这个nt一开始是反着理解题意的,结果状态都没设对...

言归正传。

/*
pos  当前枚举到pos位置
sum  各位数字之和
fro  我们正在算的原数(在模mod意义下)
mod  模数,如果mod==sum才会算作一个答案
flag 上一位是否卡上界
合法的情况:pos==0 and fro%mod==0 and mod==sum
*/
int dfs(int pos,int sum,int fro,int mod,int flag){
    if(sum>mod)return 0;//显然sum一旦大于mod就再也不会等于mod了
    if(pos==0)return sum==mod&&fro==0;//判断合法
    if(~dp[pos][sum][fro]&&!flag)return dp[pos][sum][fro];//记忆化
    int res=0,up=flag?num[pos]:9;//一样的判断上界
    for(register int i=max(0ll,mod-sum-9*pos);i<=up;i++)res+=dfs(pos-1,sum+i,(fro*10+i)%mod,mod,flag&&(i==num[pos]));
    //这一行后半部分应该很好懂
    //i=max(0ll,mod-sum-9*pos)是剪枝,如果后面全填9还不够,那显然是不行的
    if(!flag)dp[pos][sum][fro]=res;
    return res;
}

int work(int x){
    int res=0;cnt=0;
    while(x){num[++cnt]=x%10;x/=10;}
    for(register int i=1;i<=9*cnt;i++)memset(dp,-1,sizeof(dp)),res+=dfs(cnt,0,0,i,1);//我们枚举mod,因为sum最大不超过9*18=162所以不会T掉
    return res;
}

版权属于:Crab_Dave

转载时须注明出处及本声明