S-Nim

http://acm.hdu.edu.cn/showproblem.php?pid=1536

SG经典题，不多说

    // File Name: hdu1536.cpp

// Author: bo_jwolf

// Created Time: 2013年09月30日 星期一 18:23:53



#include<vector>

#include<list>

#include<map>

#include<set>

#include<deque>

#include<stack>

#include<bitset>

#include<algorithm>

#include<functional>

#include<numeric>

#include<utility>

#include<sstream>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<ctime>



using namespace std;



const int N = 105 ;

const int MAXN = 10100;

bool vis[MAXN];

int sg[MAXN];

int si[ MAXN ] , n ;

int Getsg( int N )

{//printf( " n = %dn",n );

    int hash[105] = {0};

    for( int i = 0; i < n && si[i] <= N; ++i )

    {

         if( sg[N-si[i]] == -1 )

             sg[N-si[i]] = Getsg( N - si[i] );

         hash[sg[N-si[i]]] = 1;

     }

     for( int i = 0; ; i++ )

          if( !hash[i] )

              return i;

}



int main(){

    int temp , ans , m  ; 

    while( scanf( "%d" , &n ) != EOF && n ){

        for( int i = 0 ; i < n ; ++i ){

            scanf( "%d" , &si[ i ] ) ;

        }

        memset( sg , -1 , sizeof( sg ) ) ;

        sort( si , si + n ) ;

        int Case ;

        scanf( "%d" , &Case ) ;

        while( Case-- ){

            scanf( "%d" , &m ) ;

            ans = 0;

            for( int i = 0 ; i < m ; ++i ){

                scanf( "%d" , &temp ) ;

                ans ^= Getsg( temp ) ;

            }

            if( ans ==  0 ) cout << "L"  ;

            else cout << "W"  ;

        }

        cout << endl ;

    }

return 0;

}
  

S-Nim