3.2.2 Stringsobits 01串

3.2.2 Stringsobits 01串

时间： 1ms        内存：64M

描述：

考虑排好序的N(N<=31)位二进制数。

你会发现，这很有趣。因为他们是排列好的，而且包含所有长度为N且这个二进制数中1的位数的个数小于等于L(L<=N)的数。

你的任务是输出第i（1<=i<=长度为N的二进制数的个数）小的（注：题目这里表述不清，实际是，从最小的往大的数，数到第i个符合条件的，这个意思），长度为N，且1的位数的个数小于等于L的那个二进制数。

（例：100101中，N=6，含有位数为1的个数为3）。

输入：

共一行，用空格分开的三个整数N，L，i。

输出：

共一行，输出满足条件的第i小的二进制数。

示例输入：

5  3  19

示例输出：

10011

提示：

参考答案（内存最优[752]）：

#include <stdio.h>
#include <string.h>

#define NBIT 31
int main()
{
	int none, nbit;
	long long index, count[NBIT+1][NBIT+1];
	char bits[32];
	int i, j, x, y;

	while	(scanf("%d %d %lld", &nbit, &none, &index)!=EOF)
	{
		memset(count, 0, sizeof(count));
		for(i = 1; i <= NBIT; i++)
		{
			count[0][i] = 1;
		}
		for(i = 0; i <= NBIT; i++)
		{
			count[i][0] = 1;
		}

		for(j = 1; j <= nbit; j++)
		{
			for(i = 1; i <= none; i++)
			{
				count[i][j] = count[i][j-1] + count[i-1][j-1];
			}
		}

		memset(bits, 0, sizeof(bits));
		x = none;
		y = nbit;
		for(i = 0; i < nbit; i++)
		{
			if(index <= count[x][y-1]) {
				bits[i] = '0';
				y--;
			}
			else {
				bits[i] = '1';
				index = index-count[x][y-1];
				x--;
				y--;
			}
		}

		printf("%s\n", bits);
	}
	return 0;
}

参考答案（时间最优[0]）：

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAX 40
using namespace std;
long long num[MAX][MAX];
int main()
{
    long long N,L,I,i,j;
    while(cin>>N>>L>>I)
    {
        memset(num,0,sizeof(num));
        for(i=1; i<N; i++)num[i][0]=1;
        for(i=0; i<=L; i++)num[0][i]=1;
        for(i=1; i<=N; i++)
        {
            for(j=1; j<=L; j++)
            {
                if(j>i)
                    num[i][j]=num[i][i];
                else
                    num[i][j]=num[i-1][j-1]+num[i-1][j];
            }
        }
        for(i=N; i>0; i--)
        {
            if (I!=1 && num[i-1][L]<I)
            {
                cout<<1;
                I-=num[i-1][L];
                L-=1;
            }
            else
            {
                cout<<0;
            }
        }
        cout<<endl;
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。