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
Sample Output
Author
wqb0039
Source
Recommend
lcy
加一个参数记录%13的余数。。。。newres=(res×10+i)%13
#include <iostream>
#include <cstdio>
#include <cstring>
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 )