不要62（HDU 2089数位dp入门）

时间：2021-08-20 03:00:11

题意：统计区间 [a,b] 中不含 4 和 62 的数字有多少个。

分析：dp[i][f]数字表示不含 4 和 62的前提下，剩余长度为 len ，首位是否为 6 的个数。

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  1000000007;

int dp[10][2],bit[10],n,m;

int dfs(int i,int f,bool e){

    if(i==0)return 1;

    if(!e&&dp[i][f]!=-1)

        return dp[i][f];

    int num=0,l=e?bit[i]:9;

    for(int j=0;j<=l;++j)

    {

        if(j==4||(f&&j==2))

            continue;

        num+=dfs(i-1,j==6,e&&(j==l));

    }

    return e?num:dp[i][f]=num;

}

int solve(int x1){

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

    int len=0,x=x1;

    while(x){

        bit[++len]=x%10;

        x/=10;

    }

    dfs(len,0,1);

}

int main()

{

    while(~scanf("%d%d",&n,&m)){

        if(m==0&&n==0)break;

        printf("%d\n",solve(m)-solve(n-1));

    }

return 0;

}

相关文章