博弈论SG函数入坑

重点就是找sg函数的值，然后异或为0 必败否则必胜。
感谢大佬提供的模板可用于打表算SG
dfs 暴力打表

例1
n堆石子，每次不拿超过一半的石子。
找规律可知 n为偶数 SG(n)=(n)/2;奇数 SG(n)= SG(n/2)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e3;
ll SG(ll x)
{
    return x%2==0?x/2:SG(x/2);
}
int main()
{
    int t;cin>>t;
    while(t--){
    int n;cin>>n;
    ll a;
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        ll sg=SG(a);
        ans^=sg;
    }
    if(ans==0)
    {
        cout<<"NO"<<endl;
    }else cout<<"YES"<<endl;
    }
    return 0;
}

例2 杭电 1848
3堆石子，每次取斐波拉切数。因为数据都不打就直接打表了

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e3+5;
int sg[N];int f[N];int s[N];
void SG(int n)
{
    for(int i=1;i<=n;i++)
{
        memset(s,0,sizeof(s));
        for(int j=1;f[j]<=i;j++)
        {
            s[sg[i-f[j]]]=1;
          //  cout<<i<<" "<<i-f[j]<<" "<<11<<endl;
        }
       // cout<<s[0]<<" "<<i<<endl;
        for(int k=0;k<=i;k++)
        {
            if(s[k]==0)
            {
                sg[i]=k;
              //  cout<<i<<" "<<k<<endl;
                break;
            }
        }
    }
}
//1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
int main()
{
    f[1]=1,f[2]=2,f[3]=3,f[4]=5,f[5]=8,f[6]=13,f[7]=21,f[8]=34,f[9]=55,f[10]=89,f[11]=144
    ,f[12]=233,f[13]=377,f[14]=610,f[15]=987,f[16]=10000;
    int a,b,c;
    SG(1000);
    while(cin>>a>>b>>c)
    {
        int ans=0;
        if(a==0&&b==0&&c==0)
            break;
        ans=(sg[a]^sg[b]^sg[c]);
          if(ans==0)
    {
        cout<<"Nacci"<<endl;
    }else cout<<"Fibo"<<endl;
    }


    return 0;
}

例三 hdu1847

每次取 2的幂打表找规律发现是1、2、0 的循环
代码改的例二的

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e3+5;
int sg[N];int f[N];int s[N];
void SG(int n)
{
    for(int i=1;i<=n;i++)
{
        memset(s,0,sizeof(s));
        for(int j=1;f[j]<=i;j++)
        {
            s[sg[i-f[j]]]=1;
          //  cout<<i<<" "<<i-f[j]<<" "<<11<<endl;
        }
       // cout<<s[0]<<" "<<i<<endl;
        for(int k=0;k<=i;k++)
        {
            if(s[k]==0)
            {
                sg[i]=k;
              //  cout<<i<<" "<<k<<endl;
                break;
            }
        }
    }
}
//1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
int main()
{
    f[1]=1,f[2]=2,f[3]=4,f[4]=8,f[5]=16,f[6]=32,f[7]=64,f[8]=128,f[9]=256,f[10]=512,f[11]=1024;


//    for(int i=2;i<11;i++)
//    {
//        f[i]=f[i-1]*2;
//        cout<<f[i]<<endl;
//    }
    int a,b,c;
    SG(1000);
    while(cin>>a)
    {

          if(sg[a]!=0)
    {
        cout<<"Kiki"<<endl;
    }else cout<<"Cici"<<endl;
    }


    return 0;
}

例四 hdu1850
题意输出先手第一次取的方式多少种

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e2+5;
int num[N];
int main()
{

    int a,b,c;
while(cin>>a&&a)
{


int ans=0;
for(int i=0;i<a;i++)
{


    cin>>num[i];
    ans^=num[i];
    }
    int ta=ans;
    int x=0;
    if(ans>0)
    {

    for(int i=0;i<a;i++)
    {
        ta^=num[i];
        if(ta<=num[i])
        {
            x++;
        }
          ta^=num[i];
    }
    cout<<x<<endl;
    }
 else
   cout<<0<<endl;
}


    return 0;
}

例五

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e3+5;
int num[N];
int main()
{

    int a,b,c;
while(cin>>a&&a)
{


int ans=0;
for(int i=0;i<a;i++)
{


    cin>>num[i];
    ans^=num[i];
    }

    if(ans>0)
    {
    cout<<"Rabbit Win!"<<endl;
    }
 else
   cout<<"Grass Win!"<<endl;
}


    return 0;
}

例六
普通多堆取石子

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e3+5;
int num[N];
int main()
{

    int a,b,c;
while(cin>>a)
{


int ans=0;
for(int i=0;i<a;i++)
{


    cin>>b;
    ans^=b;
    }

    if(ans==0)
    {
    cout<<"No"<<endl;
    }
 else
   cout<<"Yes"<<endl;
}


    return 0;
}

例七
 大佬的解析



#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e3+5;
int num[N];
int con(int x)
{
    int y=x;
    int c=0;
    int tc=0;
    while(y)
    {
      c+=(y&1);
      y=y>>1;
    }
    return c;
}
int main()
{

    int a,b,c;
    int t;cin>>t;
for(int j=1;j<=t;j++)
{
cin>>a;

int ans=a;
for(int i=0;i<a;i++)
{


    cin>>b;
    ans+=con(b);
 //  cout<<con(b)<<endl;
    }
cout<<"Case "<<j<<": ";
    if(ans%2==0)
    {
    cout<<"No"<<endl;
    }
 else
   cout<<"Yes"<<endl;
}
    return 0;
}

例八

博弈论SG函数入坑

推荐阅读更多精彩内容