欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

【NOIP2012模拟8.7】奶牛编号

程序员文章站 2022-04-21 10:14:25
思维题。题目大意:从小到大枚举自然数, 将其分为二进制的形式, 若其中有k可1,则我们称其为一个合法的数。求第n个合法的数。暴力易得。只需从小到大枚举自然数。但其中有很多不是合法的数,我们考虑只枚举合法的数将这个过程加速。我们可以先确定第n个合法的数二进制下有几位。我们考虑每一个k个1的p位数有几个。简称kp数易得0的位置有p - k个0可以出现的位置有p - 1个所以有(p - 1)选 (p - k)个kp数所以我们递增p,累加之前得到的k(k......

思维题。

题目大意:从小到大枚举自然数, 将其分为二进制的形式, 若其中有k可1,则我们称其为一个合法的数。求第n个合法的数。

 

暴力易得。只需从小到大枚举自然数。

 

但其中有很多不是合法的数,我们考虑只枚举合法的数将这个过程加速。

 

我们可以先确定第n个合法的数二进制下有几位。

 

我们考虑每一个k个1的p位数有几个。简称kp数

易得0的位置有p - k个

0可以出现的位置有p - 1个

所以有(p  - 1)选 (p - k)个kp数

所以我们递增p,累加之前得到的k(k ~ p)数的个数,知道找到n所在的位置。

 

知道了位数, 就知道了0有几个, 不难发现0不会很多,所以我们依次确定每个0的位置。

 

观察 k = 3时得到的kn数

 

111 - 1011 - 1101 - 10011 - 10101 - 10110 - 11001 - 11010 - 11100 - 100011

 

发现从小到大,我们总是把0在前面的数放在前面。

 

第x个0 如果放到第u位, 对应的合法数有 (p - u) 选 (p - k - x)个

 

类似上面的方法叠加,即可确定最终的数。

 

 

 

 

 

本文地址:https://blog.csdn.net/Com_man_der/article/details/107879818

相关标签: 数位 构造