Codeforces Round #668 (Div. 2) D. Tree Tag 题解(博弈)

题目链接

题目大意

给你一颗树，Alice在a点，Bob在b点，Alice最多走da步，Bob最多走db步，两人轮流走路。要你判断经过无数次追赶后，Alice是否可以追上Bob，两人进行的都是最优策略

题目思路

感觉也不特别像一个博弈，但是也不知道该划分到哪里了

这个题目没想象的那么难，首先如果a和b的距离小于da，那么肯定Alice胜，如果2da>=len,len代表树的直径，那么也是Alice胜。前两个都是显然的。还有一种如果2*da>=db,这个代表不存在A只差一步追上B的时候，B可以反向再跑一段很长的距离，使得A一步追不上B。那么也是Alice胜

代码

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<vector>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<unordered_map>

#define fi first

#define se second

#define debug printf(" I am here\n");

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;

const double eps=1e-10;

int n,a,b,da,db,dis[maxn];

int head[maxn],cnt;

struct node{

    int to,next;

}e[maxn<<1];

void add(int u,int v){

    e[++cnt]={v,head[u]};

    head[u]=cnt;

}

void dfs(int son,int fa){

    int cur=0;

    for(int i=head[son];i;i=e[i].next){

        if(e[i].to==fa) continue;

        dis[e[i].to]=dis[son]+1;

        dfs(e[i].to,son);

    }

}

void init(){

    cnt=0;

    for(int i=1;i<=n;i++){

        head[i]=dis[i]=0;

    }

}

signed main(){

    int _;  scanf("%d", &_);

    while(_--){

        scanf("%d%d%d%d%d",&n,&a,&b,&da,&db);

        init();

        for(int i=1,u,v;i<=n-1;i++){

            scanf("%d%d",&u,&v);

            add(u,v),add(v,u);

        }

        dfs(a,-1);

        bool flag=0;

        if(da>=dis[b]){//第一次直接抓住Bob

            flag=1;

        }

        int ma=0,v;

        for(int i=1;i<=n;i++){//寻找最远的端点

            if(dis[i]>ma){

                ma=dis[i];

                v=i;

            }

        }

        for(int i=1;i<=n;i++){

            dis[i]=0;

        }

        dfs(v,-1);

        int len=0;

        for(int i=1;i<=n;i++){

            len=max(len,dis[i]);

            //树的直径

        }

        if(2*da>=len||2*da>=db){

            flag=1;

        }

        puts(flag?"Alice":"Bob");

    }

    return 0;

}

巴特西

Codeforces Round #668 (Div. 2) D. Tree Tag 题解(博弈)

题目链接

题目大意

题目思路

代码

最新文章

热门文章