BZOJ1188 分裂游戏

题目传送门

Description

有n堆石子,每次可以选三堆(i,j,k),满足i<j<=k,从i中取出一颗石子,在j和k中各放入一颗,发现有先手必胜的策略,问第一步有多少种取法并输出字典序最小的一组

Solution

一道博弈论的题目,可以发现对于每一堆石子,数量不是关键,关键在于奇偶,如果一堆石子有偶数个,则后手可以每次模仿先手在这堆石子上的操作,如果是奇数个则不一定。我们可以通过预处理出每一堆石子的sg函数(sg函数的求解只与n有关,与每堆石子的数量无关),对于一堆数量为偶数个的石子,可以不管,对于奇数个,则先将ans异或上这一堆得sg函数(因为要多取一次),然后对于必胜局面,只要枚举i,j,k,满足ans^sg[i]^sg[j]^sg[k]=0就是第一步可以取的三堆石子。

Code

#include<bits/stdc++.h>
using namespace std;
int sg[100],flag[100],cas,n;
void getsg()
{
    memset(sg,0,sizeof(sg));
    sg[1]=0;
    for (int i=2;i<=21;i++)
    {
        memset(flag,0,sizeof(flag));
        for (int j=1;j<i;j++)
            for (int k=1;k<=j;k++)
                flag[sg[j]^sg[k]]=1;
        for (int j=0;;j++)
        {
            if (!flag[j])
            {
                sg[i]=j;
                break;
            }
        }
    }
}
int main()
{
    scanf("%d",&cas);
    getsg();
    while (cas--)
    {
        int ans=0,tot=0;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            if (x&1) ans^=sg[n-i+1];
        }
        for (int i=1;i<=n;i++)
            for (int j=i+1;j<=n;j++)
                for (int k=j;k<=n;k++)
                {
                    if ((ans^sg[n-i+1]^sg[n-j+1]^sg[n-k+1])==0)
                    {
                        tot++;
                        if (tot==1)
                        {
                            printf("%d %d %d\n",i-1,j-1,k-1);
                        }
                    }
                }
        if (tot==0) printf("-1 -1 -1\n");
        printf("%d\n",tot);
    }
    return 0;
}

2条评论

  1. BZOJ1188 分裂游戏
    avatar

    I wanted to write down a small remark to be able to say thanks to you for those magnificent ideas you are sharing at this site. My time-consuming internet research has finally been honored with useful strategies to talk about with my classmates and friends. I would believe that many of us site visitors actually are very endowed to exist in a really good community with so many perfect professionals with great tips. I feel rather fortunate to have seen the web page and look forward to tons of more thrilling minutes reading here. Thank you once more for everything.

  2. BZOJ1188 分裂游戏
    avatar

    I really wanted to send a comment in order to thank you for these great facts you are giving at this website. My rather long internet research has at the end of the day been recognized with awesome facts and strategies to talk about with my colleagues. I ‘d admit that we website visitors actually are very much lucky to live in a remarkable network with so many marvellous professionals with beneficial tricks. I feel very much blessed to have used the website and look forward to really more pleasurable times reading here. Thank you once more for all the details.

    发表评论