HDU-3652-B-number

水深无声 2022-03-24 14:44 86阅读 0赞

## 原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=3652][http_acm.hdu.edu.cn_showproblem.php_pid_3652] ##

# B-number #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 9349    Accepted Submission(s): 5573**

**Problem Description**

A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.

**Input**

Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).

**Output**

Print each answer in a single line.

**Sample Input**

13 100 200 1000

**Sample Output**

1 1 2 2

**Author**

wqb0039

**Source**

[2010 Asia Regional Chengdu Site —— Online Contest][2010 Asia Regional Chengdu Site _ Online Contest]

**Recommend**

lcy   |   We have carefully selected several similar problems for you:  [3651][] [3655][] [3654][] [3653][] [3659][]

题目大意：给你一个区间，让你在这个区间内找到一个有连续13并且能整除13的数的个数

思路：这种题一眼就看出来是个数位DP，但是如何去求解？？我们平常都是找一个数就行了例如49，62那些题，这道题加了一个整除，我们该如何去做？？

我们可以开一个3维dp数组dp    dp\[nl\]\[mod\]\[judge\]///nl表示位数judge表示判断条件mod表示对3取模的数

然后judge又有三种状态：0：上一位不是1，1：上一位是1（只需要判断此位是否为3）2：为13，满足条件；

所以代码为：

/*
    题意：给你一个区间让你找到这个区间内出现连续13且能被13整除的数的个数
    思路：数位dp，
    */
    #include<set>
    #include<map>
    #include<stack>
    #include<queue>
    #include<string>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define eps 1e-9
    #define ll long long
    #define inf 0x3f3f3f3f
    #define bug printf("mmp\n");
    #define ul unsigned long long
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T()int test,q=1,tt;scanf("%d",&test),tt=test;while(test--)
    const int N=1e2+10;
    const int maxn=1e6+100;
    const int mod=1000000007;
    const double PI=acos(-1.0);
    ll number[N];
    ll dp[N][N][N];
    ///dp[nl][mod][judge]///nl表示位数judge表示判断条件mod表示对3取模的数
    ///judge存在三种情况：0：上一位不是1，1：上一位是1，（判断此位是否为3）2：为13；
    ll getdp(ll nl,int mod,int judge,bool limit)
    {
        if(nl<0)
            return mod==0&&judge==2;///判断是否能整除13和为连续的13
        if(!limit&&dp[nl][mod][judge]!=-1)
            return dp[nl][mod][judge];
        ll up=limit?number[nl]:9;
        ll ans=0;
        for(int i=0; i<=up; i++)
        {
            int modnow=(mod*10+i)%13;
            int now=judge;
            if(judge==0&&i==1)///上一位不是1，现在为1
                now=1;
            if(judge==1&&i!=1)///上一位虽然为1，但此时不为1，标记为0
                now=0;
            if(judge==1&&i==3)///上一位为1，此位为3，满足条件
                now=2;
            ans+=getdp(nl-1,modnow,now,limit&&i==up);
        }
        if(!limit)
            dp[nl][mod][judge]=ans;
        return ans;
    }
    ll getnumber(ll n)
    {
        mm(number,0);
        ll nl=0;
        while(n)
        {
            number[nl++]=n%10;
            n/=10;
        }
        return getdp(nl,0,0,true);
    }
    int main()
    {
        ll n;
        while(scanf("%lld",&n)!=EOF)
        {
            mm(dp,-1);
            printf("%lld\n",getnumber(n));
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_3652]: http://acm.hdu.edu.cn/showproblem.php?pid=3652
[2010 Asia Regional Chengdu Site _ Online Contest]: http://acm.hdu.edu.cn/search.php?field=problem&key=2010+Asia+Regional+Chengdu+Site+%A1%AA%A1%AA+Online+Contest&source=1&searchmode=source
[3651]: http://acm.hdu.edu.cn/showproblem.php?pid=3651
[3655]: http://acm.hdu.edu.cn/showproblem.php?pid=3655
[3654]: http://acm.hdu.edu.cn/showproblem.php?pid=3654
[3653]: http://acm.hdu.edu.cn/showproblem.php?pid=3653
[3659]: http://acm.hdu.edu.cn/showproblem.php?pid=3659