题解 洛谷 P3185 【[HNOI2007]分裂游戏】

首先可以发现，当所有巧克力豆在最后一个瓶子中时，就无法再操作了，此时为必败状态。

注意到，对于每个瓶子里的巧克力豆，是可以在模\(2\)的意义下去考虑的，因为后手可以模仿先手的操作，所以就将巧克力豆个数转化为了\(0\)或\(1\)。

再考虑分裂的过程，位置为\(i\)的巧克力豆，要分裂到位置\(i\)往后的两个位置，最终会到达\(n\)这个位置，可以把向后转移看作\(Nim\)游戏中取石子的操作。

那么分裂就可以看成\(Nim\)游戏中的一堆石子分成了两堆更小的石子，那么通过这个性质，我们就可以\(O(n^3)\)求出\(SG\)值了。

求方案数和字典序最小方案就直接暴力枚举即可，当进行第一步操作后，留给后手的为必败状态，那么该操作合法。

具体实现就看代码吧。

\(code:\)

#include<bits/stdc++.h>

#define maxn 100

using namespace std;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

int T,n,ans,tot,flag;

int p[maxn],sg[maxn];

bool vis[maxn];

void SG()

{

    for(int i=n-1;i;--i)

    {

        memset(vis,false,sizeof(vis));

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

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

                vis[sg[j]^sg[k]]=true;

        int t=0;

        while(1)

        {

            if(!vis[t])

            {

                sg[i]=t;

                break;

            }

            t++;

        }

    }

}

int main()

{

    read(T);

    while(T--)

    {

        read(n),sg[n]=ans=tot=flag=0;

        for(int i=1;i<=n;++i) read(p[i]);

        SG();

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

            if(p[i]%2)

                ans^=sg[i];

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

        {

            if(!p[i]) continue;

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

            {

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

                {

                    if((ans^sg[i]^sg[j]^sg[k])==0)

                    {

                        tot++;

                        if(!flag)

                        {

                            flag=true;

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

                        }

                    }

                }

            }

        }

        if(!flag) puts("-1 -1 -1");

        printf("%d\n",tot);

    }

    return 0;

}