HDU 3555 Bomb 【数位dp】

Bomb

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 15876 Accepted Submission(s): 5794

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

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

求从1~n中含有49的数字的个数。

#include <map>
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#include <stack>
#include <cmath>
#include <string>
#include <vector>
#include <cstdlib>
//#include <bits/stdc++.h>
//#define LOACL
#define space " "
using namespace std;
//typedef long long LL;
typedef __int64 Int;
typedef pair<int, int> paii;
const int INF = 0x3f3f3f3f;
const double ESP = 1e-5;
const double PI = acos(-1.0);
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 10;
Int dp[20][3];
void init() {
    dp[0][2] = 1;
    for (int i = 1; i < 20; i++) {
        dp[i][0] = dp[i - 1][0]*10 + dp[i - 1][1]; //含有49的
        dp[i][1] = dp[i - 1][2]; //不含有49， 最高位是9
        dp[i][2] = dp[i - 1][2]*10 - dp[i - 1][1]; //不含49（高位可为9）
    }
}
void solved(Int x) {
    int bit[20];
    int p = 0; Int ans = 0;
    while (x) {bit[++p] = x%10; x /= 10;}
    bit[p + 1] = 0;
    bool flag = false;
    for (int i = p; i >= 1; i--) {
        ans += bit[i]*dp[i - 1][0];
        if (flag) {ans += dp[i - 1][2]*bit[i]; continue;} //高位已经出现过49，下次跳过，以免重复。
        if (bit[i] > 4) ans += dp[i - 1][1]; //最高位可以出现49
        if (bit[i + 1] == 4 && bit[i] == 9) flag = true;
    }
    if (flag) ans++;
    printf("%I64d
", ans);
}
int main() {
    Int T, n;
    init();
    scanf("%I64d", &T);
    while (T--) {
        scanf("%I64d", &n);
        solved(n);
    }
    return 0;
}