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
求包含13且是13的倍数的个数 状态很好设计 dp[i][rest][k][e] 表示i位数,最高为为e,模13为k,是否包含13 然后套上漂亮的数位dp板子 算是熟悉一下这个写法了
/*************************************************************************> File Name: hdu3652.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年02月22日 星期日 14时09分09秒 ************************************************************************/;const double pi = acos(-1);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;int dp[11][14][2][11];int bit[12];int dfs (int cur, int rest, bool t, int e, bool flag){if (cur == -1){return t && (!rest);}if (~dp[cur][rest][t][e] && !flag){return dp[cur][rest][t][e];}int end = flag ? bit[cur] : 9;int ans = 0;for (int i = 0; i <= end; ++i){ans += dfs (cur – 1, (rest * 10 + i) % 13, t || (e == 1 && i == 3), i, flag && (i == end));}if (!flag){dp[cur][rest][t][e] = ans;}return ans;}int calc (int n){int cnt = 0;while (n){bit[cnt++] = n % 10;n /= 10;}return dfs (cnt – 1, 0, 0, 0, 1);}int main (){int n;memset (dp, -1, sizeof(dp));while (~scanf(“%d”, &n)){printf(“%d\n”, calc (n));}return 0;}
，但没有一个创造奇迹的人是依靠瞬间的。
