首页 > 代码库 > HDU 3652 B-number
HDU 3652 B-number
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 22
题意:给你一个数n,要你求出从1到n中有多少个数满足能被13整除且含有子串“13”
思路:这个题目如果多数位DP理解深刻那么就很容易了,我们发现除了位数我们需要考虑,那么不同的状态有影响的是该数能否被13整除,是否含有子串13,该数的尾数
所以AC代码:
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int f[20][20][3][10],bits[20]; int dfs(int pos,int flag,int val,int e,bool bianjie) { int ans=0; if(pos==-1) { if(flag!=1) return 0; else { if(val==0) { return 1; } else return 0; } } if(!bianjie&&f[pos][val][flag][e]!=-1) return f[pos][val][flag][e]; int u=bianjie?bits[pos]:9; for(int i=0;i<=u;i++) { ans+=dfs(pos-1,(e==1&&i==3)||flag,(val*10+i)%13,i,bianjie&&i==u); } return bianjie?ans:f[pos][val][flag][e]=ans; } int n; int solve() { int len_m=0; while(n) { bits[len_m++]=n%10; n/=10; } return dfs(len_m-1,0,0,0,true); } int main() { memset(f,-1,sizeof(f)); while(~scanf("%d",&n)) { cout<<solve()<<endl; } return 0; }
HDU 3652 B-number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。