Loj10167 HDU2089 不要62

题目描述

杭州人称那些傻乎乎粘嗒嗒的人为 626262（音：laoer）。

杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。

不吉利的数字为所有含有 444 或 626262 的号码。例如：62315,73418,8891462315,73418,8891462315,73418,88914 都属于不吉利号码。但是，611526115261152 虽然含有 666 和 222，但不是 626262 连号，所以不属于不吉利数字之列。

你的任务是，对于每次给出的一个牌照区间号，推断出交管局今后又要实际上给多少辆新的士车上牌照了。

数位DP板子，遍历时判断每一位，如果是4就continue，如果上一位（记录的）是6，这一位是2，也contine。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#define in(a) a=read()

#define REP(i,k,n)  for(int i=k;i<=n;i++)

using namespace std;

inline int read(){

    int x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

int a,b,n,digit[],dp[][],ind;

inline int dfs(int pos,int state,bool flag){

    if(!pos)  return ;

    if(!flag && dp[pos][state]!=-)  return dp[pos][state];

    int up,ans=;

    if(flag)  up=digit[pos];

    else  up=;

    REP(i,,up){

        if(i==)  continue;

        if(state== && i==)  continue;

        ans+=dfs(pos-,i,flag && i==digit[pos]);

    }

    if(!flag)  dp[pos][state]=ans;

    return ans;

}

inline int solve(int x){

    ind=;

    while(x){

        digit[++ind]=x%;

        x/=;

    }

    digit[ind+]=-;

    return dfs(ind,,);

}

int main(){

    while(scanf("%d%d",&a,&b)!=EOF){

        if(a== && b==)  break;

        memset(dp,-,sizeof(dp));

        printf("%d\n",solve(b)-solve(a-));

    }

}