add 数位DP

[AlghaPorthos]

我遇到的问题是

内容不是很丰富，不能详细讲解内容

我希望能有这样的解决方案

浅谈数位DP

1. 引言

awa最近在康数位DP。7月21日的时候，周老师考虑（仅仅是考虑）让我分享一下自己的人生经验。所以不管最后有没有上去讲，写就完了。到时候不知道能不能用树莓派讲题awa

2. 我完成的题目

由于我做题的顺序和难度显然没有直接关联，所以我用表格记录一下qwq

Task	Difficulty(MAX=5)
LightOJ 1140	4
HDU 2089	2
HDU 3555	2
SPOJ BALNUM	4
SPOJ MYQ10	5

3. 啥叫数位DP？

数位DP通常是求：给定一个闭区间 ，让你求这个区间中满足某种条件的数的总数。

4.例题！

4.1. Light OJ 1140

题意

求：假如手写下$[n,m]$之间所有整数，会写下多少个0？

$0<n,m<2^{32},T<11000$

做法

首先转化：$[n,m]$之间的0的个数=$[1,m]$之间的0的个数$-$ $[1,n-1]$之间的0的个数

考虑从高位开始枚举，枚举当前位，最后统计。我们设当前位为第now位。

我们发现，如果递归到达终点，影响计数的只有0的个数而非0的位置。所以我们用一个值记录下当前位及之前的位含有的0的个数。（cnt）

我们发现，如果当前位之前的位（前now-1位）和上限的前now-1位一模一样的时候，当前位（即第now位）只能填写$[0,上限第now位数字]$之间的数字。所以用一个值判断一下。（ok）

我们发现，如果当前位及之前的位（前now位）都是0(即全前导0)的时候，这些0是不应该被计入的。所以用一个值判断一下。（pre）

考虑使用DFS实现算法，从下一位的子状态中转移而来。子状态的要素有：当前处于第now位，前now位中有cnt个0，以及是否全顶格和是否全前导零的判断（分别为ok，pre）

需要特别注意的是，如果是发现到达递归终点的时候，仍然为全前导0（也就是0），应当记为1个0，否则递归到上一层的时候会认为两位数结尾的0不存在。

为达到更高的效率，我们把前now位中出现cnt个0且既不全前导0，也不全顶格的情况使用 $f[now][cnt]$记录下来，以节约时间。

int dfs(int now,int cnt,int ok,int pre){
//当前处于第now位，前now-1位中有cnt个0，
//ok::是否全顶格，pre:是否全前导0

      if(now==0)//递归终点
		return pre?1:cnt;
	if(f[now][cnt]!=-1&&!ok&&!pre)//记忆化
		return f[now][cnt];顶格g[now]:9;
	//maxk是该位能取到哪些值，受是否全顶格影响。
	for(int i=0;i<=maxk;++i){
		if(pre)//如果全前导0，那么之前的0不应该被记入
			res+=dfs(now-1,0,ok&&(i==maxk),i==0);
		else
			res+=dfs(now-1,cnt+(i==0),ok&&(i==maxk),0);
	}
	if(!ok&&!pre)//记忆化
		f[now][cnt]=res;
	return res;
}

int getans(int u){
	memset(f,-1,sizeof(f));
    int a=u,cnta=0;
    while(a){
        dig[++cnta]=a%10;
        a=a/10;
    }
    return dfs(cnta,0,1,1);
}

4.2. HDU 2089

题意

求：假如手写下$[n,m]$之间所有整数，会有多少数不含有数字4或者连续的62？

做法

考虑dfs求解的时候，记录当前位数字是什么，枚举下一位的数字是什么。如果下一位是4，直接continue；如果当前位是6，并且下一位是2，也continue。

int dfs(int now,int yet,int ok){
	if(now==0)
		return 1;
	int res=0,maxk=ok?dig[now]:9;
	for(int i=0;i<=maxk;++i){
		if(i==4)
			continue;
      	else{
			if(yet==6&&i==2)
				continue;
			res+=dfs(now-1,i,ok&&(i==maxk));
		}
	}
	return res;
}

4.3. HDU 3555

与HDU 2089(4.2.)类似，故跳过。

4.4. SPOJ BALNUM

题意

我们认为：如果一个n位数字被拆分成n个1位数字，出现的任何奇数都有偶数个、任何偶数都有奇数个，则称该数为“平衡数”。此数非彼树

求：$[n,m]$之间的所有整数中，有多少“平衡数”？

解法：

事先声明，我写的比较飘逸，在考场上不建议大家这么玩。我就是吃饱了没事儿干

考虑：在递归时带着当前位，是否全0，是否全顶格以及（每一位是没出现过，还是出现了奇数次，还是赤县了偶数次）的值，一路狂飚。

