Gym 102452B Binary Tree 博弈

428人浏览 / 1人评论

题目链接

  • B - Binary Tree
    • 简单的树上博弈题,考察的是透过现象看本质、不被输入带偏的能力。
    • 首先我们知道,满k层二叉树的结点数为1+2+2²+2³+……+2^k-1^=2^k^-1
    • 注意到上面2^k-1这个数为奇数,我们还知道,任意一个数减去一个奇数都会改变其奇偶性。(奇数-奇数=偶数,偶数-奇数=奇数)
    • 最终胜利态为0(树上结点全部拿完,沦为空树),是一个偶数。
    • 如果一棵树上有奇数个结点,那么我们需要奇数次操作将其变成偶数;
    • 如果一棵树上有偶数个结点,那么我们需要偶数次操作将其变成偶数。
    • 奇数次操作,则最后一个拿到根节点的人为A;偶数次操作即为B。
    • (千万不要看到题目就去建树,这题的树是背景而不是解题模型)

代码:

#include<cstdio>
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		int x,y;
		for(int i=0;i<n-1;++i)
		{
			scanf("%d%d",&x,&y);
		}
		if(n&1)
		{
			printf("Alice\n");
		}
		else
		{
			printf("Bob\n");
		}
	}
	return 0;
}

全部评论