【博弈】2019CCPC秦皇岛赛区 - K - MUV LUV UNLIMITED

45 阅读 0 评论 30 点赞

我是靠谱客的博主敏感悟空，最近开发中收集的这篇文章主要介绍【博弈】2019CCPC秦皇岛赛区 - K - MUV LUV UNLIMITED，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=6741

题意

一棵树上，两个人进行博弈，每次操作至少删去一个叶子节点，不能删的人输。

题解

首先瞎编一个定义：一个叶子节点一直往上到分叉点为止（不包括分岔点）的这一条链称为一个枝条。

如果某棵树上存在一个长度为1的枝条，那么先手必胜。这个我们可以分两种情况进行证明：

如果删去这根长度为1的枝条，剩下的树先手必败，那么我们只需要删去这根长度为1的枝条，把必败的状态扔给对面就行了
如果删去这跟长度为1的枝条，剩下的树先手必胜，那么我们就删去剩下的树先手应该删的点，顺带删掉我们这个长度为1的枝条。

所以如果存在长度为1的枝条，先手必胜。那如果有人碰到枝条长度全是2的情况，就必败，因为它无论怎么删，必然制造出长度为1的枝条。

这样子的话，我们就可以把这棵树所有的枝条都拿出来，把他们的长度减去2，放进一个数组里。如果把数组里的数看成石子，题目转化成有若干个石子堆，每次至少拿走一颗石子，每个石子堆至多拿走一颗石子，不能拿的人输。

这就是个比较简单的博弈题，如果石子堆个数都是偶数，那先手必败，因为先手无论怎么取，后手都可以做一样的操作。如果存在奇数个石子堆，那先手必胜，他只需要把所有石子堆变成偶数即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<ll,int>piir;
const int N=2e6+7;
int f[N],d[N];
int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<=n;i++) f[i]=0,d[i]=0;
        for(int i=2,x;i<=n;i++){
            scanf("%d",&x);
            d[x]++;
            f[i]=x;
        }
        bool flag=false;
        for(int i=1;i<=n;i++){
            int cnt=0;
            if(d[i]==0){
                int u=i;
                while(u!=0&&d[u]<=1){
                    cnt++;
                    u=f[u];
                }
                if(cnt&1){flag=true;break;}
            }
        }
        if(flag) printf("Takerun");
        else printf("Meiyan");
    }
}