HDU
Description
杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局常常会扩充一些的士车牌照。新近出来一个好消息。以后上牌照，不再含有不吉利的数字了。这样一来。就能够消除个别的士司机和乘客的心理障碍。更安全地服务大众。
不吉利的数字为全部含有4或62的号码。
比如：
62315 73418 88914
都属于不吉利号码。
可是。61152尽管含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号。判断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input
输入的都是整数对n、m（0<n≤m<1000000），假设遇到都是0的整数对。则输入结束。
Output
对于每一个整数对，输出一个不含有不吉利数字的统计个数。该数值占一行位置。
Sample Input
1 100 0 0
Sample Output
80
思路：打表 ，数据量不大
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000000;
int n, m;
int f[maxn+5];
int check(int num) {
while (num) {
if (num % 10 == 4)
return 0;
if (num % 100 == 62)
return 0;
num /= 10;
}
return 1;
}
int cal(int num) {
int ans = 0;
for (int i = 1; i <= num; i++)
if (check(i))
f[i] = f[i-1] + 1;
else f[i] = f[i-1];
return ans;
}
int main() {
memset(f, 0, sizeof(f));
cal(maxn);
while (scanf("%d%d", &n, &m) != EOF && n+m) {
printf("%d
", f[m]-f[n-1]);
}
return 0;
}
思路：数位DP，属于比較基础的一道，注意最后的flag的推断。这个是为了将数字本身算进去
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1000;
/*
* dp[i][0],表示长度为i。不存在不吉利数字
* dp[i][1],表示长度为i,不存在不吉利数字。且最高位为2
* dp[i][2],表示长度为i,存在不吉利数字
*/
int n, m;
int dp[maxn][3];
void init() {
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
dp[0][1] = dp[0][2] = 0;
for (int i = 1; i < maxn; i++) {
dp[i][0] = dp[i-1][0]*9 - dp[i-1][1];
dp[i][1] = dp[i-1][0];
dp[i][2] = dp[i-1][2]*10 + dp[i-1][1] + dp[i-1][0];
}
}
int cal(int num) {
int len = 0;
int tmp = num;
int bit[maxn];
while (num) {
bit[++len] = num%10;
num /= 10;
}
bit[len+1] = 0;
int ans = 0;
int flag = 0;
for (int i = len; i >= 1; i--) {
ans += dp[i-1][2]*bit[i];
if (flag)
ans += dp[i-1][0]*bit[i];
if (!flag && bit[i] > 4)
ans += dp[i-1][0];
if (!flag && bit[i+1] == 6 && bit[i] > 2)
ans += dp[i][1];
if (!flag && bit[i] > 6)
ans += dp[i-1][1];
if (bit[i] == 4 || (bit[i+1] == 6 && bit[i] == 2))
flag = 1;
}
if (flag)
ans++;
return tmp - ans;
}
int main() {
init();
while (scanf("%d%d", &n, &m) != EOF && n+m) {
printf("%d
", cal(m)-cal(n-1));
}
return 0;
}