Gym 102452G Game Design 搜索+计数原理

545人浏览 / 1人评论

题目链接

  • G - Game Design
    • 这一题是构造题,我们必须想出一种策略可以使树上的结点数满足要求。
    • 为了简化构造难度,我们可以试图把每一个点都作为某个答案中的一个点,并且只考虑二叉树。显然,每个叶子结点都设防是满足条件的情况,我们把每个叶子结点的代价都设为1.
    • 考虑一个结点和它的两个子结点的关系,如果它的两个子结点都被防住(不一定是在子结点处设防,也可能在子结点的子结点设防),那么这个父结点就无须设防了。设两个子结点能防住的最小代价分别为a和b,那么父结点如果也要成为最优的一种情况,其代价就必须为a+b。
    • 下面考虑方案数分配,如果一个结点的两个子结点分别有防住最优方案数m种和n种,那么这个结点防住的方案数就是mn+1种(根据乘法原理可得两个子结点为根的子树中设防的方案有mn种,当前结点设防有1种)。
    • 所以,我们容易想到思路——从上向下分配方案数,自下而上回溯时算出代价(我们设每个叶子结点代价均为1)。
    • 如何分配树的形态?
    • 原来我们有K种方案;
    • 当我们即将要分配一个结点,还剩k种方案时,我们先给这个结点分配1种方案,子结点要分配k-1种方案。若k-1为奇数,我们只给这个结点分配一个子结点,这个子结点分配1种方案,这样剩下k-2种方案(为偶数);若k-1为偶数,我们给这个结点分配两个子结点,其中一个分配2种方案,另外一个分配(k-1)/2种方案。直到方案数为1,停止递归即可。

代码:

#include<cstdio>
using namespace std;
int far[(int)1e5+10],value[(int)1e5+10],tot;
void dfs(int ind,int k)
{
	if(k==1)
	{
		value[ind]=1;
		return;
	}
	if(k&1)
	{
		int son1=++tot,son2=++tot;
		dfs(son1,2);
		dfs(son2,(k-1)/2);
		far[son1]=far[son2]=ind;
		value[ind]=value[son1]+value[son2];
	}
	else
	{
		int son=++tot;
		dfs(son,k-1);
		far[son]=ind;
		value[ind]=value[son];
	}
}
int main()
{
	int k;
	scanf("%d",&k);
	if(k==1)
	{
		printf("2\n1\n1 2");
		return 0;
	}
	tot=1;
	dfs(1,k);
	printf("%d\n",tot);
	for(int i=2;i<=tot;++i)
	{
		printf("%d ",far[i]);
	}
	putchar('\n');
	for(int i=1;i<=tot;++i)
	{
		printf("%d ",value[i]);
	}
	return 0;
}

全部评论