题目描述
求 $[n,m]$ 内不包含数位串 “4” 和 “62” 的数的个数。
输入
输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。
输出
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
样例输入
1 100
0 0
样例输出
80
题解
数位dp
设 $f[i][j]$ 表示 $i$ 位数，最高位为 $j$ ，且不出现数位串 “4” 和 “62” 的数的个数。
那么直接枚举上一位，根据是否构成非法串进行转移。
然后对于每组询问转化为 $[1,a)$ 的区间相减，每个区间进行数位dp，先计算位数不满的，再从高位到低位枚举，当前位如果小于 $a$ 的这一位则一定满足区间条件。如果这一位和上一位不构成 “62” 则统计到答案中。
注意当上一位与当前位组成“62”时及时跳出循环。
（貌似本题暴力可过？...）
#include <cstdio>
int f[8][10] , b[8];
void init()
{
int i , j , k;
f[0][0] = b[0] = 1;
for(i = 1 ; i < 8 ; i ++ )
{
b[i] = b[i - 1] * 10;
for(j = 0 ; j < 10 ; j ++ )
for(k = 0 ; k < 10 ; k ++ )
if(j != 4 && !(j == 6 && k == 2))
f[i][j] += f[i - 1][k];
}
}
int calc(int n)
{
int i , j , di = 1 , last = 0 , now , ans = 0;
for(i = 1 ; b[i] <= n ; i ++ )
for(j = 1 ; j < 10 ; j ++ )
ans += f[i][j];
for( ; i ; i -- )
{
now = n / b[i - 1] % 10;
for(j = di ; j < now ; j ++ )
if(!(last == 6 && j == 2))
ans += f[i][j];
if(now == 4 || (last == 6 && now == 2)) break;
di = 0 , last = now;
}
return ans;
}
int main()
{
init();
int n , m;
while(~scanf("%d%d" , &n , &m) && !(n == 0 && m == 0))
printf("%d
" , calc(m + 1) - calc(n));
return 0;
}