题解 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了一下老师的)： ```cpp #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; } ```