首页 > 代码库 > HDU 3652 B-number
HDU 3652 B-number
B-number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2464 Accepted Submission(s): 1346
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
Recommend
lcy | We have carefully selected several similar problems for you: 3651 3655 3654 3653 3659
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<stack> #include<queue> #include<set> #include<map> #include<vector> using namespace std; typedef long long LL; /* int dfs(int i, int s, bool e) { if (i==-1) return s==target_s; if (!e && ~f[i][s]) return f[i][s]; int res = 0; int u = e?num[i]:9; for (int d = first?1:0; d <= u; ++d) res += dfs(i-1, new_s(s, d), e&&d==u); return e?res:f[i][s]=res; } ~~f为记忆化数组; ~~i为当前处理串的第i位(权重表示法,也即后面剩下i+1位待填数); ~~s为之前数字的状态(如果要求后面的数满足什么状态,也可以再记一个目标状态t之类,for的时候枚举下t); ~~e表示之前的数是否是上界的前缀(即后面的数能否任意填)。 ~~for循环枚举数字时,要注意是否能枚举0,以及0对于状态的影响,有的题目前导0和中间的0是等价的, 但有的不是,对于后者可以在dfs时再加一个状态变量z,表示前面是否全部是前导0,也可以看是否是首位, 然后外面统计时候枚举一下位数。It depends. */ //dp[i][j][k],i表示位数,j表示余数,k=0表示“不含13”,k=1表示“不含13且末位为1”,k=2表示“含有13” LL n,dp[40][13][3]; int num[50]; //分别表示当前考虑的位置,前一个数字,当前余数,是否有限制,是否已经出现13 LL dfs(int pos,int pre,int mod,bool limit,bool flag) { if(pos==0) return flag&&(mod==0); if(!limit && flag && dp[pos][mod][0]!=-1) return dp[pos][mod][0]; if(!limit && !flag && pre!=1 && dp[pos][mod][2]!=-1) return dp[pos][mod][2]; if(!limit && !flag && pre==1 && dp[pos][mod][1]!=-1) return dp[pos][mod][1]; int end = limit?num[pos]:9; LL ans = 0; for(int i=0;i<=end;i++) { ans+=dfs(pos-1,i,(mod*10+i)%13,limit&&(i==end),flag||(pre==1&&i==3)); } if(!limit) { if(flag) dp[pos][mod][0] = ans; if(!flag && pre!=1) dp[pos][mod][2] = ans; if(!flag && pre==1) dp[pos][mod][1] = ans; } return ans; } LL work() { int len = 0; while(n) { num[++len] = n%10; n/=10; } return dfs(len,0,0,true,false); } int main() { memset(dp,-1,sizeof(dp)); while(scanf("%I64d",&n)!=EOF) { printf("%I64d\n",work()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。