文章目录
  1. 1. 对于SG函数的一些浅薄的理解
  2. 2. 经典SG博弈 - POJ2311 - Cutting Game
    1. 2.1. 为什么我不能将(1,1)的G值设为0?
    2. 2.2. AC代码

引言:这是一篇zz兄学习了一天博弈之后一头雾水,第二天上午听学长讲了博弈后茅塞顿开,奋笔疾书记录下来的SG博弈笔记。


对于SG函数的一些浅薄的理解

  • SG博弈中,父游戏可以转若干个子游戏,并且有几种转化子游戏的方式,每种转化方式都对应一个Grundy值,记为G1,G2,...,GnG_1 , G_2 , ... , G_n,其中任意某个Grundy值的求法是将该种转化方式下的子游戏的Grundy值异或。最终父游戏的Grundy值为mex{G1,G2,...,Gn}mex \lbrace G_1,G_2,...,G_n \rbrace
  • mexmex是指集合中无法取到的最小的自然数(包括0在内),如mex{0,1,3,5}=2mex \lbrace 0,1,3,5 \rbrace = 2

经典SG博弈 - POJ2311 - Cutting Game

为什么我不能将(1,1)的G值设为0?

  • 首先,肯定不能把这么直观的点,比如题目告诉你什么时候你获胜的点的G值设为0。就像我不能直接把UVA10561 - Treblecross 题中XXX的G值设为0一样,这样的话你把计算机想得太聪明了。

  • 那么,我该将什么情况的G值设为0?

    • 我们应该把避免在某种局面下棋的局面的G值设为0
      • 什么意思呢?举个比较容易理解的例子。比如 UVA10561 - Treblecross ,我们设 X..X,X...X,X....XX..X,X...X,X....X的G值为0,因为我们避免在这种局面下棋。
      • 回到本题,我们无法找到这样一个确切的局面。所以抽象一下,变成了我们必须避免在不得不走到w==1h==1的局面开始下棋,因此我们将拆不成w且h至少为2的局面G值返回0。
      • 再举例有N个石子,每人轮流拾取1~N个,最先取完石子的胜。则我们一定避免出现轮到我的时候,还剩N+1个棋子,那就很杯具了。因此我把N+1的G值设为0,则 N+2 ~ 2N+1的G值肯定都是大于0的,而可推N+2的G值等于0,然后推得x%(N+1)==0的点G值都为0。

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
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <set>
using namespace std;
int dp[210][210];
int grundy(int w, int h)
{
if (dp[w][h] != -1)return dp[w][h];
set<int> s;
for (int i = 2; w - i >= 2; i++)
s.insert(grundy(i, h) ^ grundy(w - i, h));
for (int i = 2; h - i >= 2; i++)
s.insert(grundy(w, i) ^ grundy(w, h - i));
int res = 0;
while (s.count(res))res++;
return dp[w][h] = dp[h][w] = res;
}
int main()
{
int w, h;
memset(dp, -1, sizeof(dp));
while (scanf("%d %d", &w, &h) == 2)
{
if (grundy(w, h) != 0)puts("WIN");
else puts("LOSE");
}

return 0;
}
文章目录
  1. 1. 对于SG函数的一些浅薄的理解
  2. 2. 经典SG博弈 - POJ2311 - Cutting Game
    1. 2.1. 为什么我不能将(1,1)的G值设为0?
    2. 2.2. AC代码