思路:数位dp+二分答案+小优化

​ 首先学习一下数位dp，并且先知道一下这个题:洛谷P2602

​ 知道了这个题，很容易我们可以想到可以二分答案。check的时候，只需要$min(i出现的次数,i\in[0,9])$ 和 $k$的关系即可。

​ 但是这样并不能拿满分(至少python是过不去的)。我们需要找规律，发现$0$ 总是出现的最少的那个。所以$dp$ 转移的时候只需要求$0$.快个$10$倍。

代码

python

def calcNumber (l , r):
    nu = 17
    dp = [0 for _ in range(nu)]
    arr1 = [0]
    arr2 = [0]
    mid = [0 for _ in range(nu)]
    mid[0] = 1
    for i in range(1,14):
        dp[i] = dp[i-1]*10+mid[i-1]
        mid[i] = 10 * mid[i-1]
    def solve(n,ans):
        a = [0 for _ in range(nu)]
        tt = n
        len = 0
        while(n):
            len += 1
            a[len] = int(n%10)
            n=int(n/10)
        for i in range(len,0,-1):
            ans[0] += dp[i-1]*a[i]
            if a[i] > 0:	
 	           ans[0] += mid[i-1]
            tt -= mid[i-1]*a[i]
            if a[i] == 0:
	            ans[a[i]] += tt+1
            ans[0]-= mid[i-1]
        return ans
    
    g1=solve(r,arr1)
    g2=solve(l-1,arr2)
    return g1[0]-g2[0]

t = int(input())
for x in range (t):
    k = int (input())
    l = 1
    r = 10000000000000
    while l <= r:
        mid = (l + r) >> 1
        mi = calcNumber(1 , mid)
        if mi >= k:
            r = mid - 1
        else:
            l = mid + 1
    print (l)

题目内容

小红是一个数学家，他喜欢研究各种数学问题。有一天，他在数数时想到了这个问题。给定一个正整数序列，从前往后进行数数: 1,2,3,4,5,6,7,8,9,10,11,…。

试求当小红数到多少时，0到9每个数字各出现了至少 $k$ 次。

其中，我们定义“数字”为十进制下的数位，例如，3233出现了三个’3’和一个2。

共有 $t$ 组询问，每组询问都是独立的。

输入描述

第一行输入一个正整数$t$，代表询问的次数。 接下来的$t$行，每行输入一个正整数$k$，代表一次询问。

$1 \leq t \leq 1000,1 \leq k \leq 10^{13}$

输出描述

输出$t$行，每行输出一个整数，代表每次询问的答案。

样例$1$

输入

3
1
11
20

输出

10
100
109

说明： 在第1组询问中，当数到10时，0到9每个数至少出现了1次。