题目描述
杭州人称那些傻乎乎粘嗒嗒的人为 $62$(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有 $4$ 或 $62$ 的号码。例如:$62315,73418,88914$ 都属于不吉利号码。但是,$61152$ 虽然含有 $6$ 和 $2$,但不是 连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照号区间 $[n,m]$,推断出交管局今后又要实际上给多少辆新的士车上牌照了。
输入格式
输入包含多组测试数据,每组数据占一行。
每组数据包含一个整数对 $n$ 和 $m$。
当输入一行为“0 0”时,表示输入结束。
输出格式
对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。
数据范围
$1 \le n \le m \le 10^9$
输入样例:
1 100
0 0
输出样例:
80
这题与 Windy数类似,甚至还要更简单
#include <iostream>
#include <cstring>
const int N = 18, M = 10;
using namespace std;
int f[N][M];
int s[N], ls;
int l, r;
int calc(int u, int pre, int limit)
{
if(!u) return 1;
if(!limit && f[u][pre] != -1) return f[u][pre];
int res = 0;
int up = s[u];
if(!limit) up = 9;
for(int i = 0;i <= up;i ++)
{
if(i == 4 || (pre == 6 && i == 2)) continue;
res += calc(u - 1, i, limit && (i == up));
}
if(!limit) f[u][pre] = res;
return res;
}
int dp(int x)
{
ls = 0;
while(x) s[++ ls] = x % 10, x /= 10;
memset(f, -1, sizeof f);
return calc(ls, 0, 1);
}
int main()
{
while(cin >> l >> r)
{
if(!l && !r) break;
cout << dp(r) - dp(l - 1) << endl;
}
return 0;
}