重點就是找sg函數的值，然后異或 為0 必敗否則 必勝。
感謝大佬提供的模板 可用于 打表算SG
dfs 暴力打表
例1
n堆石子，每次不拿超過一半的石子。
找規(guī)律可知 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;
}
每次取 2的冪 打表找規(guī)律 發(fā)現是1、2、0 的循環(huán)
代碼改的例二的
#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;
}
