题目链接

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 ) T (1 <= T <= 10000) 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 ) N (1 <= N <= 2^{63}-1) N(1<=N<=263−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

数位DP~
我们针对题目的要求找到三种状态：

• 不含 49 49 49 的
• 首位为 4 4 4 的
• 含 49 49 49 的

然后套数位 DP 的 DFS 模板即可，AC代码如下：

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
int a[20];
ll dp[20][3];

ll dfs(int pos, int state, bool limit) {
    if (pos == -1) return (state == 2);
    if (!limit && dp[pos][state] != -1) return dp[pos][state];
    int up = limit ? a[pos] : 9;
    ll ans = 0;
    for (int i = 0; i <= up; i++) {
        int newState = state;
        if (state == 0 && i == 4) newState = 1;
        if (state == 1 && i != 9) newState = 0;
        if (state == 1 && i == 9) newState = 2;
        if (state == 1 && i == 4) newState = 1;
        ans += dfs(pos - 1, newState, limit && i == a[pos]);
    }
    if (!limit) dp[pos][state] = ans;
    return ans;
}

ll solve(ll x) {
    int pos = 0;
    while (x) {
        a[pos++] = x % 10;
        x /= 10;
    }
    return dfs(pos - 1, 0, true);
}

int main() {
    int t;
    ll n;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &n);
        memset(dp, -1, sizeof(dp));
        printf("%lld\n", solve(n));
    }
}