uva 1378 - A Funny Stone Game sg博弈 - c++编程基础

题意：David 玩一个石子游戏。游戏中，有n堆石子,被编号为0..n-1。两名玩家轮流取石子。每一轮游戏，每名玩家选取3堆石子i,j,k(i

解法：看上去是将石子都往右移，直到所有都到了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 42 int main() { init(); int kk=1; while(cin>>n&&n) { memset(help,0,sizeof help); int ans=0; for(int i=0; i