sg值的求解(NIM)

硬币游戏2

挑战程序设计竞赛P315

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 }
时间: 04-14

sg值的求解(NIM)的相关文章

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.对于游戏的任何一种可能的局面,合法的移动集合只取决于这个局面本身,不取决于轮到哪名选手操作.以前的任何操作.骰子的点数

博弈论之Nim

博弈论(一):Nim游戏 重点结论:对于一个Nim游戏的局面(a1,a2,...,an),它是P-position当且仅当a1^a2^...^an=0,其中^表示位异或(xor)运算. Nim游戏是博弈论中最经典的模型(之一?),它又有着十分简单的规则和无比优美的结论,由这个游戏开始了解博弈论恐怕是最合适不过了. Nim游戏是组合游戏(Combinatorial Games)的一种,准确来说,属于“Impartial Combinatorial Games”(以下简称ICG).满足以下条件的游戏

博弈之——SG模板(hdu1848&amp;&amp;hdu1536)

很久没搞博弈了.先来写个模板: 现在我们来研究一个看上去似乎更为一般的游戏:给定一个有向无环图和一个起始顶点上的一枚棋子,两名选手交替的将这枚棋子沿有向边进行移动,无法移动者判负.事实上,这个游戏可以认为是所有Impartial Combinatorial Games的抽象模型.也就是说,任何一个ICG都可以通过把每个局面看成一个顶点,对每个局面和它的子局面连一条有向边来抽象成这个"有向图游戏".下面我们就在有向无环图的顶点上定义Sprague-Garundy函数. 首先定义mex(m

(博弈 sg入门2)

接下来介绍Nim游戏(同样引用杭电上的,懒的打字) 1.有两个玩家:   2.  有三堆扑克牌(比如:可以分别是    5,7,9张):  3. 游戏双方轮流操作:  4. 玩家的每次操作是选择其中某一堆牌,然后从中取走任意张:   5.最后一次取牌的一方为获胜方: 想一会: 还记得刚才说的P点和N点吗?P:必败点,N:必胜点 先给出结论,这里要用到位运算,异或:^ 游戏的某个位置(x1,x2,x3) x1,x2,x3表示3堆的个数.当且仅当 x1^x2^x3=0时,此点才是必败点P: 结论可以

博弈之——SG模板

很久没搞博弈了.先来写个模板: 现在我们来研究一个看上去似乎更为一般的游戏:给定一个有向无环图和一个起始顶点上的一枚棋子,两名选手交替的将这枚棋子沿有向边进行移动,无法移动者判负.事实上,这个游戏可以认为是所有Impartial Combinatorial Games的抽象模型.也就是说,任何一个ICG都可以通过把每个局面看成一个顶点,对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”.下面我们就在有向无环图的顶点上定义Sprague-Garundy函数. 首先定义mex(minima