Problem Description The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence “49”, the power of the blast would add one point. Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?
Input The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.
The input terminates by end of file marker.
Output For each test case, output an integer indicating the final points of the power.
Sample Input
3 1 50 500
Sample Output
0 1 15 Hint From 1 to 500, the numbers that include the sub-sequence “49” are “49”,”149”,”249”,”349”,”449”,”490”,”491”,”492”,”493”,”494”,”495”,”496”,”497”,”498”,”499”, so the answer is 15.
Author fatboy_cw@WHU
Source 2010 ACM-ICPC Multi-University Training Contest（12）——Host by WHU
Recommend zhouzeyong | We have carefully selected several similar problems for you: 3554 3556 3557 3558 3559
这题没用那个经典的板子
设dp[i][0]表示位数小于等于i的所有数中, 不包含49的数的个数 dp[i][1]表示位数小于等于i的所有数中,第i位为9,且不包含49的数的个数 dp[i][2]表示位数小于等于i的所有数中,包含49的数的个数
/*************************************************************************> File Name: hdu3555.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年02月22日 星期日 22时13分31秒 ************************************************************************/;const double pi = acos(-1);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;LL dp[70][3];int bit[70];void calc (LL n){int cnt = 0;while (n){bit[++cnt] = n % 10;n /= 10;}LL ans = 0;bool flag = false;bit[cnt + 1] = 0;for (int i = cnt; i >= 1; –i) //枚举比n开始小的那一位{ans += dp[i – 1][2] * bit[i]; //先统计i-1位以下的符合条件的数的个数if (flag) //既然前缀中出现了49,后面的随意填{ans += dp[i – 1][0] * bit[i];}if (!flag && bit[i] > 4) //前缀里没有49,但是此时可以产生49{ans += dp[i – 1][1];}if (bit[i + 1] == 4 && bit[i] == 9){flag = 1;}}if (flag) //本身{++ans;}printf(“%lld\n”, ans);}int main (){dp[0][0] = 1;for (int i = 1; i <= 64; ++i){dp[i][0] = dp[i – 1][0] * 10 – dp[i – 1][1]; //不包含的情况下要减去第i位恰好为4的情况dp[i][1] = dp[i – 1][0];dp[i][2] = dp[i – 1][2] * 10 + dp[i – 1][1];}int t;scanf(“%d”, &t);while (t–){LL n;scanf(“%lld”, &n);calc (n);}return 0;}
，创造条件,去改变生活,做生活的强者.愿你早日成为生活的强者
