?pid=3652
B-numberTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2815Accepted Submission(s): 1552
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
131002001000
Sample Output
1122
/***hdu 3652 数位dp（含13且被能被13整除的数）题目大意：求出给定区间内的数字含有“13”并且能被13整除的个数解题思路：记忆化搜索。dp[i][j][k][z]：i:处理的数位，j:该数对13取模以后的值，，k:是否已经包含13,z结尾的数*/#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;int dp[10][15][2][10],bit[10];int dfs(int pos,int mod,int t,int now,int flag){if(pos==-1)return mod==0&&t;if(!flag&&dp[pos][mod][t][now]!=-1)return dp[pos][mod][t][now];int end=flag?bit[pos]:9;int ans=0;for(int i=0;i<=end;i++){ans+=dfs(pos-1,(mod*10+i)%13,t||(now==1&&i==3),i,flag&&(i==end));}if(!flag)dp[pos][mod][t][now]=ans;return ans;}int solve(int n){int len=0;while(n){bit[len++]=n%10;n/=10;}return dfs(len-1,0,0,0,1);}int main(){int n;memset(dp,-1,sizeof(dp));while(~scanf("%d",&n)){printf("%d\n",solve(n));}return 0;}
我无所事事的度过了今天，是昨天死去的人们所期望的明天。
