首页 > 牛牛和牛可乐的赌约2
开通博客写题解
头像 __故人__
发表于 2020-09-21 14:14:58
分析 对于博弈问题我们可以把从一个必胜状态和必败状态进行推导。我们已经知道 是个必败节点，那么 则是必胜节点，从而可以得到 也是必败节点。把图画出来，我们发现出现了一个很显然的分形结构，而最小单元是个 的图，把表打出来就可以了，时间复杂度为 。 代码 #include<bits/st 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 秃头小白
发表于 2020-09-21 16:45:53
题目链接 https://ac.nowcoder.com/acm/contest/7412/B 题目大意 棋盘左上角为(0,0)，在棋盘的(x,y)位置有一枚棋子，牛牛先移动，牛可乐再移动，轮流进行。规定：每只牛都采用最优移动策略，且每次移动只能向上移动1个或2个格，或者向左1个或2个格（不存在“左 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 Dear㉿You
发表于 2020-09-28 21:41:23
分析 牛牛和牛可乐的赌约2虽然是个博弈论，但不似之前的一眼看出结论的题，我们来试试枚举几个点，看看规律。 解释：根据必胜和必败的概念，当一个点的下一个状态全部是必胜的时候，他必败，画出这张图，就能找到规律 代码 #include<bits/stdc++.h> using nam 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 灯又烬
发表于 2020-09-20 10:19:31
题意 在大小的棋盘中，对位置的棋子进行操作，向上1或2格，向左1或2格。最终无法移动棋子的人输。 题解 根据SG定理画出NP点的转移图 SG定理 P点(必胜点)：即处于此位置，在双方无失误情况下此方必胜N点(必败点)：即处于此位置，在双方无失误情况下此方必败转移：1.对于所有必胜点，一定存在至少一种 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 AB-IN
发表于 2020-09-24 20:52:25
B 牛牛和牛可乐的赌约2 博弈，第一行/列 能除尽的都是牛牛的必败点。其它的点，如果你能从当前点转移到一个必败，那这个点就是必胜。 打表出来总结规律即可。 #include<bits/stdc++.h> using namespace std; #define ll long long 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 昨晚梦见发财了
发表于 2020-09-21 20:10:58
首先 java选手一定不要用Scanner  我咋说怎么会超时！！！ 大家可以自己画一下这个格子的地图 首先左上角的(0,0)是失败的。我们接下来只需要看一下当前所在的位置是否能走到能让对手失败的位置即可。 比如(1,0)(2,0)都可以一 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 肖先生~
发表于 2020-09-26 10:35:28
博弈打表 题目描述牛牛感觉在上一次赌约中，情况对于自己非常不利，所以决定再赌一场。这时候，牛蜓队长出现了：第一，绝对不意气用事；第二，绝对不漏判任何一件坏事；第三，绝对裁判的公正漂亮。牛蜓队长带他们来到了一个棋盘游戏，棋盘左上角是(0,0)(0,0)，这个棋盘在(x,y)(x,y)的位置有一个棋子， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 回归梦想
发表于 2020-09-20 10:04:10
来源：牛客网： 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 牛牛感觉在上一次赌约中，情况对于自己非常不利，所以决定再赌一场。这时候，牛蜓队长出现了：第一，绝对不意气用事；第二，绝对不漏判 展开全文
去ta的博客 赞 (0) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”