【SSL 1473】奶牛编号

技术文章 2年前 (2020) 完美者
1,989 0

标签:题目   scan   长度   个数   amp   pre   代码   break   bre   

题目大意:

求字典序第 \(N\) 大的只含 \(k\) 个 1 的 01 串。

正文:

考虑到用组合数,由于首位一定是 1,那么我们需要选择位置的 1 就只有 \(k-1\) 个,枚举 01 串长度 \(len\),长度为 \(len\) 的 01 串个数是 \(C_{len}^{k-1}\),每次枚举的时候用 \(N\) 减去。最后得到终点长度 \(len\),只需要求第 \(N\) 大了,暴力求即可。

代码:


void work(int len, int n)
{
	for (int i = len - k + 1; i <= len; i++) a[i] = 1;
	n--;
	while (n--)
	{
		int tot = 0, i;
		for (i = len; i >= 1; i--)
			if (a[i])
				break;
		for (; i >= 1; i--)
		{
			if (!a[i])
				break;
			tot++;
		}
		for (int j = len; j >= i; j--) a[j]=0;
		for (int j = len; j >= len - tot + 2; j--)
			a[j] = 1;
		a[i] = 1;
	}
	for (int i = 1; i <= len; i++) printf("%d", a[i]);
}

int main()
{
	scanf ("%d%d", &n, &k);
	C[0][0] = 1ll;
	for (int i = 1; i <= N - 10; i++)
	{
		C[i][0] = 1ll;
		for (int j = 1; j <= N - 10; j++)
			C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
	}
	printf("1");
	if(k == 1)
	{
		for (int i = 1; i < n; i++)
			printf("0");
		puts("");
		return 0;
	}
	int len;
	for (len = k - 1; C[len][k - 1] < n; n -= C[len][k - 1], len++)
	{
		if(len == 2333){
			len = 2000;
		}
	}
	k--;
	work(len, n);
	return 0;
}

【SSL 1473】奶牛编号

标签:题目   scan   长度   个数   amp   pre   代码   break   bre   

原文地址:https://www.cnblogs.com/GJY-JURUO/p/13495421.html

版权声明:完美者 发表于 2020-08-13 22:09:50。
转载请注明:【SSL 1473】奶牛编号 | 完美导航

暂无评论

暂无评论...