题解 P3179 【[HAOI2015]数组游戏】

· · 题解

折腾一晚上终于搞出来了

Step1

首先是翻棋子问题的套路，每个棋子可以作为单个游戏，整个游戏就是所有白棋子的SG异或和，可以想到一个暴力算SG的方法，有50分

Step2

进一步优化就是可以打表发现\frac{n}{i}下取整的值相同的棋子SG值相同（i表示位置），于是有一个分块想法

先处理q[i]=k表示从左到右第i块的右端点为k，然后我们枚举x=q[i]，同时记录res为异或和，cnt表示有多少不同的SG值，于是我们对于区间[L,R]（[L,R]的\frac{n}{i}值相等），我们需要由下面的状态取mex转移

\{0,SG([2L,2R]),SG([2L,2R]\ xor\ SG[3L,3R]....)\}

于是我们接下来对[l,r]分块（[l,r]表示[L,R]的[l,r]倍在同一个大块里面），用这个的奇偶性来维护SG异或的前缀和

最后一个优化是存储x的值，块x表示右端点x，\frac{n}{i}，那么如果x在1到根号n只之内直接存，否则存\frac{n}{i}，这样子就能优化空间到根号n了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
const int N=500000;
int T,n,W,c[N],a[N],b[N];
int q[N],nn,tag[N],tot;
void Pre()
{
    nn=sqrt(n);tot=0;
    for(int l=1,r;l<=n;l=r+1)
        r=n/(n/l),q[++tot]=r;
    for(int u=tot;u;u--)
    {
        int x=q[u],res=0,cnt=0;
        for(int l=2*x,r;l<=n;l=r+x)
        {
            r=n/(n/l)/x*x;
            int z=r>nn?b[n/r]:a[r];
            c[++cnt]=res^z;tag[c[cnt]]=1;
            if(((r-l)/x+1)&1) res^=z;
        }
        res=1;while(tag[res]) res++;
        x>nn?b[n/x]=res:a[x]=res;
        for(int i=1;i<=cnt;i++) tag[c[i]]=0;
    }
}
void work()
{
    cin>>W;int res=0;
    for(int i=1;i<=W;i++)
    {
        int x;cin>>x;
        res^=x>nn?b[n/x]:a[x];
    }
    res?puts("Yes"):puts("No");
}
int main()
{
    cin>>n>>T;Pre();
    while(T--) work();
}

打个小广告：博弈总结

管理员请重新审核之前有个地方有误o=o