数位DP之数字计数
嗯，这将是我本人写的第一篇博客。不知怎的，学到数位dp，又恰好A掉了数字计数，就想开设自己的博客了。算了，废话少说，进入正题了。题目链接.
给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。
题意大概是给定两个数a,b，求区间[a,b]内0~9这些数码出现的次数，其中a,b可能爆int，因而要开longlong。本题思路也不算复杂，若完全按照数位dp的思想，在记忆化搜索时传递记录10个数码出现次数的结构体，多开一位数组记录前几位固定的数的总数，每次搜索处理本位上数字的出现次数，并吸收下层搜索结果。搜索用10来处理前导零。到了搜索边界后，使个位上对应的数字总数+1即可。最后，求出1~a,1~b的情况后，再用差分思想即可得出最终答案。本人蒟蒻，明明这么简单的题还调了四个多小时。
#include<iostream>#include<cstdio>#include<cstring>#definelllonglongusingnamespacestd;structnode{lltot[11];node(){//构造函数for(inti=0;i<=10;i++){tot[i]=0;}}}f[25][25];intnum[15];lla,b;nodedfs(intpos,intnu,boolpd){if(pos<=0){nodean;if(nu==10){an.tot[10]=0;}else{an.tot[10]=1;an.tot[nu]=1;//处理个位}returnan;}if(~f[pos][nu].tot[10]&&!pd){returnf[pos][nu];}nodean;intend=pd?num[pos]:9;for(inti=0;i<=end;i++){nodeans;if(nu==10&&i==0){ans=dfs(pos-1,10,pd&&(i==end));//处理前导零}else{ans=dfs(pos-1,i,pd&&(i==end));}an.tot[10]+=ans.tot[10];//计次数for(intj=0;j<=9;j++){an.tot[j]+=ans.tot[j];//吸收下层搜索结果}}an.tot[nu]+=an.tot[10];//前几位数字固定的数不止一个，会使本位数重复出现if(!pd){f[pos][nu]=an;//记忆化}returnan;}nodesolve(llx){inttot=0;while(x){num[++tot]=x%10;x/=10;}returndfs(tot,10,true);}intmain(){//freopen(".in","r",stdin);scanf("%lld%lld",&a,&b);memset(f,-1,sizeof(f));nodeaa=solve(a-1);//差分nodebb=solve(b);intf=1;for(inti=0;i<=9;i++){if(f)f=0;elseprintf("");printf("%lld",bb.tot[i]-aa.tot[i]);}return0;}
