[Luogu2022] 有趣的数

摘要

题意:Q(N,K) 表示把 1-N 按字典序从小到大排列后 K 的排名。给出 K,M,最小化 N,且 Q(N,K)=M. 无解输出 0。

一道思路很清奇的题。首先可以想到这些结论:

  1. 关于 i 单调递增(非严格)
  2. 排名一定为 i+1

有了上面的结论,意味着 K 是有最小排名的。即 1-K 必然是要考虑的。考虑字典序比 K 小的数,当 K=345 时,枚举一下:

  1. 1-3
  2. 10-34
  3. 100-345

即当 时,K 的最小排名为

计算上式的复杂度是

然后通过比较 m 和最小排名的大小可以判断是否无解。那么如果 m 比最小排名还大,说明 N>K。则我们可以继续枚举,方法与上面的类似:

  1. 1000-3449
  2. 10000-34449

如果枚举的个数累加起来大于等于 m,说明找到解了,于是输出即可(解的位置可以 O(1) 计算)

总复杂度 (和答案的对数有关)

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
int k,m;
int a[20],la;
signed main(){
    scanf("%lld%lld",&k,&m);
    int x=0,k2=k,m10=1;
    while(k2)a[++la]=k2%10, k2/=10;
    reverse(a+1,a+la+1);
    for(int i=1;i<=la;i++){k2=k2*10+a[i];
        x+=k2-m10+1;
        m10*=10;
    }
    if(la==x&&m!=x)return puts("0"),0;
    if(x>m)return puts("0"), 0;
    if(x==m)return printf("%lld",k), 0;
    while(x<m){
        k2*=10;
        int d=k2-m10;// 不含 k2 本身
        if(x+d<m)x+=d;
        else return printf("%lld",m10+m-x-1), 0;
        m10*=10;
    }
    return 0;
}

  转载请注明: Sshwy's Blog [Luogu2022] 有趣的数

 上一篇
[BZOJ2219] 数论之神 [BZOJ2219] 数论之神
摘要 啃课件的时侯遇到的,先放个题解,至于代码的话先咕着 多组数据( 1. . X 在范围 [0, 2K] 内 的 X 的个数. 即求同余方程 $x^a\equiv b\b
2019.06.08
下一篇 
[国家集训队]Middle [国家集训队]Middle
摘要 题意:对于一个数列每次询问 ,求左端点在 右端点在 的区间的中位数的最大值。偶数的情况下标向下取整。 . 对于求这种答案在某一维度上单调的最值问题,
2019.05.21
  目录