首页 > 试题广场 >

先手策略

[单选题]
两人在一个 n 个点的无向完全图上进行游戏，每次可以选择当前图中某条两个端点度数奇偶性相同的边删除，谁不能操作谁输，则在n=1,2,3,......,9,10 中，有____个图先手有必胜策略。 
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
查看答案及解析
添加回答
推荐
渊鸿头像 渊鸿
N个点的无向完全图边数为：N*（N-1）/2；先手获胜必须总数为奇数；
N=1,2,3,......,9,10代入公式，为奇数的只有N=2,3,6,7,10这5个。
编辑于 2016-02-25 10:29:13 回复(5)
老空楼头像 老空楼
首先，2k+1个结点与2k个结点的情况是一样的，因为其多出了个不能对其操作的结点，最简单的例子是1个结点和0个结点，次简单点的可以自己画个2、3个结点或4、5个结点的来分析。所以只用讨论2k个结点的情况。2k个结点有 k * ( 2k - 1 ) 条边，当有奇数条边时，就能保证先手必胜。所以k = 1，3，5，7…换成对应的2k以及2k+1，即2，3，6，7，10，11，14，15…都可以满足情况。又因为题目限制2k <= 10 及 2k + 1 <= 10，所以2，3，6，7，10满足，共5个。
发表于 2016-09-17 11:23:30 回复(0)
这世界很cool头像 这世界很cool
这题，思想是动态规划
首先列出1 2 3 的情况，后面都是动态规划为1 2 3 的情况，
比如4 ，6条线，删除 3*2-1 删除5条线，还剩一条线，则先手失败，其他情况类似，这样
注意：1没有线，直接算先手输了
发表于 2018-09-04 09:53:59 回复(0)
璎珞-沐头像 璎珞-沐
总觉得解释的不对，每次可以选择当前图中两个端点度数奇偶性相同的边删除，这句话是不是被忽略了
发表于 2017-05-25 19:50:27 回复(0)
牛客940318头像 牛客940318
我靠，你们的这解释也太牵强了吧。
发表于 2015-10-18 17:17:55 回复(0)
搭上最后一班车头像 搭上最后一班车
n=1，无边可以删除，先手输；
n=2，只有一条边，且顶点度数均为1，先手删除这条边，胜；
n=3~9，对于任意无向全连通图，边数为n(n-1)/2，如果边数为奇数，那么先手会删除最后一条符合条件边，胜；如果边数为偶数，则先手输。共有4个图符合。
故满足条件的图有5个。
发表于 2016-09-09 14:49:34 回复(0)
牛客8788852号头像 牛客8788852号
如渊鸿所说。
另外，对于完全无向图来说，删除边操作前，任何两个相邻顶点的度奇偶性相同。n次删除操作后，除非没有边了，否则总能找到一个边的两个顶点奇偶性相同。举例子总结出来的经验。若有依据或异议，请指正。
发表于 2017-06-10 16:35:23 回复(0)
公众号:重温新知头像 公众号:重温新知
不懂，蒙的
发表于 2017-04-27 14:57:52 回复(0)
别灰心头像 别灰心
有奇数个边的图一定存在某条边的两个端点度数奇偶性相同。 证明如下: 假设当边为奇数时不存在某条边的两个端点度数奇偶性相同。那么对于每一条边来说，其左右端点度数和一定为奇数，一共有奇数条边，加起来也为奇数，与图的度数和为偶数矛盾。但是在求和的时候会重复计算度数，比如一个边的某端点度数为n，那么有n条边连接这个端，点，也就是说n会被计算n次，度数多计算了n*(n-1)为偶数。也就是说在这个假设下，奇数条边最后的度数和还是为奇数，矛盾。故有奇数条边的图一定存在着两个端点度数奇偶性相同的边。 在这个结论的基础上，当完全图有奇数条边，先手的一定能找到一条删除，此后边的条数变为偶数，如果后手还能删，则重新变为奇数，直至变为某个偶数时后手不能删，先手胜利。同理可得先手面临的是偶数时，必败。 个人想法，不一定对，欢迎指正
发表于 2023-09-01 00:36:02 回复(0)
coding的鱼头像 coding的鱼
N个点的无向完全图边数为：N*（N-1）/2；先手获胜必须总数为奇数；
N=1,2,3,......,9,10代入公式，为奇数的只有N=2,3,6,7,10这5个。
发表于 2016-03-16 11:12:25 回复(1)
我心飞翔6496头像 我心飞翔6496
规律题，如果n个顶点完全无向图的边最多n*2(n-1)条，若n*2(n-1)/2%2=1则先手赢，若n*2(n-1)/2%2=0则后手赢，但是1要特别判断一定是先手输。所以1…10只有2，3，6，7，10。 拿去交代码吧QWQ
发表于 2023-11-19 22:35:21 回复(0)
mopodao头像 mopodao
对称性：C(n,2)得图有多少边。只要边是奇数就先手win
编辑于 2015-08-27 00:27:28 回复(2)
列灵头像 列灵
无向完全图,每个点度数相同,当去掉一条边,则只能从剩下的(n-2)的点集中选择对应的边，
由数学归纳法得，当点的个数为（n/2为奇数时）先手必胜
发表于 2022-09-25 10:25:13 回复(0)
上岸er头像 上岸er
看到一个大佬写的，感觉不错。

n=1，无边可以删除，先手输； 
n=2，只有一条边，且顶点度数均为1，先手删除这条边，胜； 
n=3~9，对于任意无向全连通图，边数为n(n-1)/2，如果边数为奇数，那么先手会删除最后一条符合条件边，胜；如果边数为偶数，则先手输。共有4个图符合。 
故满足条件的图有5个。
发表于 2022-08-10 09:07:29 回复(0)
牛客515325384号头像 牛客515325384号
有五个奇数连接的边 只有第一次删奇数的边就有必胜把握
发表于 2022-05-21 18:03:48 回复(0)
梅老板头像 梅老板
咋看不懂这个题目
发表于 2022-02-04 23:41:32 回复(0)
Vigilr头像 Vigilr
这道题好难
发表于 2021-01-21 20:51:03 回复(0)
江边鸟头像 江边鸟
虽然题目要求只能选择当前图中两个端点度数奇偶性相同的边删除。但完全图都是对称的，一条边满足条件。则对称边必然满足。一条边不满足，则对称边也不满足。所以只要选上一次删的对称边就能保证不输。最后必然剩偶数条边没删。故而想要先手获胜必须有奇数条边。
发表于 2019-11-16 18:13:02 回复(0)
codeor头像 codeor
对于完全无向图，任意两点肯定是连通的，n=1时，只有一个结点直接排除，对于其他，只要为奇数结点，先手肯定会赢，因为每次拿两个结点，如果是偶数那么最后拿的也是两个，要为奇数，最后只剩一个结点，无法拿取，所以先手就赢了
发表于 2019-07-26 20:45:54 回复(0)
Gwen_夜雨声烦头像 Gwen_夜雨声烦
偶数条边，比如2，我一次你一次，最后肯定是对方拿，肯定我输
奇数条边，比如3，我先拿，最后也是我那，肯定我赢
选择当前图中两个端点度数奇偶性相同的边删除：我们只要知道，在一个图里，总能找到两个端点度数一样即可

发表于 2018-09-27 10:43:27 回复(0)
凡凡的女孩儿头像 凡凡的女孩儿
简单粗暴，为奇数个顶点的先画的就胜利✌
编辑于 2018-08-13 10:31:08 回复(0)
提交观点

问题信息

图
来自：阿里巴巴2016研发工...
难度：
29条回答 12001浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号