题目描述

难度分:$1500$

输入$T(\leq 10^4)$表示$T$组数据。

每组数据输入$k(1 \leq k \leq 10^{12})$。

输出第$k$个不含$4$的正整数，例如$k=4$时答案为$5$。

输入样例

7
3
5
22
10
100
12345
827264634912

输出样例

3
6
25
11
121
18937
2932285320890

算法

二分答案+数位DP

题目很明显是有单调性的，一个数$x$越大，显然区间$[1,x]$内不含$4$的数字就越多，因此可以利用单调性来确定最后一个满足$[1,x]$内不含$4$的数字$x$是多少。

而对于一个给定的上界$x$，就可以用数位DP来计算$[1,x]$中不含$4$的数字个数。使用灵茶山艾府的记忆化搜索模板来做即可。$dp[i][islimit][isnum]$表示$[0,i-1]$数位已经填数完毕，贴合上界情况为$islimit$，之前是否真的填过数$isnum$，从数位$i$开始填到最后能得到多少个不含$4$的数。

复杂度分析

时间复杂度

根据状态定义，粗略估计状态一共有$18 \times 2 \times 2$个，状态转移时最多遍历$0$~$9$除$4$以外一共$9$个数，在长整型内进行二分大概需要$60$次左右，因此常数操作大约是$18 \times 2^2 \times 9 \times 60 \times 10^4$（事实上有很多较小的$k$，复杂度会比这个低很多）。

空间复杂度

开辟的$dp$数组就是额外空间消耗，是$20 \times 2^2$的量级。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

LL dp[20][2][2];

LL dfs(string& s, int i, int islimit, int isnum) {
    if(i == s.size()) {
        return isnum;
    }
    LL &v = dp[i][islimit][isnum];
    if(v != -1) return v;
    LL cnt = isnum? 0: dfs(s, i + 1, 0, 0);
    int digit = s[i] - '0';
    int ub = islimit? digit: 9;
    for(int d = 1 - isnum; d <= ub; d++) {
        if(d == 4) continue;
        cnt += dfs(s, i + 1, islimit && d == digit, 1);
    }
    return v = cnt;
}

LL check(LL n) {
    string s = to_string(n);
    memset(dp, -1, sizeof(dp));
    // 计算[1,n]中不含4的数字个数
    return dfs(s, 0, 1, 0);
}

LL solve(LL k) {
    LL left = 1, right = 1e15;
    while(left < right) {
        LL mid = left + right >> 1;
        if(check(mid) >= k) {
            right = mid;
        }else {
            left = mid + 1;
        }
    }
    return right;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        LL k;
        scanf("%lld", &k);
        printf("%lld\n", solve(k));
    }
    return 0;
}