# sg值的求解(NIM)

1堆的情况：

``` 1 #include<bits/stdc++.h>
2 int x=9,grundy[1000],k=2,A[1000]={1,4},n=3;
3 using namespace std;
4 int main(){
5     grundy[0]=0;
6     for(int i=1;i<=9;i++){
7         set<int>s;
8         for(int j=0;j<k;j++){
9             if(i>=A[j]) s.insert(grundy[i-A[j]]);
10         }
11         int g=0;
12         if(s.count(g)!=0) g++;
13         grundy[i]=g;
14     }
15     if(grundy[x]) printf("Alice\n");
16     else printf("Bob\n");
17
18 } ```

n堆的情况：

``` 1 #include<bits/stdc++.h>
2 #define MAX_N 1000
3 #define MAX_K 1000
4 #define MAX_X 1000
5 using namespace std;
6 int N=3,K=3,X[MAX_N]={5,6,8},A[MAX_K]={1,3,4};
7 int grundy[MAX_X+1];
8 int main(){
9     grundy[0]=0;
10     int max_x=*max_element(X,X+N);
11
12     for(int i=1;i<=max_x;i++){
13         set<int>s;
14         for(int j=0;j<K;j++){
15             if(A[j]<=i) s.insert(grundy[i-A[j]]);
16         }
17         int g=0;
18         while(s.count(g)!=0) g++;
19         grundy[i]=g;
20     }
21
22     int x=0;
23     for(int i=0;i<N;i++) x^=grundy[X[i]];
24
25     if(x!=0) puts("Alice\n");
26     else puts("Bob\n");
27     return 0;
28 }```

## hdu5795 A Simple Nim 求nim求法，打表找sg值规律 给定n堆石子，每堆有若干石子，两个人轮流操作，每次操作可以选择任意一堆取走任意个石子（不可以为空） 或者选择一堆，把它分成三堆，每堆不为空。求先手必胜，还是后手必胜。

/** 题目:A Simple Nim 链接:http://acm.hdu.edu.cn/showproblem.php?pid=5795 题意:给定n堆石子,每堆有若干石子,两个人轮流操作,每次操作可以选择任意一堆取走任意个石子(不可以为空) 或者选择一堆,把它分成三堆,每堆不为空.求先手必胜,还是后手必胜. 思路: 组合游戏Nim: 计算出每一堆的sg值,然后取异或.异或和>0那么先手,否则后手. 对于每一堆的sg值求解方法: 设:sg(x)表示x个石子的sg值.sg(x) = mex{sg

## Nim or not Nim? hdu3032 SG值打表找规律

Nim or not Nim? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 858    Accepted Submission(s): 412 Problem Description Nim is a two-player mathematic game of strategy in which players take turns

## Treblecross 博弈SG值

Treblecross is a two player game where the goal is to get three X in a row on a one-dimensional board. At the start of the game all cells in the board are empty. In each turn a player puts an X in an empty cell, and if the move results three X next t

## 【UVA1378】A Funny Stone Game （博弈-求SG值-输出方案）

[题目] Description The funny stone game is coming. There are n piles of stones, numbered with 0, 1, 2, ..., n − 1. Twopersons pick stones in turn. In every turn, each person selects three piles of stones numbered i, j, k(i < j, j ≤ k and at least one s

## Nim 游戏、SG 函数、游戏的和

Nim游戏 Nim游戏定义 Nim游戏是组合游戏(Combinatorial Games)的一种,准确来说,属于"Impartial Combinatorial Games"(以下简称ICG).满足以下条件的游戏是ICG(可能不太严谨):1.有两名选手:2.两名选手交替对游戏进行移动(move),每次一步,选手可以在(一般而言)有限的合法移动集合中任选一种进行移动:3.对于游戏的任何一种可能的局面,合法的移动集合只取决于这个局面本身,不取决于轮到哪名选手操作.以前的任何操作.骰子的点数