链接 来源：牛客网
杭州人称傻乎乎的人为62，而嘟嘟家这里没有这样的习俗。
相比62，他那里的人更加讨厌数字38，当然啦，还有4这个
数字！所以啊，嘟嘟不点都不想见到包含38或者4的数字。
每次给出一个区间[n，m],你能找到所有令人讨厌的数字吗？
输入描述:
多组输入输出； 输入的都是整数对n、m（0<n≤m<1000000）， 如果遇到都是0的整数对，则输入结束。
输出描述:
对于每次的输入 输出全部令人讨厌的数的个数
示例1 输入
1 100 0 0
输出
20
#include <iostream>
#include <cstring>
using namespace std ;
const int len = 7 ;
int dp[8][10] , bit[8] ;//全局变量初始为0，dp[x][y]数组表示长为x的以y打头的所有数中“合法”数的个数，
// 注意首位为0的数也看作x位，例如0123看作4位数，
// 原因：如果不考虑以0开头的数那么dp[3][3] = dp[2][9] + dp[2][8] + ...+ dp[2][2] + dp [2][1] + dp[1][9] + dp[1][8] + ... + dp[1][2] + dp[1][1]
// 若把所有一位数看作以0开头的2位数则实际上dp[3][3] = dp[2][9] + dp[2][8] + ...+ dp[2][2] + dp [2][1] + dp[2][0]
// 所以认为dp[x][0] = dp[x-1][0...9]
// 我们只需要把dp[2][0...9]这些加起来就好了
int n , m ;
void Get_dp() {
dp[0][0] = 1 ;
for ( int i = 1 ; i <= len ; ++i )//长度i从1到7
for ( int j = 0 ; j <= 9 ; ++j )//数值j从0到9
if ( j != 4 )//排除j等于4的情况
for ( int k = 0 ; k <= 9 ; ++k )//第二个数值k从0到9
if ( !( j == 3 && k == 8 ) )//排除j，k为3，8的情况
dp[i][j] += dp[i - 1][k] ;//i从1开始所以i-1不会越界且由于是全局变量默认值为0，所以免去了对i-1是否越界的讨论
/**
* 从长为1位的数，开头的数从0到9，填表
* 状态转移方程：
* dp[x][y] = 0; 若y==4
* dp[x-1][0...9]; 若y!=3（相当于在所有x-1位的合法数前面加了个不是3的数，肯定也是合法数）
* dp[x-1][0...9] - dp[x-1][8]; 若y==3则要排除掉第二位为8的情况
*/
}
int solve( int n ) {//根据表来得出从1到n（实际上没有包括n，因为下面有一句for ( int j = 0 ; j < bit[i] ; ++j )用的小于号，我们先不考虑这细节）的所有合法数的个数
memset( bit , 0 , sizeof( bit ) ) ;//将n分解放入bit数组中
int top = 0 ;//（从n的底位到高位倒序放入）
while ( n ) {
bit[++top] = n % 10 ;
n /= 10 ;
}
int ans = 0 ;//保存所有合法数个数
for ( int i = len ; i >= 1 ; --i ) {//i从数的最高位开始向下
for ( int j = 0 ; j < bit[i] ; ++j )
if ( !( bit[i + 1] == 3 && j == 8 ) )
ans += dp[i][j] ;//排除上一位是3且这一位以8开头的情况
if ( bit[i] == 4 || ( bit[i + 1] == 3 && bit[i] == 8 ) )
break ;//若这一位是4则跳出循环
}
/**
* 这里举个例子解释一下：
* 假设输入n为243
* 那么我们应该将1...243分解成 000...199 200...239 240...242 243
* 对应一下其实就是 dp[3][0...1] dp[2][0...3] dp[1][0...2] dp[0][]恒为0（所以代码中不管数字n是否合法都没有考虑到，最终返回值其实是1...n-1的所有合法数个数）
* 注解 (1) (2) (3)不合法，之后的也是 (4)不合法
*
* (1)从最高位开始
* (2)00...39中的所有合法数前面加一个2还是合法数
* (3)0...2的前面加上一个4出问题了！！，所有的0...2中的合法数变得不合法,应该排除,接下来所以位的分解前面也会加上4，所以直接跳出循环
* if ( bit[i] == 4 || ( bit[i + 1] == 3 && bit[i] == 8 ) )
* break ;//若这一位是4则跳出循环
* (4)这里为什么单独分开来？提示：“小于”号“<”
*
* 其实这些分法都是受到了上面的：
* for ( int j = 0 ; j < bit[i] ; ++j )
* 的影响（注意小于号），也就是按照这条语句来分的
* 需要仔细想想
*/
return ans ;
}
int main() {
Get_dp() ;//打表
while ( cin >> n >> m && ( n || m ) )
cout << m - n + 1 - ( solve( m + 1 ) - solve( n ) ) << endl ;
return 0 ;
}