int dfs(int now,int ful0,int fulc,int c0,int c1,int c2,int c3,int c4,int c5,int c6,int c7,int c8,int c9){
    if(!now){//递归终点
        if((c0==0||c0==2)&&(c1==0||c1==1)&&(c2==0||c2==2)&&(c3==0||c3==1)&&(c4==0||c4==2)&&(c5==0||c5==1)&&(c6==0||c6==2)&&(c7==0||c7==1)&&(c8==0||c8==2)&&(c9==0||c9==1))
            return 1;//判断合法性
        else
            return 0;
    }
    if(!ful0&&!fulc&&f[now][c0][c1][c2][c3][c4][c5][c6][c7][c8][c9]!=-1)//记忆化
        return f[now][c0][c1][c2][c3][c4][c5][c6][c7][c8][c9];
    int res=0,maxk=(fulc==1?dig[now]:9);
    for(int i=0;i<=maxk;++i){
        if(i==0) res+=dfs(now-1,ful0,fulc&&i==dig[now],ful0?0:(c0+1==3?1:2),c1,c2,c3,c4,c5,c6,c7,c8,c9);
	  //i==0时还需要特殊考虑是否全前导零导致0位的计数为0

        if(i==1) res+=dfs(now-1,0,fulc&&i==dig[now],c0,(c1+1==3?1:2),c2,c3,c4,c5,c6,c7,c8,c9);
        if(i==2) res+=dfs(now-1,0,fulc&&i==dig[now],c0,c1,(c2+1==3?1:2),c3,c4,c5,c6,c7,c8,c9);
        if(i==3) res+=dfs(now-1,0,fulc&&i==dig[now],c0,c1,c2,(c3+1==3?1:2),c4,c5,c6,c7,c8,c9);
        if(i==4) res+=dfs(now-1,0,fulc&&i==dig[now],c0,c1,c2,c3,(c4+1==3?1:2),c5,c6,c7,c8,c9);
        if(i==5) res+=dfs(now-1,0,fulc&&i==dig[now],c0,c1,c2,c3,c4,(c5+1==3?1:2),c6,c7,c8,c9);
        if(i==6) res+=dfs(now-1,0,fulc&&i==dig[now],c0,c1,c2,c3,c4,c5,(c6+1==3?1:2),c7,c8,c9);
        if(i==7) res+=dfs(now-1,0,fulc&&i==dig[now],c0,c1,c2,c3,c4,c5,c6,(c7+1==3?1:2),c8,c9);
        if(i==8) res+=dfs(now-1,0,fulc&&i==dig[now],c0,c1,c2,c3,c4,c5,c6,c7,(c8+1==3?1:2),c9);
        if(i==9) res+=dfs(now-1,0,fulc&&i==dig[now],c0,c1,c2,c3,c4,c5,c6,c7,c8,(c9+1==3?1:2));
    }
    if(!ful0&&!fulc)
        f[now][c0][c1][c2][c3][c4][c5][c6][c7][c8][c9]=res;
	return res;
}

4.5. SPOJ MYQ10

题意

求：假如手写下$[n,m]$之间所有整数，会有多少数看起来和在镜子里看起来一模一样？$n,m<10^{44};T<10^5$

注：由于这里考虑到的镜像，只有$0,1,8$的镜像是自己本身。所以，这里的“一模一样”并不是传统意义上的回文串，而是只含有$0,1,8$的回文串。

解法

awa这道卡了我好几个小时。

首先，在数位DP过程中，显然只有$0,1,8$不会被ban。

其次，由于数值超过long long范围，所以$[n,m]=[1,m]-[1,n-1]$不再适用（高精度太麻烦qwq），而是需要对n是否合法进行判断，得出：$[n,m]=[1,m]-[1,n]+check(n)$

镜像解决了，如何判断回文？

我们需要用一个小数组记录一下之前的值。在未超过一半的长度时，只要不超上限就行；在超过一半的长度时，还需要判断是否和与之“镜面对称”的位相等。

需要额外注意的是，这道题的记忆化部分，不需要memset，也不能memset（否则你将T飞）。比较显然的是，对于没有限制的$n$位数，镜像数总是一样的。

int check(char cc[]){//n的特判
    int strc=strlen(cc);
    for(int i=0;i<strc;++i){
        if(!(cc[i]==cc[strc-i-1]&&(cc[i]=='1'||cc[i]=='8'||cc[i]=='0')))
            return 0ll;
    }
    return 1ll;
}
//now:当前位；eff:有效位；fulc:是否全顶格；ful0:是否全0
int dfs(int now,int eff,bool ful0,bool fulc){
    if(now==0)
        return 1ll;
    if(!fulc&&f[now][eff][ful0]!=-1)//记忆化
        return f[now][eff][ful0];
    
    int res=0,maxk=fulc?dig[now]:9;
    for(int i=0;i<=maxk;++i){
        if(i!=0&&i!=1&&i!=8)
            continue;
        b[now]=i;
        if(ful0&&i==0)//全前导0
            res+=dfs(now-1,eff-1,1,0);
        else if(now>eff/2)//未过半程
            res+=dfs(now-1,eff,0,fulc&&(dig[now]==i));//已过半程
        else if(b[now]==b[eff-now+1])
            res+=dfs(now-1,eff,0,fulc&&(dig[now]==i));
    }
    if(!fulc)
        f[now][eff][ful0]=res;
    return res;
}

