2017 多校赛6 Gameia hdu 6105

飞机直达

题目

题目意思:太长了,自己看吧。
题目思路:这个博弈可以得出一个很重要的结论(神队友分析出来的,很坑的神队友):如果能把树切割成两两配对的形式则Bob赢,否则Alice赢(网友可以自行验证)。我提供的实现思路(树拓扑),顺便也和另一队友分别做了验证和提供数据。后来想了一下,也可以用二分图最大匹配来做嘛,一棵树能两两匹配当且经当它完美匹配(最大匹配数*2==节点数)。做法多种多样,关键是这个结论的分析过程(多得神坑队友给力,说他神坑是因为他老犯低级错误OrzOrz)。
代码还是贴一下吧(队友主写)。。。

#include <cstring>
#include <cstdio>
#include <iostream>
#include <string>
#include <climits>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
#define MAXN_NUM 0x3f3f3f3f
#define EPS 1e-6

#define DGA(x)
#define DFA(x) 
#define PRT(x,a) printf("%s%d%s\n",a,x,a)
#define TEST(x)  printf("---------test %c---------\n",x+'A')
#define Fin(i,f,t) for(int i=f;i<=t;++i)
#define Fde(i,f,t) for(int i=f;i>=t;--i)
#define SfI(x)  scanf("%d",&x)
#define SfLL(x) scanf("%lld",&x)
#define SfD(x)  scanf("%lf",&x)
#define SfC(x)  scanf("%c",&x)
#define SfS(x)  scanf("%s",x)

#define MAXN 5000

int deg[MAXN]={},far[MAXN]={};//deg树节点的度(儿子数), far是father的意思,怪题目单词错了。
bool exist[MAXN];//节点是否以删除
int N,K;
bool Judge(){
    if(N%2)//显然奇数节点不可能两两配对
        return false;
    if(K < (N/2-1))
        return false;
       //我不知道队友为什么对这个判断产生疑问,很明显的撒:留下N/2条边,原N-1条边,最少需要(N/2-1)次切割
    memset(exist,true,sizeof exist);
    exist[0] = false;//这里是个坑
    int cnt = N;
    while(cnt){
        Fin(i,1,N) if(!deg[i]){//叶子节点,度数为0
            //printf("%d - %d\n",i,far[i]);
            if(exist[far[i]]){
                --deg[far[far[i]]];//可能产生新的叶子节点
                exist[i] = exist[far[i]] = false;//删点
                deg[i] = deg[far[i]] = -1;//删点
                cnt -= 2;
                break;
            }
            else//如果存在未删除的叶子节点,但是他父亲已经删除了,gg
                return false;
        }
    }
    return true;
}
int main(void){
    DFA(freopen("D:\\test.txt","r",stdin));
    //freopen("D:\\tsst.txt","w",stdout);
    int T;
    SfI(T);
    Fin(t,1,T){
        memset(deg,0,sizeof deg);
        scanf("%d%d",&N,&K);
        Fin(i,2,N){
            SfI(far[i]);
            ++deg[far[i]];
        }
        printf("%s\n",Judge()?"Bob":"Alice");
    }
    return 0;
}

这个题目对我们这种渣渣来说算难题了,能写出来算侥幸Orz。。

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值