2011-12-24 18:56:53

地址：

题意：有一个集合有S个数。玩N次取石子游戏，每次只能取S集合里的数个石子。求判先手胜负。

mark：SG函数，NIM博弈标准题。先求SG值打表，之后一串异或就OK了。复杂度是100w。

代码：

# include 
     
       # include 
      
        int sg[10010] ; int k, knum[110] ; int flag[110] ; int met(int n) {
   int i, ans = 0 ;     memset (flag, 0, sizeof(flag)) ; for (i = 0 ; i < k ; i++) if (n - knum[i] >= 0)             flag[sg[n - knum[i]]] = 1 ; for (i = 0 ; i <= 101 ; i++) if (flag[i] == 0) return i ; } void Sprague_Grundy() {
   int i ; for (i = 1 ; i <= 10000 ; i++)         sg[i] = met(i) ; } int main () {
   int i, n, l, num, ans ; while (~scanf ("%d", &k) && k)     {
   for (i = 0 ; i < k ; i++)             scanf ("%d", &knum[i]) ;         Sprague_Grundy() ;         scanf ("%d", &n) ; while (n--)         {
               ans = 0 ;             scanf ("%d", &l) ; while (l--)             {
                   scanf ("%d", &num) ;                 ans ^= sg[num] ;             }             printf (ans == 0 ? "L" : "W") ;         }         printf ("\n") ;     } return 0 ; }