题目链接

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