朴素写法

#include <bits/stdc++.h>
using namespace std;
int L, R;
int dp[10][10]; // dp[i][j]: i开头的j位数有多少个方案
// 预处理dp数组
void init()
{
    for (int i = 0; i <= 9; i++)
        if (i == 4)
            dp[i][1] = 0;
        else
            dp[i][1] = 1;
    for (int j = 2; j <= 7; j++) // 位数
    {
        for (int i = 0; i <= 9; i++) // 最高位
        {
            // 计算 dp[i][j]
            dp[i][j] = 0;
            if (i == 4)
                continue;
            for (int k = 0; k <= 9; k++) // 枚举j-1位上的数
            {
                if (k == 4)
                    continue;
                if (i == 6 && k == 2)
                    continue;
                dp[i][j] += dp[k][j - 1];
            }
        }
    }
}
// 计算 0~x 不含有不吉利成分的数的数量
int d[10], dlen;
int cal(int x)
{
    if (x == 0)
        return 1;
    dlen = 0;
    for (int i = x; i != 0; i /= 10)
        d[++dlen] = i % 10;
    // d[dlen] -> d[1]
    int last = 0; // 第i位的上一位
    int res = 0;
    for (int i = dlen; i >= 1; i--)
    {
        int now = d[i]; // 第i位上数字是now
        // 完整的部分
        for (int j = 0; j < now; j++)
        {
            if (j == 4)
                continue;
            if (last == 6 && j == 2)
                continue;
            res += dp[j][i];

            // cout<<"add"<<j<<" "<<i<<"="<<dp[j][i]<<"\n";
        }
        // 不完整的部分
        if (now == 4)
            break;
        if (last == 6 && now == 2)
            break;
        last = now;
        if (i == 1)//如果 x 本身合法
            res++;//把 x 本身算上
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    while (cin >> L >> R)
    {
        if (L == 0 && R == 0)
            break;
        cout << cal(R) - cal(L - 1) << "\n";
    }
    return 0;
}

dfs 写法

#include <bits/stdc++.h>
using namespace std;
int L, R;
int dp[10][2];//记忆化搜索 dp[pos][sta]
int d[10], dlen;//d[dlen]~d[1]
//做到了第 pos 位，前一位是 pre，pre==6，是否顶到了上限
int dfs(int pos, int pre, int sta, bool limit)
{
    if (pos == 0)
        return 1;
    //算过了没贴边的结果的话就直接返回
    if (!limit && dp[pos][sta] != -1)
        return dp[pos][sta];
    //当前这一位的上限
    int up = limit ? d[pos] : 9;
    int sum = 0; //记录方案数
    for (int now = 0; now <= up; now++)//枚举当前这一位
    {
        if (pre == 6 && now == 2)
            continue;
        if (now == 4)
            continue;
        sum += dfs(pos - 1, now, now == 6, limit && now == d[pos]);
    }
    //如果前面没贴边，就记忆化一下
    if (!limit)
        dp[pos][sta] = sum;
    return sum;
}
// 计算 0~x 不含有不吉利成分的数的数量
int cal(int x)
{
    if (x == 0)
        return 1;
    dlen = 0;
    for (int i = x; i != 0; i /= 10)
        d[++dlen] = i % 10;
    return dfs(dlen, 0, 0, true);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> L >> R)
    {
        if (L == 0 && R == 0)
            break;
        memset(dp, -1, sizeof(dp));
        cout << cal(R) - cal(L - 1) << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int L, R;
int dp[10][10];  // 记忆化搜索 dp[pos][pre]
int d[10], dlen; // d[dlen]~d[1]
// 做到了第 pos 位，前一位是 pre，是否顶到了上限
int dfs(int pos, int pre, bool limit)
{
    if (pos == 0)
        return 1;
    // 算过了没贴边的结果的话就直接返回
    if (!limit && dp[pos][pre] != -1)
        return dp[pos][pre];
    // 当前这一位的上限
    int up = limit ? d[pos] : 9;
    int sum = 0;                        // 记录方案数
    for (int now = 0; now <= up; now++) // 枚举当前这一位
    {
        if (pre == 6 && now == 2)
            continue;
        if (now == 4)
            continue;
        sum += dfs(pos - 1, now, limit && now == d[pos]);
    }
    // 如果前面没贴边，就记忆化一下
    if (!limit)
        dp[pos][pre] = sum;
    return sum;
}
// 计算 0~x 不含有不吉利成分的数的数量
int cal(int x)
{
    if (x == 0)
        return 1;
    dlen = 0;
    for (int i = x; i != 0; i /= 10)
        d[++dlen] = i % 10;
    return dfs(dlen, 0, true);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> L >> R)
    {
        if (L == 0 && R == 0)
            break;
        memset(dp, -1, sizeof(dp));
        cout << cal(R) - cal(L - 1) << "\n";
    }
    return 0;
}