M_sea

洛谷3185 [HNOI2007]分裂游戏
LuoguBZOJ分析很神仙的一道博弈论题。首先发现必败态一定是所有的豆子都装在最后一个瓶子里。然后,每次的转移一...
扫描右侧二维码阅读全文
19
2019/02

洛谷3185 [HNOI2007]分裂游戏

Luogu

BZOJ

分析

很神仙的一道博弈论题。

首先发现必败态一定是所有的豆子都装在最后一个瓶子里。

然后,每次的转移一定是拿出一颗豆子,放入两颗豆子。

于是我们可以把每颗豆子看做一个单独的游戏了。

继续观察发现,如果有两个在同一个瓶子里的豆子,那么可以直接忽略掉这两个,因为后手可以模仿先手。于是所有位置的豆子等价于$\text{这个位置上的豆子数}\%2$。

现在问题成功简化为,有一颗在$i$位置的豆子,求胜负情况。

显然可以预处理 $SG$ 函数来做。至于如何找答案,利用一些性质即可。

具体实现和细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=21+10;

int tim=0;
int a[N],sg[N],vis[N];

int main() {
    int T=read();
    while (T--) {
        int n=read();
        for (re int i=1;i<=n;++i) a[i]=read();
        /*求SG函数*/
        memset(sg,0,sizeof(sg));
        for (re int i=n-1;i>=1;--i) {
            ++tim;
            for (re int j=i+1;j<=n;++j)
                for (re int k=j;k<=n;++k)
                    vis[sg[j]^sg[k]]=tim;
            for (re int j=0;;++j)
                if (vis[j]!=tim) { sg[i]=j; break; }
        }
        /*求答案*/
        int cnt=0,A=0,B=0,C=0,s=0;
        for (re int i=1;i<=n;++i)
            if (a[i]&1) s^=sg[i];
        for (re int i=1;i<=n;++i) {
            if (!a[i]) continue;
            for (re int j=i+1;j<=n;++j)
                for (re int k=j;k<=n;++k)
                    if ((s^sg[i]^sg[j]^sg[k])==0) {
                        if (!cnt) A=i,B=j,C=k;
                        ++cnt;
                    }
        }
        printf("%d %d %d\n%d\n",A-1,B-1,C-1,cnt);
    }
    return 0;
}
最后修改:2019 年 02 月 19 日 05 : 28 PM

发表评论