字典序

解题思路

这道题可以使用字典树的方法来解，这里用所构建的字典树来举一个例子：

思路就是每一次统计当前节点的子节点的个数，如果是大于等于的，则答案就在当前节点的子树中，如果是小于的，那说明当前答案一定不在这个子树中，就继续去看下一个子树。

如何统计一棵子树中的节点个数呢，直接说的话会有些抽象，这里用一个数字来举例，例如当数字为时，的限制为，则该子树中的节点个数是这样统计的，首先的子节点有,然后继续向下扩展的话是没有的，所以节点对应的子节点个数为,以此类推节点和节点一直到节点的子节点个数都为,我们可以发现，对于一棵节点的子节点为该类节点的个数乘以

参考代码

def getCntOfSon(pre, n):
    cnt = 1
    p = 10

    while True:
        if pre * p > n:
            break
        if pre * p + p - 1 < n:
            cnt += p  # 判断当前节点是否可以扩展一层，一层的节点个数为p
        else:
            """
            如果不可以扩展一层，则说明 pre * p <= n <= pre * p + p - 1,
            则只需要加上[pre * p, n]之间的数字个数就好了，也就是n - pre * p + 1
            """
            cnt += n - pre * p + 1  
        p *= 10

    return cnt


def solve(n, m):
    ans = 1

    while True:
        cnt = getCntOfSon(ans, n)
        if cnt >= m: # 如果m <= 当前子树节点个数，则这个数字就在这个子树中
            m -= 1
            if m == 0:
                break
            ans *= 10
        else: # 否则的话换一棵子树
            m -= cnt
            ans += 1
    return ans

l = input().split(" ")
n = int(l[0])
m = int(l[1])

print(solve(n, m))