当前位置：Gxlcms >
数据库问题 >
【数位DP】bnuoj 52813 J. Deciphering Oracles
【数位DP】bnuoj 52813 J. Deciphering Oracles
时间：2021-07-01 10:21:17
帮助过：7人阅读
#include<bits/stdc++.h>
2 using namespace std;
3 typedef
long long ll;
4 ll N,K;
5 ll dp[
20][
200];
6 ll cnt[
200];
7 int sumdigit(ll x)
8 {
9 int tot=
0;
10 while(x)
11 {
12 tot+=x%
10;
13 x/=
10;
14 }
15 return tot;
16 }
17 int digit[
20];
18 int split(ll x)
19 {
20 int ret=
0;
21 while(x)
22 {
23 digit[++ret]=x%
10;
24 x/=
10;
25 }
26 reverse(digit+
1,digit+
1+
ret);
27 return ret;
28 }
29
30 void Dp(
int len)
31 {
32 memset(dp,
0,
sizeof(dp));
33 //从高位到低位递推
34 for(
int i=
1;i<digit[
1];i++)
//最高位
35 {
36 dp[
1][i]=
1;
37 }
38 int sum=digit[
1];
39 for(
int i=
2;i<=len;i++
)
40 {
41 for(
int j=
0;j<
200;j++
)
42 {
43 if(dp[i-
1][j])
//不为0才有贡献
44 for(
int tran=
0;tran<
10;tran++)
//从高到底第i位
45 {
46 if(j+tran<
200)
47 {
48 dp[i][j+tran]+=dp[i-
1][j];
49 }
50 }
51 }
52 for(
int j=
1;j<=
9;j++) dp[i][j]++;
//因为初始化dp[1][i]时dp[1][0]为0，所以要补上000..j这种情况
53 for(
int j=
0;j<digit[i];j++) dp[i][sum+j]++;
//因为初始化dp[1][digit[1]]为0，所以要补上只有第i位不同的情况
54 sum+=
digit[i];
55 }
56 dp[len][sum]++;
//算的是小于等于x的数，要加上本身
57 }
58
59 ll cal(ll X,
int sum,
int type)
60 {
61 int len=
split(X);
62 Dp(len);
63 if(type==
1)
//[1,X]中位数和小于sum的总数
64 {
65 ll ans=
0;
66 for(
int i=
1;i<sum;i++
)
67 {
68 ans+=
dp[len][i];
69 }
70 return ans;
71 }
72 else //[1,x]中位数和恰好为sum的总数
73 {
74 return dp[len][sum];
75 }
76 }
77
78 ll solve(ll X,ll k)
79 {
80 int len=
split(X);
81 Dp(len);
82 for(
int i=
0;i<
200;i++
)
83 {
84 cnt[i]=
dp[len][i];
85 }
86 for(
int i=
1;i<
200;i++
)
87 {
88 cnt[i]+=cnt[i-
1];
89 }
90 ll pos=lower_bound(cnt+
1,cnt+
200,k)-
cnt;
91 k-=cnt[pos-
1];
92 ll l=
1,r=
1e18;
93 while(l<=
r)
94 {
95 ll mid=(l+r)>>
1;
96 if(cal(mid,pos,
0)<
k)
97 {
98 l=mid+
1;
99 }
100 else
101 {
102 r=mid-
1;
103 }
104 }
105 return l;
106 }
107 int main()
108 {
109 while(~scanf(
"%I64d%I64d",&N,&
K))
110 {
111 cout<<cal(N,sumdigit(K),
1)+cal(K,sumdigit(K),
0)<<
" ";
112 cout<<solve(N,K)<<
endl;
113 }
114 return 0;
115 }
数位DP
【数位DP】bnuoj 52813 J. Deciphering Oracles
标签：bit sed ring scan code 不同 pos style names
