洛谷P2575高手过招——SG函数初试

题目：https://www.luogu.org/problemnew/show/P2575

第一次用SG函数解决问题，有许多不熟练的地方；

试图按自己的理解写一个dfs，结果错了(连题都没读对，以为是像跳棋一样跳)，这样的话用dfs从左往右推就不行了呢；

附上自己的错误尝试：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int maxn=;

int T,n,p,ans,g[];

int dfs(int x)

{

    if(g[x])return g[x]-;

    int ret=;

    for(int i=;i>=;i--)

        if(x&(<<i))

        {

            if((x&(<<(i-)))&&(x&(<<(i-)))==&&i->=)

            {

                int k=x-(<<i)+(<<(i-));

//                if(!dfs(k))

//                {

//                    g[x]=2;

//                    return 1;

//                }

                ret^=dfs(k);

            }

            if((x&(<<(i-)))==&&i->=)

            {

                int k=x-(<<i)+(<<(i-));

//                if(!dfs(k))

//                {

//                    g[x]=2;

//                    return 1;

//                }

                ret^=dfs(k);

            }

        }

    if(!ret)g[x]=;

    else g[x]=;

//    printf("%d %d\n",x,g[x]-1);

    return g[x]-;

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        memset(g,,sizeof g);

        ans=;

        scanf("%d",&n);

        for(int i=,m;i<=n;i++)

        {

            p=;

            scanf("%d",&m);

            for(int j=,x;j<=m;j++)

            {

                scanf("%d",&x);

                x--;

                p|=(<<(-x));

            }

//            if(ans)continue;

//            if(dfs(p)==0)ans=1;

            ans^=dfs(p);

        }

        if(ans)printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

囧

下面是正解，也就是个SG函数的模板；

状压一下每一行，先预处理出来所有状态的SG函数值(注意vis[里面是SG函数值])，然后每次询问异或一下就可以了，还挺简明的。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int T,n,m,ans,sg[<<];

bool vis[];

void init(int x)

{

    memset(vis,,sizeof vis);

    int w=;

    for(int i=;i<=;i++)//从小到大对应从右往左

    {

        int t=(<<(i-));

        if(x&t)

        {

            if(i>&&(x&(t>>))==)

                vis[sg[x-t+(t>>)]]=;

//            if(i>2&&(x&(t>>1))&&(x&(t>>2))==0)

//                vis[sg[x-t+(t>>2)]]=1;//读错题

            if((x&(t>>))&&w)

                vis[sg[x-t+(<<(w-))]]=;

        }

        else w=i;

    }

    int k=;//求mex

    while(vis[k])k++;

    sg[x]=k;

}

int main()

{

    scanf("%d",&T);

    for(int i=;i<=(<<)-;i++)init(i);

    while(T--)

    {

        ans=;//!

        scanf("%d",&n);

        for(int i=;i<=n;i++)

        {

            scanf("%d",&m);

            int p=;

            for(int j=,x;j<=m;j++)

            {

                scanf("%d",&x);

                p|=(<<(-x));

            }

            ans^=sg[p];

        }

        if(ans)printf("YES\n");

        else printf("NO\n");

    }

    return ;

}