题目大意：求区间 [n,m] 中数位不包含 4 和 62 的数字的个数。
题解：数位dp。
预处理出 (f[i][j]) 表示 i 位数字中以 j 为第一位的满足条件的数字个数。
对于统计答案来说采用前缀和相减的方式，即：统计出 [0,m] 中有多少满足条件的数减去 [0,n-1] 中满足条件的数字个数即可。
对于求 [0,n] 中满足条件的个数来说，将原问题划分为若干子问题，每个子问题为从第 i 位开始小于 n 的合法数字的个数，显然划分出的子问题不重不漏，因此子问题的方案数的累加即是原问题的方案数。
注意：根据子问题划分可以发现，统计出来的方案数是小于 n 的方案数，即：不包括 n。因此，前缀和相减时要注意是 g[0,m+1] - g[0,n]，g 为统计出的方案数。
代码如下
#include <bits/stdc++.h>
using namespace std;
int n,m,f[8][10],digit[10],tot;
void init(){
f[0][0]=1;
for(int i=1;i<=7;i++)
for(int j=0;j<=9;j++)
for(int k=0;k<=9;k++)
if(j!=4&&!(j==6&&k==2))
f[i][j]+=f[i-1][k];
}
inline void get(int x){
tot=0;
memset(digit,0,sizeof(digit));
while(x)digit[++tot]=x%10,x/=10;
}
int calc(int x){
get(x);
int ret=0;
for(int i=tot;i;i--){
for(int j=0;j<digit[i];j++)
if(j!=4&&!(j==2&&digit[i+1]==6))
ret+=f[i][j];
if((digit[i]==2&&digit[i+1]==6)||digit[i]==4)break;
}
return ret;
}
int main(){
init();
while(scanf("%d%d",&n,&m)&&n&&m){
printf("%d
",calc(m+1)-calc(n));
}
return 0;
}
update on 5.25
数位 dp 的迭代版本细节过多，因此斟酌之后，目前采用递归版。
递归版需要注意的点如下：
- 递归到边界处意味着生成了一个合法的数字，需要返回数字对答案的贡献。
- 递归版本的 dp 值个人感觉没有迭代版本的 dp 含义清晰，不过 dp 的定义一定要保证和搜索框架中传入的参数个数相等，除了 limit 和 lead 位。
- 在判断是否有前导零的时候，尽量在每种情况中讨论符合情况的转移，即：不要将转移的判断条件写在所有转移的前面，这样可能会导致丢解漏解。
- 递归版的优势在于可以很好地处理前导零问题，以及得到的解是区间 [1,n] 的解，与迭代版 [1,n) 不同。
代码如下
#include <bits/stdc++.h>
using namespace std;
int dp[10][10];
int digit[10],tot;
int dfs(int cur,int pre,bool lead,bool limit){
if(!cur)return 1;
if(!lead&&!limit&&dp[cur][pre]!=-1)return dp[cur][pre];
int ret=0;
int bit=limit?digit[cur]:9;
for(int i=0;i<=bit;i++){
if(i==4||(pre==6&&i==2))continue; // 尽量不要将判断条件写在这里，应写在下面每个判断语句中（懒得改了这里
if(!i&&lead)ret+=dfs(cur-1,i,1,limit&&i==bit);
else ret+=dfs(cur-1,i,0,limit&&i==bit);
}
if(!limit&&!lead)dp[cur][pre]=ret;
return ret;
}
int part(int x){
tot=0;
memset(digit,0,sizeof(digit));
do{
digit[++tot]=x%10;
x/=10;
}while(x);
memset(dp,-1,sizeof(dp));
return dfs(tot,0,1,1);
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)&&n+m){
printf("%d
",part(m)-part(n-1));
}
return 0;
}