UVALive 3668 A Funny Stone Game

题目大意为给定n堆石子，每次的操作是选择三个数i<j<=k，从i中拿一枚石子，在j和k中分别放入一枚石子。不能操作者输。求先手是否能赢，若可以，则输出字典序最小的第一步操作。

思路是把在每个位置上的每颗石子当成一个游戏。

用SG[i]表示在第i堆中的一颗石子的sg函数。

则SG[i]=mex(SG[j] ^ SG[k])。

然后异或求游戏的和即可。

为找到字典序最小的第一步操作，我们枚举第一步操作，然后求游戏的和即可。

代码如下：

 #include"cstdio"

 #include"iostream"

 #include"cstring"

 #include"algorithm"

 #include"cstdlib"

 #include"vector"

 #include"set"

 #include"map"

 #include"cmath"

 using namespace std;

 typedef long long LL;

 const LL MAXN=;

 int n;

 int f[MAXN];

 int sg(int x)

 {

     if(x==n) return ;

     if(f[x]!=-) return f[x];

     int vis[];

     memset(vis,,sizeof(vis));

     for(int i=x+;i<=n;i++)

         for(int j=i;j<=n;j++)

             vis[sg(i)^sg(j)]=;

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

         if(!vis[i])

             return f[x]=i;

     return ;

 }

 int d[MAXN];

 int cal()

 {

     memset(f,-,sizeof(f));

     int ans=;

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

         if(d[i]%!=)

             ans ^= sg(i);

     return ans;

 }

 int main()

 {

 #ifdef LOCAL

     freopen("in.txt","r",stdin);

     // freopen("out.txt","w",stdout);

 #endif

     int t=;

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

     {

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

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

         int i,j,k;

         bool ok=false;

         for(i=;!ok && i<=n;i++)

             for(j=i+;!ok && j<=n;j++)

                 for(k=j;!ok && k<=n;k++)

                     if(d[i]>)

                     {

                         d[i]--;

                         d[j]++;

                         d[k]++;

                         if(cal()==)

                             ok=true;

                         d[i]++;

                         d[j]--;

                         d[k]--;

                     }

         printf("Game %d: ",++t);

         if(ok) printf("%d %d %d\n",i-,j-,k-);

         else printf("-1 -1 -1\n");

     }

     return ;

 }

巴特西

UVALive 3668 A Funny Stone Game

最新文章

热门文章