P3235 [HNOI2014]江南乐 题解

· · 题解

一开始我以为是用整除分块来求解 SG 函数，后来参考同校犇犇的代码更换了思路。

首先这道题是一个公平博弈游戏，考虑使用 SG 函数。

SG 函数的性质是多堆石子的 SG 函数值相当于每一堆石子的 SG 函数值异或和。

在整体使用 SG 函数的性质

我们在整体上使用 SG 函数的性质。

我们单独求出每一个石子堆的 SG 函数值，最后求异或和即可。

我们可以写记忆化搜索，因为有用的 SG 函数项不多，这样节省时间。

在内部使用 SG 函数的性质

内部也是一个道理。

问题中的操作将石子分成了很多石子，不好处理。

但是，种类只有两类，同样的石子堆的 SG 函数值肯定相同。

分成多个石子堆后，注意到有很多相同的，根据 SG 函数的性质，可以异或抵消。

所以其实相同的石子堆 SG 函数值异或之后抵消了。

对于操作后产生的每种石子堆，我们可以根据石子数量奇偶性质思考讨论。

如果是奇数，那最后还有一个没抵消。

如果是偶数，那么全部抵消掉了。

也就是看起来很多堆石子，其实到头来，每个种类最多一个最少没有。

一个小优化

这时候还不够，需要剪枝。

注意到求解 SG_x 时，我们枚举的分开的量 y 如果满足 \lceil\frac x y\rceil<F 时，分成的石子堆石子数一定小于 F。

后面的 SG 函数值肯定都是 0，没必要再枚举。

于是这道题就写完了。

代码

我的代码是洛谷目前最优解。

#include<bits/stdc++.h>
#define LL int
LL T,F,n,x,sum,sg[100005];
using namespace std;
// 快读
inline LL dfs(LL x)
{
    if(x<F)return 0;
    if(~sg[x])return sg[x];//记忆化
    bool vis[105];
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=x;i++)//枚举分开操作所需的量
    {
        LL t=0;
        if((x+i-1)/i<F)//剪枝
        {
            vis[0]=1;
            break;
        }
        if((x%i)&1)t^=dfs(x/i+1);//奇偶讨论
        if((i-x%i)&1)t^=dfs(x/i);
        vis[t]=1;
    }
    for(int i=0;i<=100;i++)//求mex
    {
        if(!vis[i])return sg[x]=i;
    }
}
int main()
{
    memset(sg,-1,sizeof(sg));
    T=read(),F=read();
    while(T--)
    {
        sum=0;
        n=read();
        for(int i=1;i<=n;i++)
        {
            x=read();
            sum^=dfs(x);//求解x的SG函数值
        }
        if(sum)putchar('1');//根据SG函数值输出
        else putchar('0');
        putchar(' ');
    }
}

唉？我怎么私了？

由于之前的做法被杀了，现在加个优化。

考虑到整除后的值的种类数量是 \mathcal O(\sqrt n)，我们考虑整除分块。

但是一个块内整除的值时一样的，模之后的值却未必，我们发现模之后的值好像只会影响下面这一段：

        if((x%L)&1)t^=dfs(x/L+1);
        if((L-x%L)&1)t^=dfs(x/L);

我们思考一下，显然，如果整除分块得到的区间 [L,R] 有 L=R 我们直接做 i=L 就行了，否则我们只要做 i=L 和 i=L+1 就行，因为我们观察上面代码，我们只关心模之后的值的奇偶性。

然后我又开开心心过题了。

#include<stdio.h>
#include<bits/stdc++.h>
int T,F,n,x,sum,sg[200005];
using namespace std;
//快读
inline int dfs(int x)
{
    if(x<F)return 0;
    if(~sg[x])return sg[x];
    bool vis[60];
    memset(vis,0,sizeof(vis));
    for(int L=2,R;L<=x&&R+1<=x;L=R+1)
    {

        R=x/(x/L);
        if(ceil(x*1.0/L)<F)
        {
            vis[0]=1;
            break;
        }
        int t=0;
        if((x%L)&1)t^=dfs(x/L+1);
        if((L-x%L)&1)t^=dfs(x/L);
        vis[t]=1;
        if(L!=R)
        {
            int t=0;
            if((x%(L+1))&1)t^=dfs(x/(L+1)+1);
            if(((L+1)-x%(L+1))&1)t^=dfs(x/(L+1));
            vis[t]=1;
        }

    }
    for(int i=0;;i++)
    {
        if(!vis[i])return sg[x]=i;
    }
}
int main()
{
    memset(sg,-1,sizeof(sg));
    fasI::Rd(T),fasI::Rd(F);
    while(T--)
    {
        sum=0;
        fasI::Rd(n);
        for(int i=1;i<=n;i++)
        {
            fasI::Rd(x);
            sum^=dfs(x);
        }
        putchar('0'+(sum>0));
        putchar(' ');
    }
}