正题

题目链接:https://www.luogu.com.cn/problem/P3235

题目大意

\(T\)组游戏，固定给出\(F\)。每组游戏有\(n\)个石头，每次操作的人可以选择一个数量不少于\(F\)的石堆并把它尽量均摊成\(M\)堆\((M>1)\)。无法操作的人输，求每组游戏是否先手必胜。

解题思路

每个石头之间互不影响，所以求出它们的\(SG\)函数然后异或起来就好了。

设\(sg_i\)表示\(i\)个石头的\(SG\)函数，然后暴力的想法是枚举\(M\)然后求答案，但是这样显然过不了。

发现对于一个\(M\)和石头数量\(n\)，能产生\(n\%M\)个大小\(\lfloor\frac{n}{M}\rfloor+1\)的石头堆和\(M-n\% M\)个大小\(\lfloor\frac{n}{M}\rfloor\)的石头堆。

额，好像就可以整除分块了。每次整除分块出来的一个区间\([l,r]\)，如果\(l=r\)直接计算。

如果\(l\neq r\)的情况好像比较麻烦，其实只需要考虑\(l\)和\(l+1\)就好了，因为如果再往后的奇偶性就会重复。

时间复杂度\(O(n\sqrt n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e5+10;

int T,F,cnt,cl[N],sg[N];

bool v[N];

void add(int x)

{if(!v[x])cl[++cnt]=x;v[x]=1;return;}

void clear(){

    while(cnt)v[cl[cnt]]=0,cnt--;

    return;

}

int main()

{

    scanf("%d%d",&T,&F);

    for(int i=F;i<N;i++){

        for(int l=2,r;l<=i;l=r+1){

            r=i/(i/l);

            int k=i%l,p=i/l,q=p+1;

            if((k&1)&&((l-k)&1))add(sg[p]^sg[q]);

            else if((k&1)&&!((l-k)&1))add(sg[q]);

            else if(!(k&1)&&((l-k)&1))add(sg[p]);

            else add(0);

            if(l!=r){

                l++;k=i%l;

                if((k&1)&&((l-k)&1))add(sg[p]^sg[q]);

                else if((k&1)&&!((l-k)&1))add(sg[q]);

                else if(!(k&1)&&((l-k)&1))add(sg[p]);

                else add(0);

            }

        }

        while(v[sg[i]])sg[i]++;

        clear();

    }

    while(T--){

        int n,ans=0;

        scanf("%d",&n);

        while(n--){

            int x;scanf("%d",&x);

            ans^=sg[x];

        }

        if(ans)printf("1 ");

        else printf("0 ");

    }

    return 0;

}

巴特西

P3235-[HNOI2014]江南乐【整除分块,SG函数】

正题

题目大意

解题思路

code

最新文章

热门文章