题解 P2022 【有趣的数】
首先感谢一下王乃广老师的耐心讲解！
其次感谢一下@友邻牧鸡同学的指正。
考虑特殊的数字:1,10,100...
可以发现，无论n取何值(n足够大)，我们均可得出第一条结论:10^n(n>=0)总是会排在i+1号位置上。
定义一个数组mi[i]表示排在第i位上的最大数值，显然一定为10^n(n>=0)。
在草稿纸上枚举一下，我们可以得出第二条结论:对于给出的k，随着n的增加，q(n,k)的值总是不下降的。
注：q(n,k)的意义同题目给出，为k在n个数中的位置。
那么我们可以计算出k的最小位置，定义为base。
怎么求base呢？枚举一下排在k前边的数字（包括自己）！
例如：k=234。
-
一位数：1,2(2)-> 2-1+1=2;
-
两位数：10~23(14) ->23-10+1=14;
-
三位数：100~234(135) ->234-100+1=135;
有没有发现什么？
我们可以一位一位计算，只需要将当前的前n位数字，减去10^(n-1)后加1(别忽略10^(n-1))。最后再累加。
接下来拿base与m作比较，
-
如果base==m，那么我们的结果就恰好为k。
-
如果base>m，那么肯定不存在满足条件的n，直接输出0。
-
如果m>base，要在k=234之前增加m-base个元素。
注意，由于按照字典序排序，我们增加的元素，只能从这n位数的第n+1位(10^(n+1))开始枚举，还是拿234做例子。
增加元素的过程，和之前求k的最小位置是类似的。
- 四位数：1000~2339(1340)个元素。
如果仍然达不到m，我们再让m减去刚才增加的元素个数，继续枚举五位数，这样是乘10地枚举的，速度是对数级别的，可以跑得很快。
那么，如何统计答案呢？
因为从234以后的三位数即使加进去也不影响234之前的排序，所以我们可以这样做：
答案记录当前枚举的位数（记为x）的前一位所有的数字，也就是10^x-1个数字（在这里我们一开始先不删除，最后一并处理）。
如果当前的位数还不符合，就继续枚举下一位。ans乘10。
直到枚举的数字大于了m，我们再让结果加上m减去1(正如之前所说，乘上10的时候，包括了当前一位的10^x，需要删除)，就是ans啦~
代码如下(copy了一下老师的)：
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int k,m;
int base,len;
long long mi[20];
long long ans;
//计算k的最小位置
int calc(int k){
char s[12];
sprintf(s,"%d",k);
int ans=0,w=0;
len=strlen(s);
for(int i=0;i<len;i++)
{
w=w*10+s[i]-'0';
ans+=w-mi[i]+1;
}
return ans;
}
int main()
{
mi[0]=1;
for(int i=1;i<19;i++) mi[i]=mi[i-1]*10;
scanf("%d%d",&k,&m);
//1,10,100的位置是固定的
for(int i=0;i<10;i++){
if(k==mi[i]&&m!=i+1){
printf("0\n"); return 0;
}
}
base=calc(k);
if(m<base){
printf("0\n"); return 0;
}
if(m==base){
printf("%d\n",k); return 0;
}
ans=mi[len];
m-=base;
for(int i=1;;i++)
{
long long tmp=k*mi[i]-mi[len+i-1];
if(m>tmp)
{
m-=tmp;
ans*=10;
}
else break;
}
ans+=m-1;
cout<<ans<<endl;
return 0;
}