基础博弈论（巴什博奕、斐波那契博弈、威佐夫博奕、尼姆博奕）

【前言】

今天才算是搞明白了（？？）最基本的四种博弈

【小结】

1.巴什博奕（Bash Game）

一堆中取石子，两个人轮流取石子，每次取石子量至少为1，至多为m，先取完者胜利。

当n%(m+1)==0，后手胜。

2.斐波那契博弈（Fibonacci Game）

一堆中取石子，两个人轮流取石子，第一次可以取任意多个，但不能全部取完，以后每次取的石子数不能超过上次的两倍，先取完者胜。

当n为斐波那契数时，先手必败。

3.威佐夫博奕（Wythoff Game）

两堆中取石子，两个人轮流取石子，每次从一堆中取任意数量石子或者同时从两堆中取相同数量石子，先取完者胜利。

当形成奇异局势时后手胜。

即令两堆石子量分别为a、b(a<b)，c=b-a,当a=(c*(1+sqrt(5))/2)时，后手胜。

4.尼姆博奕（Nimm Game）

若干堆中取石子，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，先取完者胜利。

所有堆石子的数量异或为0时后者胜。

【题目】

1122: 取石子游戏II

Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 234  Solved: 122 [Submit][Status][Web Board]

Description

一堆石子有n个,两人轮流取.每次取最少取1个,最多取m个。取完者胜.先取者负输出"Second win".先取者胜输出"First win"

Input

多组测试数据。

每组测试数据包含2个正整数n,m。(n,m<=10000000)

Output

对于每组测试数据，输出谁获胜.

Sample Input

2 1

3 2

3 1

Sample Output

Second win

Second win

First win 

【题解】

巴什博奕

【代码】

#include<stdio.h> int main() { int n,m; while(~scanf("%d%d",&n,&m)){ if(n%(m+1)==0) printf("Second win\n"); else printf("First win\n"); } return 0; }

【题目】

 

 

1121: 取石子游戏I

Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 276  Solved: 156 [Submit][Status][Web Board]

Description

一堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".

Input

多组测试数据。

每组测试数据包含1个整数n。(1<n<=1000000000)

Output

对于每组测试数据，输出谁获胜.

Sample Input

2

13

10000

Sample Output

Second win

Second win

First win 

【题解】

 

斐波那契博弈

【代码】

#include<bits/stdc++.h> using namespace std; int main() { int f[50],i,n; f[0]=1,f[1]=2; for(i=2;i<50;i++) f[i]=f[i-1]+f[i-2]; while(~scanf("%d",&n)) { for(i=0;i<50;i++) if(n==f[i]) break; else if(n>f[i]) continue; if(i<50) printf("Second win\n"); else printf("First win\n"); } return 0; }

【题目】

 

Problem A: Return of the Nim

Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 11  Solved: 9 [Submit][Status][Web Board]

Description

Sherlock and Watson are playing the following modified version of Nim game:

  There are n piles of stones denoted as  piles0 ,   piles1 ,...,   pilesn-1 , and n is a prime number;  Sherlock always plays first, and Watson and he move in alternating turns. During each turn, the current player must perform either of the following two kinds of moves:       1.  Choose one pile and remove k(k >0) stones from it;     2.  Remove k stones from all piles, where 1≤k≤the size of the smallest pile. This move becomes unavailable if any pile is empty.   Each player moves optimally, meaning they will not make a move that causes them to lose if there are still any better or winning moves.

Giving  the initial situation of each game, you are required to figure out who will be the winner

Input

The first contains an integer, g, denoting the number of games. The 2×g subsequent lines describe each game over two lines: 1. The first line contains a prime integer, n, denoting the number of piles. 2. The second line contains n space-separated integers describing the respective values of piles0, piles1,..., pilesn-1.

1≤g≤152≤n≤30, where n is a prime.1≤pilesi≤10^5 where 0≤i≤n−1

Output

For each game, print the name of the winner on a new line (i.e., either “Sherlock” or “Watson”)

Sample Input

2 3 2 3 2 2 2 1

Sample Output

Sherlock Watson

【题解】

当n=2时为威佐夫博奕，当n>2时为尼姆博奕。

【代码】

#include<bits/stdc++.h> using namespace std; int main() { int t,n,a[35],i; scanf("%d",&t); while(t--) { scanf("%d",&n); int f=1; for(i=0;i<n;i++) scanf("%d",&a[i]); if(n==2) { if(a[0]>a[1]) swap(a[0],a[1]); int b=a[1]-a[0]; if(a[0]==floor(b*(1+sqrt(5))/2)) f=0; } else{ int c=a[0]; for(i=1;i<n;i++) c^=a[i]; if(c==0) f=0; } if(f) printf("Sherlock\n"); else printf("Watson\n"); } return 0; }