hdu 3032Nim or not Nim?<sg函数>

链接:http://acm.hdu.edu.cn/showproblem.php?pid=3032

题意:Alice和Bob轮流取N堆石子，每堆S[i]个，Alice先，每一次可以从任意一堆中拿走任意个石子，也可以将一堆石子分为两个小堆。先拿完者获胜。

数据范围: (1 ≤ N ≤ 10^6, 1 ≤ S[i] ≤ 2^31 - 1).

思路: 此题为博弈中的—取走-分割游戏（这种游戏允许取走某些东西，然后将原来的一个游戏分成若干个相同的游戏）

由于数据范围,不能直接求sg值只能打表找规律;

有SJ 定理：

对于任意的一个 Anti-SG 游戏，如果我们规定当局面中所有单一游戏的 SG 值为 0 时游戏结束，则先手必胜当且仅当以下两个条件满足任意一个：

(1)游戏的 SG 函数不为 0，且游戏中某个单一游戏的 SG 函数大于1。

(2)游戏的 SG 函数为 0，且游戏中没有单一游戏的 SG 函数大于 1。

View Code

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <string>
 6 #include <stdlib.h>
 7 #include <algorithm>
 8 using namespace std;
 9 typedef long long LL;
10 const LL Mod= 1e9+7;
11 int T, N, x;
12 int sg[10000];
13 int mex(int x) // 求sg函数 
14 {
15     if( sg[x]>0 )return sg[x];
16     bool re[10000]={0};
17     for( int i=0; i<x; ++ i ){
18         re[mex(i)]=1;
19         if( x-i>0&&i>0 )re[mex(i)^mex(x-i)]=1;
20     }
21     int i=0;
22     while( re[i] )i++;
23     return sg[x]=i;
24 }
25 
26 int main( )
27 {
28 /*    memset( sg, -1, sizeof sg );
29     sg[0]=0;
30     for( int i=0; i<100; ++ i )
31         printf( "%d\n", mex( i ) );
32 */
33     scanf( "%d", &T );
34     while( T-- ){
35         scanf( "%d", &N );
36         int ans=0;
37         for( int i=0; i<N; ++ i ){
38             scanf( "%d", &x );
39             if( x%4==0 )ans^=(x-1);
40             else if( x%4==3 )ans^=(x+1); 
41             else ans^=x;
42         }
43         if( ans!=0 )puts( "Alice" );
44         else puts( "Bob" ); 
45     }
46     return 0;
47 }