## HDOJ 3652 B-number

2018年01月20日 ⁄ 综合 ⁄ 共 1686字 ⁄ 字号 评论关闭

# B-number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1561    Accepted Submission(s): 854

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

Recommend
lcy

 #include #include #include  using namespace std; int dp[20][20][3],n,bit[20],len;/*    dp『位』『余数』『状态』    0--->没有13    1--->没有13但是前面一位是1    2--->有13*/int dfs(int pos,int res,int s,bool limit){    if(pos==-1)        return (s==2)&&(res==0);    if(!limit&&~dp[pos][res][s])        return dp[pos][res][s];    int end=limit?bit[pos]:9;    int ans=0;    for(int i=0;i<=end;i++)    {        int newres=(res*10+i)%13;        int news=s;        if(s==0&&i==1)            news=1;        else if(s==1&&i==3)            news=2;        else if(s==1&&i==1)            news=1;        else if(s==1&&i!=1)            news=0;        ans+=dfs(pos-1,newres,news,limit&&i==end);    }    if(!limit)        dp[pos][res][s]=ans;    return ans;} int main(){    memset(dp,-1,sizeof(dp));    while(scanf("%d",&n)!=EOF)    {        len=0;        while(n)        {            bit[len++]=n%10;            n/=10;        }        printf("%d\n",dfs(len-1,0,0,true));    }    return 0;}

* This source code was highlighted by YcdoiT. ( style: Pastie )