Luogu2022 有趣的数-二分答案+数位DP

Solution

我好像写了一个非常有趣的解法233，

我们可以用数位$DP$ 算出比$N$小的数中字典序比 $X$ 小的数有多少个，再和 $rank$进行比较。

由于具有单调性，显然可以二分答案。

Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define ll long long
 5 using namespace std;
 6 
 7 ll m, rank, sum[40][40][3];
 8 int b[40], len, a[40], len2;
 9 
10 ll dfs(int pos, int pos2, bool cmp, bool lim, bool lead) {
11     if (pos == 0)
12         return (cmp || pos2 > 23) && (!lead);
13     if (!lim && !lead && sum[pos][pos2][cmp] != -1)
14         return sum[pos][pos2][cmp];
15     ll tmp = 0, up = lim ? a[pos] : 9;
16     for (int i = 0; i <= up; ++i) {
17         bool nxcmp = !(lead && i == 0) && i < b[pos2];
18         nxcmp |= cmp;
19         if (!cmp && i > b[pos2])
20             continue;
21         tmp += dfs(pos - 1, pos2 - ((lead && i == 0) ? 0 : 1), nxcmp, lim && i == a[pos], lead && i == 0);
22     }
23     if (!lim && !lead)
24         sum[pos][pos2][cmp] = tmp;
25     return tmp;
26 }
27 
28 ll check(ll n) {
29     len = 0;
30     while (n)
31         a[++len] = n % 10, n /= 10;
32     ll re = dfs(len, len2, false, true, true);
33     return re;
34 }
35 
36 int main()
37 {
38     memset(sum, -1, sizeof (sum));
39     scanf("%lld%lld", &m, &rank);
40     len2 = 23;
41     ll l = rank > m ? rank : m, r = 7e17, ans = 0;
42     while (m)
43         b[++len2] = m % 10, m /= 10;
44     for (; l <= r;) {
45         ll mid = (l + r) >> 1, tmp = check(mid);
46         if (tmp == rank - 1) {
47             ans = mid; r = mid - 1; 
48         }
49         else if (tmp < rank - 1) l = mid + 1;
50         else r = mid - 1;
51     }
52     printf("%lld
", ans);
53 }

View Code