游戏

游戏

https://ac.nowcoder.com/acm/contest/6871/F

非常非常玄学的题目!!!

链接:https://ac.nowcoder.com/acm/contest/6871/F
来源:牛客网

题目描述
Sparken 和 Cubercsl 喜欢玩游戏。这天他们从 Compute 那里得到了一棵有 n 个点的树(有 n-1 条边的连通图),于是他们决定利用这棵树来进行游戏。

游戏规则是这样的:

两个人轮流从树上选择一条边,对这条边两边所连接的点数较少的一边进行"收获''操作,并获得相同于所收获的点数的分数。在进行"收获''操作之后,对应边的一侧在之后的游戏中不再存在。特别的,如果两边的点数相同,可以任选一边"收获''。
如果树上只剩下一个点,那么可以单独对这一个点进行"收获''。
在双方都不能操作时,分数高者获胜。

现在 Sparken 一如既往的得到了先手的权利。她想知道,如果他们都按照最优策略进行游戏,她是否能获胜。为了保证两人一定能分出胜负,保证 n 为奇数。
输入描述:
第一行输入一个整数 T (1\leq T\leq 101≤T≤10),表示数据的组数。对于每组数据:

第一行输入一个整数 n (1\leq n \leq 191≤n≤19,n 为奇数),表示树的点数。

接下来 n-1 行,每行输入两个整数 u,v (1 \leq u, v \leq n1≤u,v≤n) 表示树的一条边。
输出描述:
对于每一组数据,在一行输出一个字符串:如果 Sparken 可以获胜,输出 Yes,否则输出 No。
示例1
输入
复制
1
3
1 2
1 3
输出
复制
Yes
要是没看到题解我也想不到要这样去写==,看了其他大佬的代码,都是写的很复杂,按照题目的意思一遍一遍去模拟,比较,算法等等。。。
但是知道我看到了另一个大佬的博客不禁

侧目,微笑,默叹,以为妙绝,绝绝绝,实在是太绝了!!!

题目说都以最优策略,那么p1>=p2>=p3>=p4...,所以p1+p3...>p2+p2...综上所诉,先手必赢!!
所以直接输出yes,有几个样例就输出几个yes

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
        cout<<"Yes"<<endl;
    return 0;
}

这么短的代码我都有点不好意思,但是确实很有道理的推理,一力破万法!!

牛客课后习题题解 文章被收录于专栏

等待蜕变

全部评论

相关推荐

找个工作&nbsp;学历是要卡的&nbsp;要求是高的&nbsp;技能不足是真的&nbsp;实习经验是0的&nbsp;简历无处可写是事实的&nbsp;钱不好赚是真的&nbsp;想躺平又不敢躺&nbsp;也不甘心躺&nbsp;怕自己的灵感和才华被掩埋甚至从未被自己发现&nbsp;又质疑自己是否真正有才华
码农索隆:你现在啊,你心里都明白咋回事,但是你没办法改变现状,一想到未来,你又没有信心狠下心来在当下努力。 得走出这种状态,不能一直困在那里面,哪不行就去提升哪,你一动不动那指定改变不了未来,动起来,积少成多才能越来越好
点赞 评论 收藏
分享
07-04 16:00
门头沟学院 Java
点赞 评论 收藏
分享
下北澤大天使:你是我见过最美的牛客女孩😍
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
05-28 12:15
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务