题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=2089
思路
一切都在代码注释中
AC代码
#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <limits>
#define CLR(a, b) memset(a, (b), sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair<string, int> psi;
typedef pair<string, string> pss;
typedef pair <int, ll> pil;
const double PI = acos(-1.0);
const double E = exp(1.0);
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e2 + 5;
const int MOD = 1e9;
int dp[10][3];
/* * 状态0： dp[i][0] 长度为i 不含有不合格数字的个数 * 状态1： dp[i][1] 长度为i 最高位为2 不含有不合格数字的个数 * 状态2： dp[i][2] 长度为i 含有不合格数字的个数 * 扩展最高位： 意思是在当前长度下 在最高位的左边再加一位 比如说 X 表示 长度为i的所有数字 那么 2X 就表示 扩展最高位为2 长度为i的所有数字 实际上2X的长度为i + 1 */
void init()
{
CLR(dp, 0);
dp[0][0] = 1, dp[0][1] = dp[0][2] = 0;
for (int i = 1; i < 10; i++)
{
dp[i][0] = dp[i - 1][0] * 9 - dp[i - 1][1];
// 加上之前长度为i - 1 状态为0 的所有数字 要筛去状态0 长度为i - 1 扩展最高位为4的所有数字 以及 状态1 长度i - 1 扩展最高位为6的所有数字
dp[i][1] = dp[i - 1][0];
// 状态转移的是 长度为i - 1 状态为0 的所有数字i的扩展最高位为2
dp[i][2] = dp[i - 1][1] + dp[i - 1][0] + dp[i - 1][2] * 10;
// 加上长度为i - 1 状态1 扩展最高位为6 的所有数字 以及长度为i - 1 状态0 扩展最高位为4的所有数字 以及长度为i - 1 状态2 扩展最高位为0-9 的所有数字
}
}
int solve(int x)
{
int bit[10];
CLR(bit, 0);
int pos = 0;
int tmp = x;
while (x)
{
bit[++pos] = x % 10;
x /= 10;
}
bit[pos + 1] = 0;
bool flag = false;
// 标记当目前为止 枚举的高位中 有没有出现过4或者62 true 表示出现过 4 或者 62
int ans = 0;
// ans 记录的是 所有不符合要求的数字 最后答案就是 x - ans
for (int i = pos; i >= 1; i--)
{
ans += dp[i - 1][2] * bit[i];
// 每次先加上 长度为 i - 1 状态为 2 的所有数字
if (flag)
ans += dp[i - 1][0] * bit[i];
// 如果 之前高位出现过 4 或者 62 那么 下面的所有数字实际上都是不符合的
// 这个有点难理解 我刚开始也理解不了
// 其实我们是这样枚举的 比如一个数字 63294 我们可以拆成 60000 + 3000 + 200 + 90 + 4
// 我们在枚举 60000 的时候 ans + dp[4][2] * 6 这个 * 6 实际上是 最高位为 0 - 5的时候 后续四位数的范围是(0000-9999) 的时候 也就是说 这个时候 我们往答案里面更新了 00000-59999 范围内的所有不符合要求的数字
// 那么到下一位的时候 ans + dp[3][2] * 3 也就是 我们枚举了 60000-62999 范围内 所有不符合要求的数字
// 再下一位 枚举的是 63000-63199 范围内 所有不符合要求的数字
// 再下一位 枚举的是 63200-63289 范围内 所有不符合要求的数字
// 再下一位 枚举的是 63290-63293 范围内 所有不符合要求的数字 显然可以发现 63294 这个数字是没有被枚举的 所在在之后 我们要对这个数字 进行判断 如果 这个数 不合理 ans 需要 + 1
else
{
if (bit[i] > 4)
ans += dp[i - 1][0];
// 如果 高位没有出现4或者62 并且此时的最高位数字>4 那么需要 ans 需要加上最高位 为4 后面跟着的不符合要求的数字
if (bit[i + 1] == 6 && bit[i] > 2)
ans += dp[i][1];
// 如果前一高位的数字是6 并且本次高位的数字> 2 那么 ans 需要加上 长度为i 状态为1 的所有数字
if (bit[i] > 6)
ans += dp[i - 1][1];
// 如果本次的最高位> 6 那么 ans 需要加上 长度为i - 1 状态为1 的所有数字
}
if (bit[i] == 4 || (bit[i + 1] == 6 && bit[i] == 2))
flag = true;
// 用来判断 高位是否出现过4或者62 以及判断本数字是否是不合格的数字
}
if (flag)
ans++;
// 若本数字是不合格数字 需要加上
return tmp - ans;
}
int main()
{
init();
int n, m;
while (scanf("%d%d", &n, &m), n || m)
printf("%d\n", solve(m) - solve(n - 1));
}