题意：给你一个区间[n, m]， 求在这个区间有多少个不含有不吉利数字的个数。（不吉利的数字为所有含有4或62的号码。）
Input
输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。（如：[1, 100]）
Output
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。（80）
还没有学数位dp之前，我用暴力做的，现在用数位dp再做了一次。
状态转移方程：dp[i][j] += dp[i - 1][k];dp[i][j]表示以j为前导的i位数满足条件的有多少个。
#include <iostream>
#include <vector>
using namespace std;
int dp[7][10];
void init() {
dp[0][0] = 1;//初始化，画一下图就知道了
for (int i = 1; i <= 7; ++i)//i代表数字的位数
for (int j = 0; j < 10; ++j)//j表示前导
for (int k = 0; k < 10; ++k)
if ((j != 4) && !(j == 6 && k == 2))
dp[i][j] += dp[i - 1][k];//开头为 j 的 i 位数的满足条件的个数
}
int solve(int n) {
vector<int> vec;
while (n) {//将数字拆分
vec.push_back(n % 10);
n /=10;
}
vec.push_back(0);//
int ans = 0;
for (int i = vec.size() - 2; i >= 0; --i) {
for (int j = 0; j < vec[i]; ++j) {
if (j != 4 && !(j == 2 && vec[i + 1] == 6))
ans += dp[i + 1][j];//加上以j为开头的个数，因为前导位都是相同的
}
if (vec[i] == 4 || (vec[i] == 2 && vec[i + 1] == 6))
break;//如果满足，则后面的都会以此为开头， 则全都不符合条件
}
return ans;
}
int main() {
init();
int a, b;
while (cin >> a >> b && a + b) {
cout << solve(b + 1) - solve(a) << endl;//在solve函数中并没有考虑b是不是不幸数的情况，因此sole(b+1)表示[1, b]的个数，而solve(a)表示[1, a)个数，所以[a, b]就是solve(b + 1) - solve(a)
}
return 0;
}
顺带贴上暴力代码：
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 1e6;
int arr[MAX_N];
int main() {
memset(arr, false, sizeof(arr));//将所有数字利用hash思想打表
for (int i = 1; i < MAX_N; ++i) {
int num = i;
while (num) {
if (num % 10 == 4) {
arr[i] = true;//如果是不吉利数字，就为真
break;
}
if(num % 100 == 62) {
arr[i] = true;
break;
}
num /= 10;
}
}
int n, m;
while (scanf("%d%d", &n, &m) != EOF && (n || m)) {
int ans = 0;
for (int i = n; i <= m; ++i)
if (!arr[i]) ++ans;
printf("%d\n", ans);
}
return 0;
}
题意：如果一个数满足任意高位大于低位且高位%低位等于0，就称这样的数为漂亮数，如841是，845不是，输出[l, r]区间中这样的数字个数。
与上一个题思路差不多，不过有一些需要注意的地方。
#include <iostream>
#include <vector>
using namespace std;
int dp[11][10];
void init() {
for (int i = 1; i < 10; ++i)
dp[1][i] = 1;//个位数均是漂亮数
for (int i = 2; i < 11; ++i)
for (int j = 1; j < 10; ++j)
for (int k = 1; k <= j; ++k)
if (j % k == 0) dp[i][j] += dp[i - 1][k];
}
int solve(int n) {
vector<int> vec;
while (n) {
vec.push_back(n % 10);
n /= 10;
}
int ans = 0;
for (int i = 1; i < vec.size(); ++i)//计算从1到最高位前导位为 0 的美丽数的和
for (int j = 1; j < 10; ++j)
ans += dp[i][j];
vec.push_back(2520);//2520为1到9的公约数，解决最高为数为前导的情况
for (int i = vec.size() - 2; i >= 0; --i) {
for (int j = 1; j < vec[i]; ++j) {
if (vec[i + 1] != 0 && vec[i + 1] % j == 0)
ans += dp[i + 1][j];
}
if (vec[i] == 0 || vec[i + 1] % vec[i] != 0) break;
}
return ans;
}
int main() {
init();
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
cout << solve(b + 1) - solve(a) << endl;
}
return 0;
}
