我要评论思维题。
题目大意：从小到大枚举自然数， 将其分为二进制的形式， 若其中有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
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论