P2022 有趣的数

Thunder_S · 2021-07-19 11:28:15 · 题解

Solution

首先从特殊往一般想。

考虑当 K=10^i 的时候的情况。由于其字典序最小，因此位置是固定的，即 i+1 ，那么只要 M 不是这个位置都是无解。

既然是位置，可以考虑先求出 K 的最小位置。

思考在 K 前面的会有多少。假设 K=114514 。

因此可以发现，在比 K 少 i 位的情况下，将会有（设 K 的长度是 len） \lfloor\dfrac{K}{10^i}\rfloor-10^{len-i}+1 个数的字典序比 K 小。

统计出 K 的最小位置 num 后，将 num 和 M 进行比较。

若 num=M，那么只要出现了 K 就可以使得 K 的位置是 M，因此 N 的最小值就是 K 。

若 num>M ，就无解了，因为 num 是 K 的最小位置。不存在其他的位置比 num 还要小。

若 num<M ，就说明还有比 K 前面的数，但是位数小于等于 K 的已经穷举完了，因此肯定有位数大于 K 的在 K 前面。逐步增加位数，同时更新最小位数。当某个时刻 num\ge M ，先将 num 减回去，算出 M 与 num 之间的差。再加上 10^{x} ，这个 x 是当前位数。最后减去 1（因为从 0 开始算），就是 N 的大小。

Code

#include<cmath>
#include<cstdio>
using namespace std;
int len;
long long k,m,num,p[20];
int main()
{
    scanf("%lld%lld",&k,&m);
    p[0]=1;
    for (int i=1;i<=18;++i)
        p[i]=p[i-1]*10;
    for (int i=0;i<=18;++i)
        if (k==p[i])
        {
            if (m==i+1) printf("%lld\n",k);
            else printf("0\n");
            return 0;
        }
    len=(int)log10(k);
    for (int i=len;i>=0;--i)
        num+=k/p[i]-p[len-i]+1;
    if (num==m) printf("%lld\n",k);
    else if (num>m) printf("0\n");
    else
    {
        for (int i=1;i<=10;++i)
        {
            k*=10;
            num+=k-p[len+i];
            if (num>=m)
            {
                num-=k-p[len+i];
                printf("%lld\n",m-num+p[len+i]-1);
                return 0;
            }
        }
    }
    return 0;
}