P3185[HNOI2007]分裂游戏（题解）

· · 题解

Problem.

起始状态：第i个瓶子里装了a_i个巧克力豆。
结束状态：前n-1个瓶子都空了，只有第n个瓶子放了巧克力豆。
状态转移：选i<j\le k，然后在第i个瓶子里取走一颗，在第j和第k个瓶子里加上一颗。

Solution.

显然，这是个博弈问题。

看到博弈问题就想到SG函数，因为笔者只会这种博弈。

这是个Multi-SG游戏。
但是可惜啊，Multi-SG并不是什么有什么套路的题目。

我们突然发现，1<n\le21。
所以我们可以考虑dp。
dp转移时可以直接暴力枚举i,j,k。
复杂度是O(N^3)能过。

然后直接套用SG函数就好了。

Coding.

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n,ans,t,sg[N],vis[N],a[N];
inline void work(int ans)
{
    int tot=0,ii=-1,jj,kk;
    for(int i=n;i>=1;i--)
        for(int j=i-1;j>=1;j--)
            for(int k=j;k>=1;k--)
                if((ans^sg[i]^sg[j]^sg[k])==0)
                {
                    tot++;
                    if(ii==-1) ii=n-i,jj=n-j,kk=n-k;
                }
    printf("%d %d %d\n%d\n",ii,jj,kk,tot);
}
int main()
{
    sg[1]=0;//预处理
    for(int i=2;i<=N-4;i++)
        for(int j=1;j<=i;j++)
            for(int k=j;k<i;k++)//暴力枚举i,j,k
            {
                vis[sg[j]^sg[k]]=i;//SG函数的转移
                for(sg[i]=0;vis[sg[i]]==i;sg[i]++);
            }
    for(scanf("%d",&t),ans=0;t--;ans=0)
    {
        scanf("%d",&n);
        for(int i=n;i>=1;i--) scanf("%d",a+i);
        for(int i=n;i>=1;i--) if(a[i]&1) ans^=sg[i];//这里是一个优化，每个数可以直接变成对二取模后的值。
        if(!ans) puts("-1 -1 -1\n0");else work(ans);
    }
    return 0;
}

完结散花，不要脸求赞