链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1011&cid=872
Problem Description
联合国太平洋方面第11军横滨基地的娱乐活动很少。207小队的成员通常会在晚饭后聚在PX玩游戏。然而无论玩什么游戏，白银武总是会输。于是白银武决定利用另一个世界中的博弈论知识来让自己转败为胜。
白银武向战友们介绍了这样一个游戏：
给出一棵n 个点以1 为根的有根树。两个人轮流进行操作。操作人需要选出至少1 个叶子(即没有儿子的点)删掉。无法操作的人输。
不幸的是，白银武发现自己的博弈论知识并不能判断自己应该选择先手还是后手。所以请你帮他判断，在双方都进行最优决策的情况下，是先手必胜还是后手必胜。
Input
第1 行一个整数T ，代表数据组数。
对于每组数据，
第1 行一个正整数n ，代表树上结点个数。
接下来一行n−1 个数字，依次表示2∼n 点的父亲编号。
2≤n≤106
每个测试文件中的n 之和不超过106 。
Output
若在双方都选择最优决策的情况下，先手必胜，请输出"Takeru"；否则输出"Meiya"。
Sample Input
2 3 1 1 4 1 2 3
Sample Output
Takeru Meiya
Hint
对于第一组数据，先手选择删去2号点，那么后手只能删去3号点，之后先手删去1号点取得胜利
题解：博弈题，可以看出分两种情况
1.当除了根节点外（别问为什么除了根节点，试出来的），如果存在某一个节点有多个叶子节点，则先手必胜
2.如果不存在以上情况，则需求出所有链条的长度，如果全是偶数则先手必胜，否则后手必胜
代码：
#include <bits/stdc++.h>
using namespace std;
long long father[1000001];
long long fl[1000001];
long long ru[1000001];
long long s[1000001];
long long ans;
long long n,m,t;
void f(int x,int i)
{
if(father[x]==x||fl[x]==1)
return;
else
{
s[i]++;
fl[x]=1;
f(father[x],i);
}
}
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
memset(father,0,sizeof(father));
memset(fl,0,sizeof(fl));
memset(ru,0,sizeof(ru));
memset(s,0,sizeof(s));
father[1]=1;
for(int i=2;i<=n;i++)
{
scanf("%lld",&father[i]);
ru[father[i]]++;
}
int j=0;
int fg=0;
for(int i=2;i<=n;i++)
{
if(ru[i]>1)
{
fg=1;
break;
}
}
if(fg==1)
printf("Takeru\n");
else
{
for(int i=2;i<=n;i++)
{
if(ru[i]==0)
{
j++;
f(i,j);
}
}
int flag=1;
//for(int i=1;i<=j;i++)
//{
// cout<<s[i]<<endl;
//}
if(j==1)
{
if(s[1]%2==1)
printf("Meiya\n");
else
printf("Takeru\n");
}
else
{
//sort(s+1,s+1+j);
for(int i=1;i<=j;i++)
{
if(s[i]%2==1)
{
flag=0;
break;
}
}
if(flag==1)
printf("Meiya\n");
else
printf("Takeru\n");
}
}
}
}
转载：https://blog.csdn.net/Luoriliming/article/details/101627956
查看评论