巴什博弈 HDU2188

素颜马尾好姑娘i 2022-08-07 06:37 152阅读 0赞

巴什博弈是个很经典的游戏。

就是只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。

那么我们可以找到一个规律，来制定必胜策略。

显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。

对于巴什博弈，那么我们规定，如果最后取光者输，那么又会如何呢？

（n-1）%（m+1）==0则后手胜利

先手会重新决定策略，所以不是简单的相反行的

例如n=15，m=3

后手 先手 剩余

0   2   13

1   3   9

2   2   5

3   1   1

1   0   0

先手胜利 输的人最后必定只抓走一个，如果>1个，则必定会留一个给对手。

由此我们可以知道：

如果n<=m，那么肯定是谁先取谁就赢。

如果n>m，并且n-m<=m，那么就是谁后取谁就赢。

如果n>m，并且n要比m大很多。

那么就有一个公式n=(m+1)\*r+s;

根据这个式子只要先手先取走s，以后先手每次取的个数与后手取的个数相加等于m+1，那么先手必赢。

但如果s为0，那么先手无论取多少个(1 -- m之间)，后手都会胜利(后手懂得巴什博弈的情况下)。

HDU2188就是一个经典的巴什博弈

网址：http://acm.hdu.edu.cn/showproblem.php?pid=2188

AC代码：

<span style="font-size:18px;">#include<stdio.h>
    int main()
    {
    	int T,n,m;
    	scanf("%d",&T);
    	while(T--)
    	{
    		scanf("%d %d",&n,&m);
    		if(n<=m) printf("Grass\n");
    		else if(n/m<=2) printf("Rabbit\n");
    		else if(n%(m+1)==0) printf("Rabbit\n");
    		else if(n%(m+1)!=0) printf("Grass\n");
    	}
    	return 0;
    }</span>

欢迎补充与纠错![微笑][smile.gif]

[smile.gif]: /images/20220805/84ba480cf57d4ef7acc7654d627b1f52.png

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关 nyoj 23 取石子（一）（巴什博弈）

取石子（一）时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述一天，TT在寝室闲着无聊，和同寝的人玩起了取石子游戏，而由于条件有限，

港控/mmm°/ 2024年02月17日 19:53/ 0 赞/ 41 阅读

相关巴什博弈小游戏（Java实现）

界面截图：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

女爷i/ 2023年02月16日 04:14/ 0 赞/ 112 阅读

相关 HDU 2147 kiki‘s game 博弈论巴什博弈 PN图

[原题链接：HDU 2147 kiki’s game][HDU 2147 kiki_s game] 题目描述 ![博弈论hdu2147][hdu2147] -----

「爱情、让人受尽委屈。」/ 2022年12月02日 10:49/ 0 赞/ 178 阅读

相关 ACM巴什博奕

NYOJ 题目23 取石子（一） ![20160805163317363][] 巴什博弈：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后

梦里梦外;/ 2022年09月25日 02:29/ 0 赞/ 107 阅读

相关博弈论--巴什博弈——HDU1846

/\巴什博弈：HDU--1846\/ \ include<iostream> using namespace std; int main() \{ int

以你之姓@/ 2022年08月27日 09:52/ 0 赞/ 192 阅读

相关巴什博弈 HDU2188

巴什博弈是个很经典的游戏。就是只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。那么我们可以找到一

素颜马尾好姑娘i/ 2022年08月07日 06:37/ 0 赞/ 153 阅读

相关 HDU 1846-Brave Game（巴什博弈-SG函数）

Brave Game Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/O

偏执的太偏执、/ 2022年07月24日 03:16/ 0 赞/ 153 阅读

相关博弈之巴什博奕

巴什博奕（Bash Game）是指这样的一个问题：有一个含有n个物品的堆，两个人轮流从这堆物品中取物品，规定每次至少取一个，最多取m个。最后取光者获胜。问你最后谁能获得胜

Dear 丶/ 2022年05月27日 11:59/ 0 赞/ 305 阅读

相关【HDU 2147】kiki's game（巴什博弈）

题目：[点击打开题目链接][Link 1] 题意：kiki和ZZ两人玩儿游戏，kiki总是先开始，游戏规则是这样的：在一个n\m的棋盘上，两人轮流移硬币，一开始硬币在棋盘的右

迷南。/ 2022年04月22日 11:32/ 0 赞/ 194 阅读

相关 HDU2188选拔自愿者

悼念512汶川大地震遇难同胞——选拔志愿者 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/3

爱被打了一巴掌/ 2021年09月20日 07:30/ 0 赞/ 210 阅读