uva 1378 - A Funny Stone Game sg博弈-白红宇

uva 1378 - A Funny Stone Game sg博弈

阅读量：7123 次

发布时间：2019-06-28

本文共 1345 字，大约阅读时间需要 4 分钟。

题意：David 玩一个石子游戏。

游戏中，有n堆石子,被编号为0..n-1。两名玩家轮流取石子。每一轮游戏。每名玩家选取3堆石子i,j,k(i<j,j<=k,且至少有一枚石子在第i堆石子中)。从i中取出一枚石子，并向j。k中各放入一枚石子(假设j=k则向k中放入2颗石子)。

最先不能取石子的人输。石子堆的个数不会超过23。每一堆石子不超过1000个。

解法：看上去是将石子都往右移，直到全部都到了n-1堆不能移为止。

首先是考虑每堆石子事实上是独立的一个子游戏，堆与堆之间不相互影响。

然后就是个数是偶数的对不会影响必胜必败态，必败态无法通过移动偶数堆得石子来扭转局面。由于必胜者仅仅需对称操作就可以。所以每堆石子就成了01的状态，sg值仅仅是跟位置有关系了。预处理出每一个位置的sg值就可以。计算第一个可行步骤时候。暴力推断ijk就可以。

代码：

/******************************************************* @author:xiefubao*******************************************************/#pragma comment(linker, "/STACK:102400000,102400000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 //freopen ("in.txt" , "r" , stdin);using namespace std;#define eps 1e-8#define zero(_) (_<=eps)const double pi=acos(-1.0);typedef long long LL;const int Max=100010;const LL INF=0x3FFFFFFF;int sg[100];bool rem[100];int n;void init(){ sg[0]=0; for(int i=1; i<=25; i++) { memset(rem,0,sizeof rem); for(int j=i-1; j>=0; j--) for(int k=j; k>=0; k--) { rem[sg[j]^sg[k]]=1; } int t=0; while(rem[t]) t++; sg[i]=t; }}bool help[100];//0 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42int main(){ init(); int kk=1; while(cin>>n&&n) { memset(help,0,sizeof help); int ans=0; for(int i=0; i

转载地址：http://hcael.baihongyu.com/

你可能感兴趣的文章