ZOJ3084_S-Nim

题目的意思是这样的，给定你若干堆石子，每次你可以从任一堆取出某些固定数量的石子，每次取完后必须保证没堆石子的数量不为0，谁无法操作了就算fail。

刚刚开始看题目的时候有点也没有思路，甚至连Sg函数也没有听过。后来学习了一番，说说自己的想法吧。

_________________有关SG函数的由来，性质及其我个人对sg函数的了解见下一篇日志。

这个题目可以这样考虑，由于每次可取的数字是一个给定的集合，我们可以求出所有的数所对应的sg的函数值（我用的是dp，不过好像跟多人喜欢用记忆化搜）。

由于博弈论里面的许多奇奇怪怪的定理，最终我们只要求出每一堆的石子数所对应的sg值的总共异或值ans，如果ans不等于0，那么说明先手有必胜的策略，否则后手有必胜的策略。

另外说明一下，sg函数值对应的是在当前状态能转化到的所有后继状态sg值中的第一个没有出现的非负整数。很神奇吧。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define maxn 10005

 using namespace std;

 bool vis[];

 int a[],sg[maxn],n,m,k,ans;

 void getSG()

 {

     for (int i=; i<maxn; i++)

     {

         memset(vis,false,sizeof vis);

         for (int j=; j<=n && a[j]<=i; j++) vis[sg[i-a[j]]]=true;

         for (int j=; ; j++)

             if (!vis[j])

             {

                 sg[i]=j;

                 break;

             }

     }

 }

 int main()

 {

     while (scanf("%d",&n) && n)

     {

         for (int i=; i<=n; i++) scanf("%d",&a[i]);

         sort(a+,a++n);

         getSG();

         scanf("%d",&m);

         while (m--)

         {

             scanf("%d",&n);

             ans=;

             while (n--) scanf("%d",&k),ans^=sg[k];

             if (ans) printf("W");

                 else printf("L");

         }

         printf("\n");

     }

     return ;

 }

巴特西

ZOJ3084_S-Nim

最新文章

热门文章