首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
AI面试、笔试、校招、雇品
HR免费试用AI面试
最新面试提效必备
登录
/
注册
PLA_Nh
2021-07-17 20:16
南通大学 Java
关注
已关注
取消关注
关于a题的疑问
我们可以从1枚举完所有n=1,m=k的情况,这些都是必胜态。但是为什么可以认为接下来n=2的0为必败态(A[2][3]==0),用作踏板来进一步得到到达必输态的所有步数呢?请问如何确定他是必败的?这个n=2的0可不可能也是一个必胜态,只是当前几步走不到而已呢?比如5 7,他可以减到的组合很多,怎么确定它所有的走法都会导致必胜态呢?数据很大时要一一列举判断吗。求解
提示
全部评论
推荐
最新
楼层
NCHU19207325
南昌航空大学 C++
必败态的定义就是,”面对当前状态的选手一定会输“的状态。而我们又知道这个游戏没有平局,所以在所有状态中除了必败态的那些状态都是必胜态(这个状态不是必败态,也就是说必定存在至少一种最优的策略,使得只要你按这种策略走,无论对方怎么走,你都能必胜,否则如果不存在这种能让你必胜的策略,那你就是必败的了,总不能平局吧)。清楚了这个概念之后就可以开始打表了。 这里我们用(n,m)这种写法来枚举状态,同时保证 m>n(不考虑 m=n 的情况,太明显了),毕竟 (1,2)和(2,1)是一样的嘛。 首先我们知道最初的必败态是(0,0),很显然嘛,题目里都说了,谁没法拿石子谁就输,所以如果你遇到了(0,0),那你就输了,所以(0,0)是必败态。然后我们看(1,m),很显然(1,m)都能通过一次操作走到(0,0),也就是说让后手的玩家碰到必败态,所以(1,m)都是必胜态,然后我们看(2,3),发现(2,3)不能一次操作走到(0,0),也就是说对(2,3)进行一次操作以后后,后手玩家一定会碰到必胜态 【 因为(2,3)之前的状态除了(0,0)都是必胜的,而且你又走不到(0,0)】,即(2,3)是个必败态,然后其他的(2,m)都可以一次操作走到(2,3),所以当 n 为 2 时,除了(2,3)都是必胜的。 继续推下去,易得出(3,m)和(4,m)也都是必胜的(都能一次操作走到(2,3))。 然后看 n=5时,(5,6)必胜,因为可以一次走到(2,3),(5,7)不能一次走到(2,3),也不能一次走到(0,0),而(5,7)其他能走的状态前面已经枚举过了,都是必胜态,所以(5,7)也是必败的。 一直这样递推下去,打表就OK了。我们用一个集合存好全部的必败态,集合最开始只有一个元素(0,0),每次遇到一个新的状态就判断一下它能否跳到存着所有必败态的集合中的任意一个状态,如果能,则说明这是必胜态,如果不能,则这是一个新的必败态,把他加入集合之中去,暴力跑完所有状态就行了。
9
回复
分享
发布于 2021-07-18 10:51
啥也不会呜呜呜
江西师范大学 Java
2 3前只有0 0一个必败,而且2 3一步到不了0 0。 同理,5 7前只有0 0和2 3必败,而5 7一步到不了这两个必败。
1
回复
分享
发布于 2021-07-18 10:22
吃花椒的妙酱
华南农业大学 C++
当前状态能走到必败态说明现在是必胜态,如果没有必败态说明此时必败,打表找出所有必败态即可
1
回复
分享
发布于 2021-07-17 22:12
ccsu_madoka
长沙学院 C++
可以学下sg函数,就能完全理解了
点赞
回复
分享
发布于 2021-07-18 00:13
暂无评论,快来抢首评~
相关推荐
05-20 13:40
拼多多集团_服务端研发工程师
拼多多26届暑期实习内推末班车
现在这么卷,有提前锁定offer的机会或履历还不抓紧? 内推岗位:算法、后端、安全工程师、前端 【拼多多集团-PDD实习生招聘】内推链接:https://careers.pddglobalhr.com/campus/intern?t=C6JlwizcX2,内推码:C6JlwizcX2。期待你的加入!我们一起,无拼不青春!(通过此链接投递计入内推,内推简历优先筛选~) #内推##实习##拼多多#
投递拼多多集团-PDD等公司10个岗位 >
点赞
评论
收藏
分享
06-09 18:06
滴滴_运维开发工程师(准入职员工)
滴滴内推-滴滴内推码
薪资: 我是运营岗,本科生 150/d,工作时间是早10晚7,弹性打卡(但其实每天打卡四小时就算一天),午休 2 小时(不过中午休息区比较难抢) 交通: 我在东软职场,每天上下班有西二旗到公司往返的摆渡车,不同职场之间往来打车可以报销,21:00 下班回家也可以报销(但我从来没用过,没加过班) 福利: 开水畅饮,特定节假日有礼盒,公司经常会举办各种活动,参加会有小礼品和积分,积分可以在商城兑换物品。 吃饭: 午饭需要自己解决,每晚有 30 的餐补,可以去周边餐馆点餐,也可以在内部软件点餐,直接送到所在楼层茶水间 总体感觉在滴滴很舒服,工作强度不大,我所在的部门也没有太多dirty wo...
滴滴公司福利 874人发布
点赞
评论
收藏
分享
不愿透露姓名的神秘牛友
06-05 04:14
已编辑
简历求锐评,不玻璃心
学历太差了就给遮上了字节投了五次 五次全简历挂,求教
真烦好烦真烦:
看着感觉好强啊,这都过不了吗
投递字节跳动等公司10个岗位
面试中的破防瞬间
点赞
评论
收藏
分享
05-08 23:17
滴滴_Java开发(实习员工)
不删
自由水:
笑死了,敢这么面试不敢让别人说
点赞
评论
收藏
分享
06-06 16:42
湖南大学 运营
花旗金融裁员,3500人瞬间停工
🍠上看到的消息花旗金融直接搞一刀切,三千多人同时断外网、收权限、禁浏览器、禁teams、禁c盘……据透露,大部分是n+6的赔偿标准虽事发突然,但是赔偿已经算大方的了……最近还听说好几家外企裁员,这都怎么了?
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
1
收藏
分享
评论
提到的真题
返回内容
全站热榜
更多
1
...
春招失败准备转行了
1.7W
2
...
这些假国企都给我避雷!
1.2W
华为开奖进度👉
热聊中
3
...
代码拜拜!被烟草录取了✌
9328
4
...
27届腾讯一面,强度太大了..
6513
5
...
Golang面试项目怎么找?
5982
6
...
一文详解各大厂人才项目差异点(吐血整理)
5591
7
...
宝宝你是最棒的宝宝
5531
8
...
牛友们,你们有多久没回家了?
4684
9
...
论双非大一的“暑期”能拿下大厂offer吗?
4548
10
...
大厂实习后的一些反思与认知改变
4030
创作者周榜
更多
正在热议
更多
#
考研对你找工作产生了哪些影响?
#
3202次浏览
41人参与
#
机械只有读研才有出路吗?
#
19706次浏览
228人参与
#
聊聊这家公司值得去吗
#
237017次浏览
2218人参与
#
远程面试的尴尬瞬间
#
100811次浏览
828人参与
#
你认为哪个岗位找工作最卷
#
15481次浏览
59人参与
#
打杂的实习你会去吗?
#
108009次浏览
942人参与
#
kpi面有什么特征
#
34747次浏览
256人参与
#
工作中哪个瞬间让你想离职
#
24088次浏览
166人参与
#
硬件人绝对不能踩的坑
#
61178次浏览
735人参与
#
职场人,说说你的烦心事
#
8886次浏览
81人参与
#
你有哪些缓解焦虑的方法?
#
2657次浏览
116人参与
#
职场上哪些事情令人讨厌
#
16809次浏览
86人参与
#
为了找工作你投递了多少公司?
#
11224次浏览
160人参与
#
秋招最大的收获是什么?
#
34078次浏览
300人参与
#
你今年的平均薪资是多少?
#
126630次浏览
661人参与
#
运营/市场营销人的秋招现状
#
17156次浏览
189人参与
#
实习生应该准时下班吗
#
223394次浏览
1397人参与
#
大家每天通勤多久?
#
42069次浏览
331人参与
#
如果可以,你希望哪个公司来捞你
#
88222次浏览
371人参与
#
运营人求职交流聚集地
#
135288次浏览
983人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务