文章目录
  1. 1. 方法1:巴什博弈
  2. 2. 方法2:SG博弈

引言:回过头来又回顾一遍 SHU418 - 丢史蒂芬妮,教训中更加清晰了SG博弈的特点。


无论什么博弈,我们不要想本步以外的事情,比如说我只考虑我这一步能不能必胜能不能必败。

方法1:巴什博弈

  • 可一步取到必输点(0,0)的点:

0235722335577 \begin{matrix} 0&&2&3&&5&&7\\ \\ 2&&2\\ 3&&&3\\ \\ 5&&&&&5\\ \\ 7&&&&&&&7\\ \end{matrix}

  • 将丢史蒂芬妮这个游戏抽象为2个石子堆,每次你可以从A堆拿走素数个石子,或者从B堆中拿走素数个石子,或者从A堆和B堆同时拿走素数个石子。很显然,(0,0)这个坐标点代表没有石子,先手无法取任何石子,肯定是必输点。

  • 根据巴什博弈, 任何能一步走到必输点的点为必胜点 ,那么能把石子取到(0,0)的,上图初步罗列了一下7以内的。以(7,7)为例,它可以取到必输点(0,0),必胜点(7,0)、(0,7)或其他什么什么点,我其实不用管,只知道它可以取到必输点(0,0)就行了,(7,7)就是必胜点。

  • 我们将能一步取到(0,0)这个必输点的点全部罗列出来后,考虑取不到必输点的点是必输点,(0,1)也是必输点(实际上每次罗列完毕后的最小未罗列点必为必输点),我们同样的,罗列出所有能一步取到(0,1)点的点,标为必胜点。相似的(1,0),(1,1)也如法炮制即可。

  • 最终未罗列的点为必输点,已罗列的点为必胜点。游戏开始的时候看先手站在哪个点上即可。

  • AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#include<stdbool.h>
#define max(x,y)((x)>(y)?(x):(y))
typedef long long ll;
int prime[510];
int maze[510][510];
void init()
{
int cnt = 0;
memset(prime,0,sizeof prime);
for(int i=2;i<=500;i++)
if(!prime[i])
{
prime[cnt++]=i;
for(int j=i+i;j<=500;j+=i)
prime[j]=1;
}
for(int i=0;i<=500;i++)
{
for(int j=0;j<=500;j++)
{
if(!maze[i][j])
{
for(int k=0;k<cnt;k++)
{
if(i+prime[k]<=500)maze[i+prime[k]][j]=1;
if(j+prime[k]<=500)maze[i][j+prime[k]]=1;
if(i+prime[k]<=500 && j+prime[k]<=500)maze[i+prime[k]][j+prime[k]]=1;
}
}
}
}
}
int main(void)
{
int T;
scanf("%d",&T);
init();
while(T--)
{
int n,m;
scanf("%d %d",&n,&m);
maze[n-1][m-1]?puts("Sora"):puts("Shiro");
}
return 0;
}

方法2:SG博弈

  • 这道题我用SG博弈搞了很久发现这确实不是SG博弈,下面是我对SG博弈的理解:
  • SG博弈的条件:
    1. SG博弈是基于巴什博弈的,如n堆石子取任意个的问题。
    2. SG博弈是基于多个巴什博弈的,它需要将子游戏(基于巴什博弈的SG博弈或巴什博弈)异或,本题不能强行找到多个巴什博弈。
  • 那什么叫做多个巴什博弈?
    • 多个巴什博弈满足互不干扰,一个巴什博弈与任意其他巴什博弈的状态不交叉或传递。如POJ2311 - Cutting Game中我将A纸进行切割不影响B纸的大小。在本题,如果我将“向右走”、“向下走”、“向右下走”分别看做三个巴什博弈的话,“向右下走”将会影响另外两个博弈的状态,和另外两个博弈交叉传递了,因此本题不适用SG博弈。
文章目录
  1. 1. 方法1:巴什博弈
  2. 2. 方法2:SG博弈