HDU 5795 A Simple Nim（Nim游戏博弈+SG函数）

  
  

   
   2
2
4 4
3
1 2 4
  
  

  
  

   
   Second player wins.
First player wins.
  
  

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
/*
打表部分 
*/
int sg[32];
bool vis[32];
void print(){
	for(int i=1;i<32;i++){
		memset(vis,0,32);
		int j,k;
		
		for( j=0;j<i;j++) vis[sg[j]]=1;//find the >=0's intergers
		
		for( j=1;j<i;j++)//save after divide;
			for( k=1;j+k<i;k++)
				vis[sg[j]^sg[k]^sg[i-k-j]]=1;
		for (j=0; j<32; j++){ //find the min j doesn't belong to this sg;	
			if(!vis[j]) break;
		}
		sg[i]=j;
		
	}
	
	
	for(int i=1;i<32;i++){
		cout<<i<<" "<<sg[i]<<endl;
	}
}
/*
主程序部分 
*/ 
int findsg(int s){
	if(s%8==0) return s-1;
	else if((s+1)%8==0) return s+1;
	else return s;
}
int main(){
	print();
	int t,n;
	scanf("%d",&t);
	while(t--){
		int ans=0;
		int s;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&s);
			ans^=findsg(s);
		}
		if(ans) printf("First player wins.n");
		else printf("Second player wins.n");
	
	}
}

题意：两个人在n堆里取糖果，每个人可以选择在同一堆里取任意数量的糖果或者把某一堆糖果分成三堆，求最后的胜者；

对于博弈游戏，我们首先要了解SG函数；

sg 即Graph Game，把博弈游戏抽象成有向无环图

(1) 有向无环图

(2) 玩家1先移动，起点是x0

(3) 两个玩家轮流移动

(4) 对于顶点x, 玩家能够移动到的顶点集记为F(x).

(5) 不能移动的玩家会输掉游戏

我们可以通过计算sg值来定胜负，如果sg>0，则先手胜，反之则先手负；

如何计算sg值：

sg值可以理解为一个数能被继续操作的次数（通常sg(0)=0,sg(1)=1)）；一个数的sg值就是就是不等于它的后继点的sg值的最小非负数，几个堆的sg值就是每个堆sg值的异或；

譬如有三个堆，它们的后继点的sg值分别为0 1 2、0 1 3、0 1 4，那么sg值就为3^2^2=3，先手赢（此时不考虑分堆）；

现在选手还可以选择分堆操作，那我们就同时要把分堆的情况考虑；

先用vis数组的下标将所有的后继点的sg值存下来，之后在存储所有可分状态分三堆的情况的sg值；

最后遍历vis数组，记录最小的、不属于已计算sg值的最小非负整数，则为当前数字的sg值；

这样可以根据需要打出sg值的表格，找到规律：每一个能被8整除的数，sg值为该数-1；它的前一个数为那个数+1（即前后交换sg值）；其他数为本身；

将每个堆的sg值异或就是最后的结果；

最后

以上就是美丽白猫为你收集整理的HDU 5795 A Simple Nim（Nim游戏博弈+SG函数）的全部内容，希望文章能够帮你解决HDU 5795 A Simple Nim（Nim游戏博弈+SG函数）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。