题解 [ABC321C] 321-like Searcher

· · 题解

题意

给定一个 k，你需要找到第 k 小的满足下面条件的正整数：

分析

这个数据范围仅有一个 1 \le k，让人很不好下手。

我们不妨先做一个 DP，看有多少个满足这样条件的数。

设 f_{i,j} 表示有 i 位，且最高位为 j 时这类数的个数。

可以很容易的写出下面这份代码：

typedef long long LL;
const int n=10;
int k;
LL f[11][10];
void test(){
    for(int i=0;i<n;i++)f[1][i]=1;
    for(int i=2;i<=n;i++){
        for(int j=i-1;j<=n;j++) f[i][j]=f[i][j-1]+f[i-1][j-1];
    }
    LL s=0;
    for(int i=1;i<=n;i++){
        for(int j=i-1;j<n;j++) printf("%lld\t",f[i][j]),s+=f[i][j];
        putchar('\n');
    }
    printf("%lld\n",s-f[0][0]);//注意是正整数，0 不符合要求。
}

可以发现这类数总共只有 1023 个，所以直接朴素枚举下一个就可以解决了。

注意事项

最大满足要求的数为 9876543210 > 2^{31}-1，所以需要 long long 存储答案。

代码

//the code is from chenjh
#include<cstdio>
#include<cmath>
#include<algorithm>
typedef long long LL;
const int n=10;
int k;
LL nx(LL x){
    int w=(int)log10(x)+1;//获取位数。
    if(w==1) return x+1;//一位数直接跳过。
    int a[20],c=0;
    for(LL t=x;t;a[++c]=t%10,t/=10);//分解成各数位。
    ++a[1];//将最低为增加。
    for(int i=1;i<c;i++)if(a[i]>=a[i+1]) a[i]=i-1,++a[i+1];//如果不满足要求，将当前位设成当前位的理论最小值。
    if(a[c]>9){//需要进位则进位。
        ++c;
        for(int i=1;i<=c;i++) a[i]=i-1;
    }
    LL r=0,s=1;
    for(int i=1;i<=c;i++) r+=s*a[i],s*=10;//还原新的数。
    return r;
}
int main(){
    scanf("%d",&k);
    LL ans=1;
    for(int i=1;i<k;i++) ans=nx(ans);//枚举下一个。
    printf("%lld\n",ans);
    return 0;
}