有這樣一種集合，集合元素為長(zhǎng)度N（1～31）的二進(jìn)制串，并且每個(gè)二進(jìn)制串中1的個(gè)數(shù)小于等于L，求這個(gè)集合中第I大的元素是多少？
最開(kāi)始很天真的想枚舉每個(gè)數(shù)，計(jì)算其中1的個(gè)數(shù)，結(jié)果第8組測(cè)試數(shù)據(jù)開(kāi)始就超時(shí)的不行了。
枚舉不行，來(lái)試試構(gòu)造可不可以，假設(shè)我們有一個(gè)長(zhǎng)度為n，1個(gè)數(shù)<=l的二進(jìn)制串的集合，那么怎么把它們從大到小區(qū)分呢？我們一位一位來(lái)，根據(jù)第n位，可以將集合劃為2部分：第n位是0的，第n為是1的。好了，遞推式突然就變得很明顯了。如何設(shè)num[N][L]為長(zhǎng)度為N，1個(gè)數(shù)小于等于L的二進(jìn)制串的個(gè)數(shù)，那么：
num[N][L] = num[N-1][L] + num[N-1][L-1]
（第n位是0） （第n位是1）
個(gè)數(shù)有了，那么第I個(gè)數(shù)是多少怎么求呢？說(shuō)來(lái)也簡(jiǎn)單，就是用遞歸的思想，看I落在num[N-1][L]和num[N-1][L-1]的哪一部分，看下面的代碼應(yīng)該就明白了：
void Print (int len, int num1, long long idx)
{
if ( len == 0 )
return;
if ( num[len-1][num1] >= idx )
{
putchar('0');
Print(len-1, num1, idx);
}
else
{
putchar('1');
Print(len-1, num1-1, idx-num[len-1][num1]);
}
}