T4 题解 - 定时炸弹

Exam02

定时炸弹

题目描述

现在发现了一枚计时炸弹。 这枚计时炸弹非常神奇，它的计时数字序列从11到NN.如果当前时刻数字序列包含子序列“49”，爆炸的力量将增加一点。

现在知道数字NN， 想要知道威力的最终点。 （炸弹最开始的威力是0）

输入格式

第一行输入由整数$T$（$1 \leq T \leq 10000$）组成，表示测试用例数。 对于每个测试用例，将会有一个整数$N$（$1 \leq N \leq 2^{63}-1$）作为描述。输入以文件标记的末尾终止。

输出格式

对于每个测试用例，输出指示功率的最终点的整数。

输入样例

3
1
50
500

输出样例

0
1
15

题解

思路

数位dp，用$F[pos][num]$表示有长度为$pos$位的以$num$开头的49数的个数。
有状态转移方程：

代码

#include <iostream>
#include <memory.h>
using namespace std;
int F[100][10], d[100];
void init() {
    F[0][0] = 1;
    for(int i = 1; i <= 90; ++i){
        for(int j = 0; j <= 9; ++j){
            for(int k = 0; k <= 9; ++k){
                if (j == 4 && k == 9) continue;
                F[i][j] += F[i-1][k];
            }
        }
    }
}
unsigned long long f(unsigned long long x) {
    memset(d, 0, sizeof(d));
    int len = 0;
    unsigned long long res = 0;
    while (x > 0) {
        ++len;
        d[len] = x % 10;
        x /= 10;
    }
    for (int i = len; i >= 1; i--) {
        for (int j = 0; j <= d[i] - 1; ++j) {
            if (j == 9 && d[i+1] == 4) continue;
            res += F[i][j];
        }
        if (d[i] == 9 && d[i+1] == 4) break;
    }
    return res;
}
int main() {
    init();
    int T;
    unsigned long long n;
    cin >> T;
    while (T--) {
        cin >> n;
        cout << n - (f(n + 1) - f(1)) << endl;
    }
    return 0;
}