[笔记] 巴什博弈

[笔记] 巴什博弈

Define

巴什博弈是最简单的一种博弈,定义如下

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

必胜态(N)和必败态(P)

• 所有必胜态(N)肯定有一种方法转移到必败态(P)
• 必败态(P)无论怎么转移,都会转移到必胜态(N)(下一手必胜)
• 所有终结点是必败态(P)

分析必胜态(N)和必败态(P)都是以终结点开始进行逆序分析

Analyze

对于必胜态(N)和必败态(P)的分析

现在如果一共有(m+1)个物品，我们去取它，先手至少要取一个，却又把所有的物品取不完，这样就导致了后手的必赢

如果物品数小于等于能取的数目，是必胜的，因为只用取一次，如果是大于能取的数目的，我们可以把总数(n)分解为((m+1)∗x+r)

显然对于((m+1)∗x+r)个数，如果我们先手，只需要取走(r)个数，然后留((m+1)∗x)给对方，这样一来，每次对方取一个数(y)我们就只需要取(m+1−y)个就可以了，也就是说每一个(m+1)的最后一个都是最开始的先手取的，这样就能保证如果是可以分解为((m+1)∗x+r)的话，先手必胜，如果只能分解为((m+1)∗x)的话，先手必败

Code

[HDU2846] Brave Game

#include <iostream>
#include <cstdio>
#define sc(x) scanf("%d", &x);

using namespace std;

int main(){
	int t, n, m;
	sc(t);
	while(t--){
		sc(n);
		sc(m);
		if(n % (m + 1) == 0)
			printf("second
");
		else 
			printf("first
");
	}
	return 0;
}