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;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。