洛谷 P3235 [HNOI2014]江南乐 解题报告
阅读原文时间:2024年06月12日阅读:1

P3235 [HNOI2014]江南乐

两人进行 T 轮游戏,给定参数 F ,每轮给出 N 堆石子,先手和后手轮流选择石子数大于等于 F 的一堆,将其分成任意(大于1)堆,使得这些堆中石子数最多的和最少的相差不超过1(即尽量均分)。求先手和后手谁必胜。

输入第一行包含两个正整数T和F,分别表示游戏组数与给定的数。

接下来T行,每行第一个数N表示该组游戏初始状态下有多少堆石子。之后N个正整数,表示这N堆石子分别有多少个。

输出一行,包含T个用空格隔开的0或1的数,其中0代表此时小A(后手)会胜利,而1代表小A的对手(先手)会胜利。


预处理每个单一游戏的\(SG\)值

小于\(F\)的置\(0\)必败

大于\(F\)的枚举拆分的堆数,把分开的用\(SG\)定理求一个异或和。

发现可以用乘除分块优化,对奇偶性相同的堆数当\(\lfloor\frac{n}{l}\rfloor\)一样时,答案一样。

预处理的复杂度\(O(n\sqrt n)\)

注意特判\(SG_1=0\)

直接\(SG\)定理回答询问就可以了。


Code:

#include <cstdio>
const int N=1e5+1;
int SG[N],T,F,n,is[N];
int hxor(int x,int k)
{
    if(k&1) return x;
    return 0;
}
int main()
{
    scanf("%d%d",&T,&F);
    for(int i=F;i<N;i++)
    {
        for(int l=1,r;l<=i;l=r+1)
        {
            r=i/(i/l);
            is[hxor(SG[i/l],l-i%l)^hxor(SG[i/l+1],i%l)]=i;
            ++l;
            if(l<=r&&l<=i) is[hxor(SG[i/l],l-i%l)^hxor(SG[i/l+1],i%l)]=i;
        }
        for(int j=0;is[j]==i;j++) SG[i]=j+1;
    }
    SG[1]=0;
    while(T--)
    {
        scanf("%d",&n);
        int sg=0;
        for(int x,i=1;i<=n;i++) scanf("%d",&x),sg^=SG[x];
        printf("%d ",sg>0);
    }
    return 0;
}

2018.12.19

手机扫一扫

移动阅读更方便

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

你可能感兴趣的文章