学步园

题意:

找出给定区间中不含有4或62的数的个数.

思路:

本题和Bomb比较像,但是多了一个条件->也不能有4.于是可以想到

先求出part1:不含4的数的个数;

再求part2:不含4且含有62.

其实不需要两个dp,因为求part2的时候dp[i][0]+dp[i][2]就等于dp4[i].

但是这道题就让我对Bomb有更清楚的认识了:这道题关键字是49,用的时候将数++,虽然是因为这种计算本来就只能计算<N的数,
但是同时也掩盖了一个问题,49+1是50,十位自动+1,于是十位的4就可以被读取,但是若把关键字换为48,就得特判一下了;就像本题.///***

还有一个细节问题,在Bomb和windy数中都注意了的,就是高一位的bit[i] = 0;我一直以为我写了的...其实是没写,总是错.
看来对于细节还是略显草率了啊.

另外:给逼得没招了学会了对拍→ →

#include <cstdio>

using namespace std;

const int MAXN = 8;
int dp4[MAXN],dp[MAXN][3];
int len;
int bit[MAXN];
void InitDP()
{
    dp4[0] = 1;
    for(int i=1;i<MAXN;i++)
        dp4[i] = dp4[i-1]*9;
    dp[0][0] = dp[0][1] = 0;
    dp[0][2] = 1;
    for(int i=1;i<MAXN;i++)
    {
        dp[i][0] = dp[i-1][0]*9 + dp[i-1][1];
        dp[i][1] = dp[i-1][2];
        dp[i][2] = dp[i-1][2]*9 - dp[i-1][1];
    }
    //for(int i=0;i<MAXN;i++)
    //    printf("%d:\t\t%d\t%d\t%d\n",i,dp[i][0],dp[i][1],dp[i][2]);
}

void pre(int x, int &len)
{
    int i;
    for(i=1; x; i++)
    {
        bit[i] = x % 10;
        x /= 10;
    }
    bit[i] = 0;
    len = i-1;
    //for(i=len; i; i--)
    //    printf("bit[%d] = %d\n",i,bit[i]);
}

int cal(int x)
{
    int part1 = 0,part2 = 0;
    for(int i=len; i; i--)
    {
        for(int j=0;j<bit[i];j++)
            if(j!=4)    part1 += dp4[i-1];
        if(bit[i]==4) break;
    }
    bool flag = 0;
    for(int i=len; i; i--)
    {
        for(int j=0;j<bit[i];j++)
        {

            if(j!=4)
            {
                part2 += dp[i-1][0];
                if(flag)    part2 += dp[i-1][2];
                if(!flag && bit[i+1]==6 && j==2) part2 += dp[i-1][2];///***
                if(!flag && j==6)    part2 += dp[i-1][1];
            }
        }
        if(bit[i]==4)   break;
        if(bit[i]==2 && bit[i+1]==6)    flag = 1;
    }
    //printf("up to %d\texcluding 4 but with 62: %d\n",x,part2);
    return part1-part2;
}

int main()
{
    int n,m;
    InitDP();
    while(scanf("%d %d",&n,&m)==2 && (n+m))
    {
        int ansn,ansm;
        pre(++m,len);
        ansm = cal(m);
        pre(n,len);
        ansn = cal(n);
        printf("%d\n",ansm-ansn);
    }
}