hdu 3032 Nim or not Nim? （sg函数打表找规律）

题意:有N堆石子，每堆有s[i]个，Alice和Bob两人轮流取石子，可以从一堆中取任意多的石子，也可以把一堆石子分成两小堆

Alice先取，问谁能获胜

思路：首先观察这道题的数据范围 1 ≤ N ≤ 10^6, 1 ≤ 【Si】 ≤ 2^31 - 1，很明显数据量太大，所以只能通过打表找规律

打表后发现，如果x%4==0 sg[x]=x-1 ;如果 x%4==3 sg[x]=x+1;如果其他情况 sg[x]=x;

代码：

打表代码：

#include <iostream>

#include <cstring>

using namespace std;

int sg[];

int get(int n)

{

    if(n<) return ;

    if(sg[n]!=-) return sg[n];

    bool visit[];

    memset(visit,false,sizeof(visit));

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

      visit[get(i)^get(n-i)]=true;

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

    {

        visit[get(n-i)]=true;

    }

    int k;

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

    {

        if(visit[i]==false)

        {

           return sg[n]=i;

        }

    }

}

int main()

{

    memset(sg,-,sizeof(sg));

    sg[]=;sg[]=;

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

    {

        get(i);

    }

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

    cout<<i<<"  "<<sg[i]<<endl;

    return ;

}

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        int n,x,ans=;

        cin>>n;

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

        {

            scanf("%d",&x);

            if(x%==)

             ans=ans^(x-);

            else if(x%==)

             ans=ans^(x+);

            else

             ans=ans^x;

        }

        if(ans)

        cout<<"Alice"<<endl;

        else

        cout<<"Bob"<<endl;

    }

    return ;

}

巴特西

hdu 3032 Nim or not Nim? （sg函数打表找规律）

最新文章

热门文章