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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注