algorithm - 如何解决算术词典问题？(How to solve arithmetic dictionary problem?)

Question

Given positive integers from 1 to n.

(给定从1到n的正整数。)

Call sumdigit (n) is the sum of digits of n.

(呼叫和数字（n）是n的数字之和。)

Call STR(n) as the string representing the number n.

(调用STR（n）作为代表数字n的字符串。)

Arrange these numbers in order of the following: We have x standing before y if and only if (1) or (2) satisfy:

(按以下顺序排列这些数字： 当且仅当（1）或（2）满足时，我们才会在y之前出现x。)

- (1) sumdigit (x) <sumdigit (y)

- (2) sumdigit(x)=sumdigit(y) && str(x)<str(y)

For example:

(例如：)

• x = 301, y = 221 -> x comes before y (because sumdigit (x)

  (x = 301，y = 221-> x在y之前（因为总和（x）)

• x = 201, y = 30 -> x comes before y (because sumdigit (x) = sumdigit (y) and str (x)

  (x = 201，y = 30-> x在y之前（因为和数（x）=和数（y）和str（x）)

• x = 222, y = 213 -> y comes before x (because sumdigit (x) = sumdigit (y) and str (x)> str (y))

  (x = 222，y = 213-> y在x之前（因为和数（x）=和数（y）和str（x）> str（y））)

---

Given the value of n<=10^18 and Q queries

(给定n <= 10 ^ 18的值和Q个查询)

There are two types of queries for the above problem:

(对于上述问题，有两种查询类型：)

- Find the kth number in the range sorted by the above rule.

(-在按上述规则排序的范围内找到第k个数字。)

(k <= n)

(（k <= n）)

• Find the sequence number of the number k in the sequence sorted according to the above rule.

  (在按上述规则排序的序列中找到数字k的序列号。)

  (k <= n)

  (（k <= n）)

---

I can solve the problem for condition (1) by using dynamic planning dp (n, sum): the number of numbers x has sumdigit (x) = sum and x <= n

(我可以通过使用动态计划dp（n，sum）解决条件（1）的问题：x的数量具有和数（x）=和且x <= n)

-> We can count the number of x numbers with sumdigit (x)

(->我们可以用和数（x）计算x个数字)

The problem I can't solve is the condition (2),
I can't think of a way to count the number of x numbers
with sumdigit(x)=sumdigit(k) and str(x)<str(k)

Can you help me solve the problem for the condition (2)?

(您能帮我解决条件（2）的问题吗？)

I need your help!

(我需要你的帮助！)

  ask by hellow translate from so

Answer 1

等待大神答复