巴什博弈
最基础的博弈游戏。
有一堆石子，共计n颗，规定二人每次拿1~m颗石头，先拿完者胜，求解先手是否能赢。
结论：如果n%（m+1）==0 先手必败 。
n%（m+1）！=0 为先手必胜。
板子题
题目：
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
int t;
int m,n;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
if(m%(n+1)==0)
{
cout<<"Lose"<<endl;
}
else
{
cout<<"Win"<<endl;
}
}
return 0;
}
扩展题
题目链接
#include<cstdio>
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
int main()
{
int t;
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n%(m+1)==0)
printf("none\n");
else
{
if(n<=m){
for(int i=n; i<=m; i++)
{
if(i!=m)
cout<<i<<" ";
else
{
cout<<i;
}
}
cout<<endl;
}
else{
cout<<n%(m+1)<<endl;
}
}
}
return 0;
}
扩展题：
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
int n,q,p,sum=0;
while(scanf("%d%d%d",&n,&p,&q)!=EOF)
{
if(n%(p+q)>p||n%(p+q)==0)
cout<<"WIN"<<endl;
else
cout<<"LOST"<<endl;
}
return 0;
}
斐波那契博弈
#include<stdio.h>
#include<algorithm>
using namespace std;
long long a[50];
void init()
{
a[0]=1,a[1]=1;
for(int i=2; i<93; i++)
a[i]=a[i-1]+a[i-2];
}
int main()
{
long long n;
init();
while(~scanf("%llu",&n))
{
int flag=0;
for(int i=1;i<93;i++)
if(n==a[i]){
flag=1;
break;
}
if(flag)
printf("No\n");
else
printf("Yes\n");
}
return 0;
}
威佐夫博弈
有两堆石子，两个玩家可以（1）从两堆石子中分别取相同数目的石子（2）从一堆石子中取任意数目的石子，求解先手是否能赢。
结论
如果成立，则此局面为先手必败，否则，先手必胜。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#define ll long long
using namespace std;
ll a,n,m;
int main()
{
while(scanf("%lld%lld",&n,&m)!=EOF)
{
if(n<m)
{
int t=m;
m=n;
n=t;
}
double w=(sqrt(5)+1)/2;
ll s=(n-m)*w;
if(s==m)
{
cout<<"0"<<endl;
}
else{
cout<<"1"<<endl;
}
}
return 0;
}
拓展题 取(2堆)石子游戏
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int a,b;
int main()
{
while(scanf("%d%d",&a,&b)!=EOF)
{
if(a==0&&b==0)
break;
int x,y;
if(a>b)
swap(a,b);
double sum=((1+sqrt(5))/2);
int yy=(b-a);
int ww=sum*yy;
if(ww==a)
cout<<"0"<<endl;
else
{
cout<<"1"<<endl;
for(int i=1; i<=a; i++)
{
x=a-i;
y=b-i;
int mmp=(y-x);
int we=sum*mmp;
if(we==x)
{
cout<<x<<" "<<y<<endl;
}
}
for(int i=b-1; i>=0; i--)
{
x=a;
y=i;
if(x>y)
swap(x,y);
int mmp=(y-x);
int we=mmp*sum;
if(we==x)
{
cout<<x<<" "<<y<<endl;
}
}
}
}
return 0;
}
尼姆博弈
一般题目：
尼姆博弈可以说是巴什博弈的加强版，即有N堆石子，可以从一堆石子中拿走任意个，先拿完者胜
结论：
一个格局记为（x1,x2,…,xn)，且次序无关，此格局为 P-格局 当且仅当 x1^x2^…^xn = 0.其中^是按位异或运算
#include<stdio.h>
#include<iostream>
using namespace std;
const int MM=1e6+5;
int a[MM];
int main()
{
int t,n;
while(scanf("%d",&t)!=EOF)
{
if(t==0)
break;
int sum=0;
for(int i=0;i<t;i++)
{
scanf("%d",&a[i]);
sum^=a[i];
}
if(sum)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
#include<stdio.h>
#include<iostream>
using namespace std;
const int MM=1e6+5;
int a[MM];
int main()
{
int t,n;
while(scanf("%d",&t)!=EOF)
{
if(t==0)
break;
int sum=0;
int ans=0;
for(int i=0;i<t;i++)
{
scanf("%d",&a[i]);
sum^=a[i];
}
if(sum==0)
cout<<"0"<<endl;
else
{
for(int i=0;i<t;i++)
{
if(a[i]>(sum^a[i]))
ans++;
}
cout<<ans<<endl;
}
}
return 0;
}
SG函数
博弈
打表：模板
int s[10005],sg[10005];
void getsg() //获得sg函数的模板
{
memset(sg,0,sizeof(sg));
for(int i=1; i<=10000; i++)
{
memset(s,0,sizeof(s));
for(int j=1; j+j<i; j++)
s[sg[j]^sg[i-j]]++;
for(int j=0; j<=10000; j++)
if(!s[j])
{
sg[i]=j;
break;
}
}
}
int sg[maxn];//sg[n] n表示每堆数量
int s[k];//每次能取的值，下标从0开始，0 ~ k-1,必须有序，可以sort(s,s+k);
bool vis[maxn];
const int k;//k是集合s的大小
void get_sg()
{
int i,j;
for(i=0;i<maxn;i++)
{
memset(vis,0,sizeof(vis));
j=0;
while(j<k&&s[j]<=i)
{
vis[sg[i-s[j]]]=1;
j++;
}
for(j=0;j<maxn;j++)
if(!vis[j])
{
sg[i]=j;
break;
}
}
}
int main()
{
...
memset(sg,-1,sizeof(sg));
get_sg();
if(sg[n]==0) //先手必败
else //先手必胜
//如果有多堆，则
// num=sg[n1]^sg[n2]^sg[n3]^....^sg[nx];
// if(num==0) 则先手必败
// else 先手必胜
...
}
京公网安备 11010502036488号