首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
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
暂无评论,快来抢首评~
相关推荐
06-06 18:10
湖南大学 运营
快手福利这块,没话说
第14个司庆日,快手又给老铁们发红包了按照入职年份发放的👇<1年:2661~3 年:466 3~5年:666 5年以上:888还举办了游园会呢!看着很热闹,有在铁厂上班的牛友吗?能不能分享一下最近福利如何?
ResourceUtilization:
还得是老铁
快手公司福利 709人发布
投递快手等公司8个岗位 >
点赞
评论
收藏
分享
06-06 18:31
中国民用航空飞行学院 Java
陌陌笔试
这玩意是海笔吗,当天投,当天发笔试链接
投递挚文集团等公司9个岗位 >
点赞
评论
收藏
分享
05-27 00:13
已编辑
东华理工大学 Java
双非一本被误认为211
双非一本目前窘境学校在南昌,投外地的公司没有一个线上面的(已投1000+),南昌公司投了个遍,一家线上其他都是线下,其中两家中厂的面试已挂;另外一家小厂的后端八股基本全答上来了(挂,公司要全栈);其他的几家小厂面试都是问了些技术无关的问题(要我去当黑奴的),譬如某皓,张口闭口就是公司文化是加班,问能不能接受,项目用的还是ssh,这谁敢去啊。同寝室室友也是和我差不多情况,他比我要好些。今天好不容易简历过了个大厂,没想到是癞蛤蟆想吃天鹅肉哈哈。
内向的柠檬精在研究求职打法:
没必要,暑假前找个中厂就行了,大厂完全不敢想,之前被哔站吊打,现在有个中厂hr面了,不知道能不能过
大家都开始春招面试了吗
找工作,你会甘心进小厂还是猛冲大厂
点赞
评论
收藏
分享
05-01 22:00
重庆城市职业学院 运维工程师
各位学姐学长,请问下这样的简历还要咋优化嘞
AAA专业长城贴瓷砖刘大爷:
这样的简历我会直接丢进垃圾桶,花里胡哨的
点赞
评论
收藏
分享
06-04 20:20
成都大学 前端工程师
腾讯15分钟面试终结
有伙伴面过腾讯 CSIG云与智慧产业事业群-中台部门的前端吗?直接15分钟速面,也没有手撕,问的感觉不是很相关,全程问协议,连接这些是被当kpi了还是我太菜了,项目没有问点啊,期待了好久,准备了一些前端知识,没问到,心碎,看来又是凉经了
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
1
收藏
分享
评论
提到的真题
返回内容
全站热榜
更多
1
...
这一次我要拿回失去的一切...
2.6W
2
...
暑假还要上课,实习怎么办😭
7668
TP-LINK开奖
热聊中
3
...
25校招 双非硕 拿下大厂🐧
7069
4
...
一文详解各大厂人才项目差异点(吐血整理)
5681
5
...
所以毕业就是分手季吗?
5528
6
...
从竞赛到实习:我的成长之路与经验分享
4544
7
...
毕业前被解约了,我该何去何从。。
3743
8
...
27届勇闯小米!
3059
9
...
遇上了人机hr...有一样的吗
2899
10
...
华为招聘状态码更新通知脚本 2025最新版
2673
创作者周榜
更多
正在热议
更多
#
为了找工作你投递了多少公司?
#
2953次浏览
21人参与
#
小米提前批笔试难吗
#
33010次浏览
352人参与
#
一人一个landing小技巧
#
75794次浏览
1090人参与
#
聊聊这家公司值得去吗
#
220280次浏览
2088人参与
#
写给毕业5年后的自己
#
11165次浏览
207人参与
#
入职第一天,你准备什么时候下班
#
53693次浏览
339人参与
#
硬件人你反向读研了吗
#
41436次浏览
626人参与
#
正在实习的你,几点下班
#
155267次浏览
1080人参与
#
担心入职之后被发现很菜怎么办
#
125681次浏览
747人参与
#
校招入职后的感受
#
273629次浏览
2661人参与
#
大家每天通勤多久?
#
41659次浏览
326人参与
#
夸夸我的求职搭子
#
191892次浏览
1895人参与
#
体制内上岸心路历程
#
26459次浏览
212人参与
#
实习吐槽大会
#
51093次浏览
238人参与
#
我的租房踩坑经历
#
43577次浏览
398人参与
#
小米硬件提前批进度交流
#
166517次浏览
1519人参与
#
投格力的你,拿到offer了吗?
#
82291次浏览
572人参与
#
我和mentor的爱恨情仇
#
47120次浏览
295人参与
#
产品实习,你更倾向大公司or小公司
#
150662次浏览
1932人参与
#
移动求职进展汇总
#
1876次浏览
20人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务