bzoj 3576: [Hnoi2014]江南乐【博弈论】
阅读原文时间:2024年09月04日阅读:1

这个东西卡常……预处理的时候要先把i%j,i/j都用变量表示,还要把%2变成&1……

首先每一堆都是不相关子游戏,所以对于每一堆求sg即可

考虑暴力枚举石子数i,分割块数j,分解成子问题求xor和(其实就是根据i/j,i/j+1的个数的奇偶性xor一下即可),然后对sg[i]暴力mex,这样是n^2的

考虑优化,注意到一共只有根号级别的i/j,所以根据这个分块,上面的xor和是跟距个数奇偶性,而同样i/j的奇偶性只有两种(因为总个数相同),也就是i%j和i%(j+2),j-(i%j)和(j+2)-i%(j+2)的奇偶性是一样的

然后对每个询问求sg的xor和即可

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int T,f,n,m=100000,sg[N],v[N],ti,ans;
int read()
{
    int r=0,f=1;
    char p=getchar();
    while(p>'9'||p<'0')
    {
        if(p=='-')
            f=-1;
        p=getchar();
    }
    while(p>='0'&&p<='9')
    {
        r=r*10+p-48;
        p=getchar();
    }
    return r*f;
}
int main()
{
    T=read(),f=read();
    for(int i=f;i<=m;i++)
    {
        ti++;
        for(int j=2,la,nw,x,y;j<=i;j=la+1)
        {
            nw=0,x=i%j,y=i/j,la=min(i,i/y);
            if(x&1)
                nw^=sg[y+1];
            if((j-x)&1)
                nw^=sg[y];
            v[nw]=ti;
            if(la+1>j+1)
            {
                nw=0,x=i%(j+1),y=i/(j+1);
                if(x&1)
                    nw^=sg[y+1];
                if(((j+1)-x)&1)
                    nw^=sg[y];
                v[nw]=ti;
            }
        }
        for(int j=0;j<=m;j++)
            if(v[j]!=ti)
            {
                sg[i]=j;
                break;
            }
    }
    while(T--)
    {
        n=read(),ans=0;
        for(int i=1;i<=n;i++)
            ans^=sg[read()];
        ans?printf("1 "):printf("0 ");
    }
    return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章