char cc1[100],cc2[100];
int strc,ansm,ansn;

int get(char cc[]){//处理封装
        strc=strlen(cc);
        for(int i=0;i<strc;++i)
            dig[strc-i]=cc[i]-'0';
        return dfs(strc,strc,1,1);
}

scanf("%s%s",cc1,cc2);
printf("%lld\n",get(cc2)-get(cc1)+check(cc1));

鸣谢

独立完成这一篇文章相当困难，故在撰文过程中，参考了不少材料。在此一并提出感谢。

• [Mathison]数字组成的奥妙——数位dp
  https://www.luogu.org/blog/virus2017/shuweidp

• [OI-Wiki]数位 DP http://oi-wiki.com/dp/number/

我觉得其他这些方案也可以接受

[welcome]

感谢你对 OI Wiki 的关注！记得在 Issue 中表达清楚自己的意思哦～

[ksyx]

ping.

内容不是很丰富，不能详细讲解内容

能不能更简明地说明一下要添加的内容呢？

[Great-designer]

看了半天，内容大致上确实已经有了

https://oi-wiki.org/dp/number/

鸣谢中也给出了本文。

本文的5道题：

• Luogu P2602 数字计数：给定两个正整数 ，求在 中的所有整数中，每个数码（digit）各出现了多少次。
• hdu 2089 不要62：统计一个区间内数位上不能有 4 也不能有连续的 62 的数有多少。
• SCOI2009 windy 数：给定一个区间 ，求其中满足条件 不含前导 且相邻两个数字相差至少为 的数字个数。
• SPOJMYQ10：假如手写下 之间所有整数，会有多少数看起来和在镜子里看起来一模一样？（)
• P3311 数数：我们称一个正整数 是幸运数，当且仅当它的十进制表示中不包含数字串集合 中任意一个元素作为其子串。例如当 时， 是幸运数，、、 不是幸运数。给定 和 ，计算不大于 的幸运数个数。

本issue的5道题：

• Light OJ 1140：假如手写下$[n,m]$之间所有整数，会写下多少个0？
• HDU 2089/HDU 3555：与OI Wiki重复。
• SPOJ BALNUM：如果一个n位数字被拆分成n个1位数字，出现的任何奇数都有偶数个、任何偶数都有奇数个，则称该数为“平衡数”。$[n,m]$之间的所有整数中，有多少“平衡数”？
• SPOJ MYQ10：与OI Wiki重复。

其中，Light OJ的题目与Luogu P2602一致，Luogu P2602是它的超集。这几个题里面似乎只有SPOJ BALNUM有可能写进数位DP页面中，然而本issue写的很是缺乏分析过程。

综上，不认为这是一个需要对数位DP页面进行有效改进的issue。

数位 DP - OI Wiki

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[Great-designer]

看了半天，内容大致上确实已经有了

https://oi-wiki.org/dp/number/

鸣谢中也给出了本文。

本文的5道题：

• Luogu P2602 数字计数：给定两个正整数 ，求在 中的所有整数中，每个数码（digit）各出现了多少次。
• hdu 2089 不要62：统计一个区间内数位上不能有 4 也不能有连续的 62 的数有多少。
• SCOI2009 windy 数：给定一个区间 ，求其中满足条件 不含前导 且相邻两个数字相差至少为 的数字个数。
• SPOJMYQ10：假如手写下 之间所有整数，会有多少数看起来和在镜子里看起来一模一样？（)
• P3311 数数：我们称一个正整数 是幸运数，当且仅当它的十进制表示中不包含数字串集合 中任意一个元素作为其子串。例如当 时， 是幸运数，、、 不是幸运数。给定 和 ，计算不大于 的幸运数个数。

本issue的5道题：

• Light OJ 1140：假如手写下$[n,m]$之间所有整数，会写下多少个0？
• HDU 2089/HDU 3555：与OI Wiki重复。
• SPOJ BALNUM：如果一个n位数字被拆分成n个1位数字，出现的任何奇数都有偶数个、任何偶数都有奇数个，则称该数为“平衡数”。$[n,m]$之间的所有整数中，有多少“平衡数”？
• SPOJ MYQ10：与OI Wiki重复。

其中，Light OJ的题目与Luogu P2602一致，Luogu P2602是它的超集。这几个题里面似乎只有SPOJ BALNUM有可能写进数位DP页面中，然而本issue写的很是缺乏分析过程。

综上，不认为这是一个需要对数位DP页面进行有效改进的issue。

数位 DP - OI Wiki

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