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

时间：2023-05-09 14:05:14

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

题解：这是数位DP的入门题了，首先要理解数DP的原理，DP[i][j]：代表第i位的第j值，举个栗子：如4715   数位数是从右向左的，则第一位是5，第二位是1，第三位是7，第四位是4。所以如果要求0到4715，ans=dp[4][x]+dp[3][y]+dp[2][z]+dp[1][k]

0<=x<=4(但是4要去掉),0<=y<=9,0<=z<=9,0<=k<=9（还要注意判断，把其中62，和4去掉）

AC代码：

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

typedef long long ll;

typedef unsigned long long ull;

#define prN printf("\n")

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d%d",&(N),&(M))

#define SIII(N,M,K) scanf("%d%d%d",&(N),&(M),&(K))

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

const int MAX_N= + ;

const double eps= 1e- ;

int dp[][];

int sol(int n)

{

    int *dig=new int [];

    int len=;

    while(n)

    {

        dig[len++]=n%;

        n/=;

    }

    int ans=;

    for (int i=len-; i!=; i--)

    {

        for (int j=; j<dig[i]; j++)

        {

            if (j!=&&!(dig[i+]==&&j==))

                ans+=dp[i][j];

        }

        if (dig[i]==||(dig[i]==&&dig[i+]==))

            break;

    }

    return ans;

}

int main()

{

#ifndef ONLINE_JUDGE

//    freopen("C:\\Users\\Zmy\\Desktop\\in.txt","r",stdin);

//    freopen("C:\\Users\\Zmy\\Desktop\\out.txt","w",stdout);

#endif // ONLINE_JUDGE

    dp[][]=;

    for (int i=; i<=; i++)

    {

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

        {

            for (int k=; k<=; k++)

            {

                if (j!=&&(j!=||k!=))

                {

                    dp[i][j]+=dp[i-][k];

                }

            }

        }

    }

    int l,r;

    while(cin>>l>>r,l||r)

    {

        cout<<sol(r+)-sol(l)<<endl;

    }

    return ;

}

相关文章