题目大意：

  • 不吉利的数字为所有含有4或62的号码

  • 输入的都是整数对n、m（0<n≤m<100000000000），如果遇到都是0的整数对，则输入结束。

  • 对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

    分析：

    数位DP的模版题:

  1. 定义：

  • f[i][0]表示i位数中吉利数字且末尾非6的个数

  • f[i][1]表示i位数中末尾为6的吉利数字的个数（因为它再加一个2就为不吉利的数字了 ）

  • f[i][2]表示i位数中不吉利数字的个数

  1. 初始化： 
for(int i=1;i<=12;i++){
        f[i][0]=9*f[i-1][0]-f[i-1][1];//加入的数不是4，不是6 
        f[i][1]=f[i-1][0];//加入6
        f[i][2]=10*f[i-1][2]+f[i-1][1]+f[i-1][0];//加入任意数，2和4 
    }
  1. 得出答案： 
long long ask(long long x){//只需求出所有不吉利的数，再用总个数减去不吉利的数就可以了 
    long long ans=x,num=0,a[15]={0},bj=0;
    while(x)a[++num]=x%10,x/=10;
    for(int i=num;i>=1;i--){
        ans-=f[i-1][2]*a[i];//由上位所有不吉利数推导
        if(bj)ans-=f[i-1][0]*a[i];//之前出现不吉利的数字
        else{
            if(a[i]>4)ans-=f[i-1][0];//出现4
            if(a[i]>6)ans-=f[i-1][1];//出现6
            if(a[i+1]==6&&a[i]>2)ans-=f[i][1];//出现62
        }
        if(a[i]==4||(a[i+1]==6&&a[i]==2))bj=1;
    }
    return ans;
}
  1. 注意：
  • l和r要加一 
while(~scanf("%lld%lld",&l,&r)&&(l||r))//一个数等于0可以继续
    printf("%lld\n",ask(r+1)-ask(l));
  • 不开long long见祖宗

下面是我的代码：

#include<bits/stdc++.h>
using namespace std;
long long f[15][3],l,r;
/*
f[i][0]表示i位数中吉利数字且末尾非6的个数
f[i][1]表示i位数中末尾为6的吉利数字的个数，因为它再加一个2就为不吉利的数字了 
f[i][2]表示i位数中不吉利数字的个数
*/
long long ask(long long x){//只需求出所有不吉利的数，再用总个数减去不吉利的数就可以了 
    long long ans=x,num=0,a[15]={0},bj=0;
    while(x)a[++num]=x%10,x/=10;
    for(int i=num;i>=1;i--){
        ans-=f[i-1][2]*a[i];//由上位所有不吉利数推导
        if(bj)ans-=f[i-1][0]*a[i];//之前出现不吉利的数字
        else{
            if(a[i]>4)ans-=f[i-1][0];//出现4
            if(a[i]>6)ans-=f[i-1][1];//出现6
            if(a[i+1]==6&&a[i]>2)ans-=f[i][1];//出现62
        }
        if(a[i]==4||(a[i+1]==6&&a[i]==2))bj=1;
    }
    return ans;
}
int main(){
    f[0][0]=1;
    for(int i=1;i<=12;i++){
        f[i][0]=9*f[i-1][0]-f[i-1][1];//加入的数不是4，不是6 
        f[i][1]=f[i-1][0];//加入6
        f[i][2]=10*f[i-1][2]+f[i-1][1]+f[i-1][0];//加入任意数，2和4 
    }
    while(~scanf("%lld%lld",&l,&r)&&(l||r)/*一个数等于0可以继续*/)printf("%lld\n",ask(r+1)-ask(l));
    return 0;
}