【NOIP2012模拟8.7】JZOJ2020年8月8日提高组T1 奶牛编号

题目

作为一个神秘的电脑高手，Farmer John 用二进制数字标识他的奶牛。

然而，他有点迷信，标识奶牛用的二进制数字，必须只含有K位“1” (1 <= K <= 10)。 当然，每个标识数字的首位必须为“1”。

FJ按递增的顺序，安排标识数字，开始是最小可行的标识数字（由“1”组成的一个K位数）。

不幸的是，他没有记录下标识数字。请帮他计算，第N个标识数字 (1 <= N <= 10^7)。

题解

题意

求第\(n\)小的合法的数

合法：该数在二进制下有且仅有\(k\)个位置为1，最高位一定为1

分析

尝试去构造这个第\(n\)小的数

可以想到利用组合数

首先先确定长度

然后再判断方案数与组合数的大小，选择填0还是1

Code

#include<cstdio>

#define mx 10000000

using namespace std;

int n,k,i,j,s,cc,l,x,c[3005][3005];

int C(int x,int y)

{

	if (x==y||y==0) return 1;

	if (y==x-1||y==1) return x;

	return c[x][y];

}

int main()

{

    scanf("%d%d",&n,&k);

    if (k==1)

    {

    	printf("1");

    	for (i=1;i<n;i++)

    		printf("0");

    	return 0;

	}

	c[0][0]=1;

	for (i=1;i<3000;i++)

	{

		c[i][0]=c[i][i]=1;

		for (j=1;j<i;j++)

		{

			c[i][j]=c[i-1][j]+c[i-1][j-1];

			if (c[i][j]>mx) c[i][j]=mx;

		}

	}

	s=0;

	i=k-1;

	j=0;

	while (s<n)

	{

		s+=C(i,j);

		i++;

		j++;

	}

    n-=s-C(i-1,j-1);

    printf("1");

    l=i-1;

    x=j-1;

    while (l)

    {

    	if (x&&n<=C(l-1,x-1))

    	{

    		printf("0");

    		x--;

		}

		else

		{

			printf("1");

			if (x) n-=C(l-1,x-1);

		}

		l--;

	}

    return 0;

}

【NOIP2012模拟8.7】JZOJ2020年8月8日提高组T1 奶牛编号的相关教程结束。