洛谷2148(SDOI2009) E&D

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

SG函数+找规律。

普通地用SG函数做。

每两堆是一个独立问题。因为虽然有可能一个人在同一组里连续操作2次，但操作一次一定会把一个必败状态改为必胜状态，不会需要连续操作两次。

关键是怎么快速求SG函数。

打表找规律：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int sg[][];

void dfs(int x,int y)

{

    if(sg[x][y]!=-)return;

    int sum=;

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

    {

        dfs(i,x-i);

        sum|=(<<sg[i][x-i]);

    }

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

    {

        dfs(i,y-i);

        sum|=(<<sg[i][y-i]);

    }

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

        if((sum&(<<i))==)

        {

            sg[x][y]=i;sg[y][x]=i;

            return;

        }

}

int main()

{

    memset(sg,-,sizeof sg);

    sg[][]=;

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

    {

        for(int j=;j<=;j++)

        {

            dfs(i,j);

            printf("%3d",sg[i][j]);

        }

        printf("\n");

    }

    return ;

}

然后发现 i 和 j 的规律：

　　SG=1：i % 2 ==1 && j % 2 ==1；

　　SG=2：i % 4 == 1,2 && j % 4 == 1,2；

　　SG=3：i % 8 == 1,2,3,4 && j % 8 == 1,2,3,4；

　　……

所以有了那个log的算法。

仔细一看，那个就是求 i 和 j 的第一个公共0在第几位，所以又有了O(1)的式子。

但是那个O(1)的式子有一个点过不去，是把NO输出成YES，不知何故。

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

const ll N=2e4+;

ll T,n,a[],sum;

ll sg(ll a,ll b)

{

    for(ll i=,tmp=;;i++,tmp<<=)

        if((a-)%tmp<(tmp>>)&&(b-)%tmp<(tmp>>))

            return i;

//    ll k=((a-1)|(b-1));

//    k=((k+1)&(-k-1));

//    return k-1;

}

int main()

{

    scanf("%lld",&T);

    while(T--)

    {

        scanf("%lld",&n);sum=;

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

        {

            scanf("%lld",&a[i&]);

            if(!(i&))sum^=sg(a[],a[]);

        }

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

        else printf("NO\n");

    }

    return ;

}

巴特西

洛谷2148(SDOI2009) E&D

最新文章

热门文章