[hdu2089][不要62] (数位dp)

Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

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

Output

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

Sample Input

1 100
0 0

Sample Output

Solution

基础的数位dp

对于初始化，我们枚举第几位，再枚举当前数字填0~9，后枚举前一位填了什么数字，只要满足不含‘4’或‘62’，就可以从前一位转移过来

用f[i][j]代表当前是第i位填了数字j的方案，从高位到低位dp

每个case计算时用的是累死前缀和的做法，注意一下区间的开闭和初始化清零就行了

#include <stdio.h>
#include <string.h>
inline int Rin() {
    int x=0,c=getchar(),f=1;
    for(;c<48||c>57;c=getchar())
        if(!(c^45))f=-1;
    for(;c>47&&c<58;c=getchar())
        x=(x<<1)+(x<<3)+c-48;
    return x*f; }
int f[8][12],zt[8],len;
void pre_dp() {
    f[0][0]=1;
    for(int i=1;i<=7;i++)
        for(int j=0;j<=9;j++)
        for(int k=0;k<=9;k++)
            if(j^4 && !(j==6 && k==2))
                f[i][j]+=f[i-1][k]; }
int getans(int x) {
    if(x<0)return 0;
    if(!x)return 1;
    for(len=0;x;x/=10)
        zt[++len]=x%10;
        zt[len+1]=0;
    int res=0;
    for(int i=len;i;i--) {
        for(int j=0;j<zt[i];j++)
            if(j^2 || zt[i+1]^6)
                res+=f[i][j];
        if(zt[i]==4 || zt[i+1]==6 && zt[i]==2)
            break; }
    return res; }
int main() {
    pre_dp();
    int n=Rin(),m=Rin();
    while(n&&m) {
        printf("%d
",getans(m+1)-getans(n));
        n=Rin(),m=Rin(); }
    return 0; }

这是一种比较直观的解法，其实因为此题仅涉及到3个数字可以有另一种写法

设f[i][0],f[i][1],f[i][2]分别代表第i位不存在不吉利数字、不存在但第一位为2、存在不吉利数字

在求解时，求区间内存在不吉利数字的情况数，用总数相减

一道‘4’和‘37’的题

#include<stdio.h>
#include<string.h>
int A,B,f[11][3],b[11];
void Prepare(){
    f[0][0]=1;
    for(int i=1;i<=10;i++)
        f[i][0]=9*f[i-1][0]-f[i-1][1],
        f[i][1]=f[i-1][0],
        f[i][2]=f[i-1][2]*10+f[i-1][0]+f[i-1][1];
}
int solve(int n){
    int l=0,ans=0;
    for(int x=n;x;x/=10)
        b[++l]=x%10;
        b[l+1]=0;
    bool advanced=false;
    for(int i=l;i;i--){
        ans+=f[i-1][2]*b[i];
        if(advanced)
            ans+=f[i-1][0]*b[i];
        else{
            if(b[i]>4)
                ans+=f[i-1][0];
            if(b[i]>3)
                ans+=f[i-1][1];
            if((!(b[i+1]^3))&&b[i]>7)ans+=f[i][1];
            if((!(b[i]^4))||((!(b[i+1]^3))&&(!(b[i]^7))))
                advanced=1;
        }
    }
    if(advanced)ans++;
    return n-ans;
}
int main(){
    Prepare();
    freopen("exam.in","r",stdin);
    freopen("exam.out","w",stdout);
    scanf("%d%d",&A,&B);
    printf("%d
",solve(B)-solve(A-1));
    fclose(stdin);
    fclose(stdout);
    return 0;
}