这题数据量相对比较小，可以暴力打表解决。不过我这里用数位dp 刚开始学数位dp，参考了别人的代码。
//2013-06-27-15.30 #include <stdio.h> #include <string.h> int dp[7][3]; //dp[i][0] 表示不存在不吉利的数字 //dp[i][1] 表示不存在不吉利的数字，且最高位是2 //dp[i][2] 表示存在不吉利的数字 int bit[10]; void init() { dp[0][0] = 1; for (int i = 1; i <= 6; i++) { dp[i][0] = 9*dp[i-1][0] - dp[i-1][1]; dp[i][1] = dp[i-1][0]; dp[i][2] = dp[i-1][2]*10 + dp[i-1][0] + dp[i-1][1]; } } int slove(int n) { int len = 0; int tmp = n; while (n) { bit[++len] = n%10; n /= 10; } bit[len+1] = 0; int ans = 0; bool flag = false; for (int i = len; i; i--) { ans += dp[i-1][2]*bit[i]; if (flag) //高位出现了4或者63 后面的就随意了 ans += dp[i-1][0]*bit[i]; if (!flag && bit[i] > 4) //高位可能出现4的情况 ans += dp[i-1][0]; if (!flag && bit[i+1] == 6 && bit[i] > 2) //高位是6 后一位可能是2 ans += dp[i][1]; if (!flag && bit[i] > 6) //高位可能出现6，要把后面最高位为2计入 ans += dp[i-1][1]; if (bit[i] == 4 || (bit[i+1] == 6 && bit[i] == 2)) flag = true; } return tmp - ans; } int main() { int l, r; init(); while (scanf("%d %d", &l, &r) != EOF && l+r) printf("%d\n", slove(r+1) - slove(l)); return 0; }
