首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
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
吃花椒的妙酱
华南农业大学 C++
当前状态能走到必败态说明现在是必胜态,如果没有必败态说明此时必败,打表找出所有必败态即可
1
回复
分享
发布于 2021-07-17 22:12
啥也不会呜呜呜
江西师范大学 Java
2 3前只有0 0一个必败,而且2 3一步到不了0 0。 同理,5 7前只有0 0和2 3必败,而5 7一步到不了这两个必败。
1
回复
分享
发布于 2021-07-18 10:22
ccsu_madoka
长沙学院 C++
可以学下sg函数,就能完全理解了
点赞
回复
分享
发布于 2021-07-18 00:13
还没有回复哦~
相关推荐
03-11 09:51
TCL_软件开发
TCL内推码
重要提示:内推码 ctkqzw,同等条件下使用内推码者优先面试亲爱的同学们,TCL 实业 2025 春季校园招聘现已正式启动!作为行业中的佼佼者,我们不仅拥有强大的竞争力,更注重每位员工的成长与发展。在 TCL,你将享受以下福利:🏢 公司福利:应届生落户:提供落户支持,助你安心扎根。五险一金:全面的社会保障,无后顾之忧。双休与法定节假日:工作与生活的完美平衡。额外带薪假期:第一年即可享受10天年假和5天全薪病假,关爱你的身心健康。定期体检:定期提供专业体检服务,关注你的健康。薪资职级晋升:完善的晋升制度,助你职业生涯步步高升。导师带新制:资深导师一对一指导,快速融入团队。年终奖:根据事业部表...
TCL公司福利 248人发布
点赞
评论
收藏
分享
03-13 19:05
中国传媒大学 营销
遇上了心软的面试官,暖我一整天
最近投递面试被打击的体无完肤,虽然没有实习经历,但是自己的学校背景还算不错,心想找个实习应该没那么困难吧,没成想不是被挂就是不回复,今天下午面了个创作者运营岗,面试官真的!人美心善!在提问完简历后,对我说我的背景很好,很聪明,对社会的认知程度也很深,但是差在不会包装自己,简历不应该这么写,给我提了一些简历的建议,然后又帮助梳理了我对社区产品的思路,感觉像是免费进行了个求职辅导55555第一次遇上这么好的面试官,牛客首帖献给她
据说名字越长别人越关注你的昵称我觉得我要被关注了:
哪家的
牛友故事会
点赞
评论
收藏
分享
02-10 00:02
美团_到店_Java后端开发工程师
学长学姐去哪了
也去查了一下
EEbond:
给北邮✌️跪了
点赞
评论
收藏
分享
02-25 17:03
西南大学 Java
26暑期实习简历,求拷打
211本,目标中厂,不玻璃心
点赞
评论
收藏
分享
03-13 14:40
南京工程学院 Java
亚信科技Java后端一面
基本都是八股,多背多看就行了。 1.List 有哪些实现,Arraylist 和LinkedList之间的区别是啥? List 是一个有序,可以重复的列表,List 是一个接口,下面有三个实现类,LinkedList、ArrayList、Vector。 三个实现类的创建方式 Vector<Integer> vector = new Vector<>(); ArrayList<Integer> arrayList = new ArrayList<>(); LinkedList<Integer> linkedList = new Lin...
牛牛的面试专栏
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
1
收藏
分享
评论
提到的真题
返回内容
全站热榜
更多
1
...
大厂Java基础面经总结
9628
2
...
生活比剧本还精彩,这届牛友太会写了!
6761
3
...
26届学院本上岸字节暑期!
3894
4
...
暑期实习作业帮一面
3551
5
...
一名本科生的七段实习经历(5)
3466
6
...
滴滴网约车春招 后端开发凉经
2925
7
...
3.17 快手后端一面
2610
8
...
26双非 非科班首战字节告捷 干货篇
2316
9
...
卡学历厂总结
2194
10
...
面试的时候可以不要亲亲吗
1843
创作者周榜
更多
正在热议
更多
#
笔试
#
2062771次浏览
23621人参与
#
初创公司值得加入吗?
#
14696次浏览
87人参与
#
腾讯音乐26届实习
#
153501次浏览
962人参与
#
牛友故事会
#
180081次浏览
3028人参与
#
打杂的实习你会去吗?
#
101868次浏览
898人参与
#
如果能重来,就业or读研你选哪个?
#
108494次浏览
1350人参与
#
元戎现在香不香
#
66381次浏览
541人参与
#
硬件人的简历怎么写
#
245836次浏览
2852人参与
#
反问环节如何提问
#
78020次浏览
1866人参与
#
机械人还在等华为开奖吗?
#
201970次浏览
1052人参与
#
技术岗笔试题求解
#
30399次浏览
463人参与
#
牛友打假中心
#
3844次浏览
170人参与
#
入职以后才知道的校招谎言
#
66672次浏览
387人参与
#
OPPO求职进展汇总
#
601140次浏览
4683人参与
#
机械人,说说你的烦心事
#
53598次浏览
758人参与
#
软开人,秋招你打算投哪些公司呢
#
72186次浏览
788人参与
#
联想求职进展汇总
#
227852次浏览
1867人参与
#
秋招最大的收获是什么?
#
20090次浏览
238人参与
#
两会劳动法放大招
#
33446次浏览
515人参与
#
我的省钱小妙招
#
6678次浏览
202人参与
#
22届毕业,是读研还是拿外包offer先苟着
#
5456次浏览
29人参与
#
双非应该如何逆袭?
#
26601次浏览
874人参与
牛客网
牛客企业服务