大家好，又见面了，我是你们的朋友全栈君。
B-number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1231 Accepted Submission(s): 651
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
题意
找包含13且被13整除的个数。
分析
能被13整除，只需要记录%13的值就好。那么如何找包含13的呢，我们需要记录当前最后一位的值，这样才可以从1 –》13。
dp[i][j][k][z]：i:处理的数位，j:该数对13取模以后的值，k:是否已经包含13,z结尾的数
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> using namespace std; int dp[12][15][2][10]; int bit[12]; int dfs(int pos,int num,bool t,int e,bool flag) { if(pos==-1)return t&&(num==0); if(!flag && dp[pos][num][t][e]!=-1) return dp[pos][num][t][e]; int end=flag?bit[pos]:9; int ans=0; for(int i=0;i<=end;i++) ans+=dfs(pos-1,(num*10+i)%13,t||(e==1&&i==3),i,flag&&(i==end)); if(!flag)dp[pos][num][t][e]=ans; return ans; } int calc(int n) { int pos=0; while(n) { bit[pos++]=n%10; n/=10; } return dfs(pos-1,0,0,0,1); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; memset(dp,-1,sizeof(dp)); while(scanf("%d",&n)==1) { printf("%d\n",calc(n)); } return 0; }
转载于:https://www.cnblogs.com/fht-litost/p/8973679.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107552.html原文链接：https://javaforall.net
