比赛 |
EYOI与SBOI开学欢乐赛11th |
评测结果 |
WWWWWWWWWW |
题目名称 |
WHZ 的数字 |
最终得分 |
0 |
用户昵称 |
yrtiop |
运行时间 |
0.465 s |
代码语言 |
C++ |
内存使用 |
4.59 MiB |
提交时间 |
2022-10-14 21:44:03 |
显示代码纯文本
#include <bits/stdc++.h>
typedef unsigned long long ull;
const int maxn = 25;
ull n,k,f[maxn][maxn],sum[maxn][maxn],cur;
int d,lim[maxn];
ull dfs(int x) {
if(!x)return 1;
ull ans = 0;
for(int i = 1;i < lim[x];++ i)
ans += f[x][i];
cur /= 10;
if(x < d)ans += cur;
return ans + dfs(x - 1);
}
ull ask(ull x) {
if(x == 0)return 1;
d = 0;
cur = x;
memset(f , 0 , sizeof(f));
for(ull m = x;m;m /= 10)lim[++ d] = m % 10;
for(int i = 2;i <= d;++ i) {
for(int j = i - 1;~ j;-- j) {
for(int k = 1;k < 10;++ k) {
f[i][k] += sum[j][9] + i - j - 1;
}
}
for(int k = 1;k < 10;++ k)
sum[i][k] = sum[i][k - 1] + f[i][k];
}
ull ans = 0;
for(int i = 1;i < d;++ i)ans += sum[i][9];
return ans + dfs(d) + (d > 1);
}
void work() {
ull l = 0,r = n;
while(l <= r) {
ull mid = l + r >> 1;
ull val;
if(mid)val = ask(n) - ask(mid - 1);
else val = ask(n);
if(val >= k)l = mid + 1;
else r = mid - 1;
}
printf("%llu\n",r);
return ;
}
int main() {
freopen("whz_number.in","r",stdin);
freopen("whz_number.out","w",stdout);
while(~ scanf("%llu %llu",&n,&k)) {
work();
}
return 0;
}