（一）巴什博弈
只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，
后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。
这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。##
#include <cstdio>
int main()
{
int t;
scanf("%d",&t);
int n,m;
while(t--)
{
scanf("%d%d",&n,&m);
if(n%(m+1)) printf("Win\n");
else printf("Lose\n");
}
}
#include <cstdio>
int main()
{
int n,m;
while(scanf("%d%d",&m,&n)!=EOF)
{
if(m>n)//这种情况先手非必败的话只有一种出法
{
if(m%(n+1)) printf("%d\n",m%(n+1));
else printf("none\n");
}
if(n>=m)//这种情况只需输出大于等于m的就行
{
for(int i=m;i<n;i++)
printf("%d ",i);
printf("%d\n",n);
}
}
return 0;
}
SG Version
#include<cstdlib>
#include<stdio.h>
#include<string.h>
using namespace std;
int fx[1010],g[1010];;
int n,m;
void getSG()
{
memset(fx,0,sizeof(fx));
fx[0]=0;//面对局面0,说明自己没法取,所以局面0的结果是输
for(int i=1;i<=m;i++)//枚举每个局面i
{
memset(g,0,sizeof(g));
for(int j=1;j<=n;j++)//分解i局面,枚举局面i产生的下一个局面,其中限制最多取n个,最少取1个
{
if(i>=j) g[fx[i-j]]=1;
else break;//已经没法取了
}
for(int j=0;j<=m;j++)//这里必须从0开始遍历
if(!g[j])
{
fx[i]=j;
break;
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
getSG();
if(m>n)//这种情况先手非必败的话只有一种出法
{
if(fx[m]) printf("%d\n",fx[m]);
else printf("none\n");
}
if(n>=m)//这种情况只需输出大于等于m的就行
{
for(int i=m;i<n;i++)
printf("%d ",i);
printf("%d\n",n);
}
}
return 0;
}
Good Luck in CET-4 Everybody!
题意:
1、 总共n张牌;
2、 双方轮流抓牌；
3、 每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…）
4、 抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；
每次都是Kiki先抓牌，请问谁能赢呢？
题解一：
(1)、若是留给Cici的是3，那么Cici只能取1个或2个，所以再轮到Kiki取的话必赢。
(2)、若是给Cici留下的是3的倍数，假设为3n(n=1,2,3,..)，那么无论Cici取什么数，剩余的数一定可以写成3m+1或者3m+2(m<n)的形式，那么只要Kiki再取的时候留给Cici的仍然是3的倍数的话，就必胜了。
#include <cstdio>
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n%3) printf("Kiki\n");
else printf("Cici\n");
}
return 0;
}
题解二:
SG ( 嵌套循环 )
#include<cstdlib>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAXN=1010;
int fx[MAXN],g[MAXN];
int pow_2[15];
void getSG()
{
fx[0]=0;
for(int i=1;i<MAXN;i++)//枚举每个局面i
{
memset(g,0,sizeof(g));
for(int j=0;j<25;j++)//枚举的局面i的分解区间
{
if(i-pow_2[j]>=0)
{
g[fx[i-pow_2[j]]]=1;
}
else break;
}
for(int j=0;j<MAXN;j++)
{
if(!g[j])
{
fx[i]=j;
break;
}
}
}
}
int main()
{
pow_2[0]=1;
for(int i=1;i<15;i++) pow_2[i]=pow_2[i-1]<<1;
getSG();
int n;
while(scanf("%d",&n)!=EOF)
{
if(fx[n]) printf("Kiki\n");
else printf("Cici\n");
}
}
题解三:
SG (记忆化搜索)
#include<cstdlib>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAXN=1010;
int fx[MAXN],g[MAXN];
int pow_2[15];
int getSG(int n)
{
if(fx[n]!=-1) return fx[n];
int g[MAXN];
memset(g,0,sizeof(g));
for(int j=0;j<25;j++)
{
if(n-pow_2[j]>=0)
{
getSG(n-pow_2[j]);
g[fx[n-pow_2[j]]]=1;
}
else break;
}
for(int j=0;;j++)
{
if(!g[j])
{
fx[n]=j;
break;
}
}
return fx[n];
}
int main()
{
pow_2[0]=1;
for(int i=1;i<15;i++) pow_2[i]=pow_2[i-1]<<1;
memset(fx,-1,sizeof(fx));
fx[0]=0;//初始化
int n;
while(scanf("%d",&n)!=EOF)
{
if(getSG(n)) printf("Kiki\n");
else printf("Cici\n");
}
}
题解四:
#include<cstdio>
int main()
{
int n;
while(~scanf("%d",&n))
{
n%=(2+1);
if(n==0) printf("Cici\n");//n=(b+1)*r,先手必输
else if(n==2) printf("Kiki\n");//n=b,先手一次性拿走b，先手赢
else if(n&1) printf("Kiki\n");//n<b;则先手和后手每次只能拿走1
//( 因为b^0=1 )，如果是奇数，则先手赢；反之，后手赢。
else printf("Cici\n");
}
return 0;
}
https://scut.online/problem.php?id=93
题目描述
大家都知道小林桑和托尔的相遇其实是假酒造成的，在喝多了酒之后，小林桑不仅会说女仆的话题，作为一个程序员码农她也会和别人玩数字有关的游戏，这次她和托尔玩的是这个游戏：首先我们提出两个整数B,N (1 <=B,N <=109),从小林桑开始，两个人轮流进行操作，操作的内容是：选取一个幂指数k(k≥0)，使得Bk <= N，然后令N = N - B^k。如果轮到一个人的时候没有可以选的幂指数kk了，这个人就输了。给出B,N，你能预测出游戏的最终结果吗？
输入格式
在单个文件包含多组数据，请循环读取至末尾。对于每组数据，包含了两个整数B,N，以空格分割，独占一行。
输出格式
若小林桑获胜，输出"kobayashisan no kachi"，独占一行。若托尔获胜，输出"tohru no kachi"，独占一行。
样例数据
输入
2 37 3
输出
tohru no kachi
kobayashisan no kachi
#include <bits/stdc++.h>
using namespace std;
int T,n,b;
int main()
{
while(scanf("%d%d",&b,&n)!=EOF)
{
n%=(b+1);
if(n==0) printf("tohru no kachi\n");//n=(b+1)*r,先手必输
else if(n==b) printf("kobayashisan no kachi\n");//n=b,先手一次性拿走b，先手赢
else if(n&1) printf("kobayashisan no kachi\n");//n<b;则先手和后手每次只能拿走1
//( 因为b^0=1 )，如果是奇数，则先手赢；反之，后手赢。
else printf("tohru no kachi\n");
}
}
邂逅明下
题意:三个数字n，p，q，表示一堆硬币一共有n枚，从这个硬币堆里取硬币，一次最少取p枚，最多q枚，如果剩下少于p枚就要一次取完。两人轮流取，直到堆里的硬币取完，最后一次取硬币的算输。对于每一行的三个数字，给出先取的人是否有必胜策略，如果有回答WIN，否则回答LOST。
题解:
若当前石子共有n =（p+q）* r个，则A必胜，必胜策略为：A第一次取q个，以后每次若B取K个，A取（p+q-k）个，如此下去最后必剩下p个给B，所以A必胜。
若n =（p+q）* r + left个（1< left <= p）B必胜，必胜策略为：每次取石子活动中，若A取k个，则B去（p+q-k）个，那么最后剩下left个给A，此时left <= p，所以A只能一次去完，B胜。
若n =（p+q）* r + left个（p < left <= q），则A必胜，必胜策略为：A第一次取t（1<left – t <= p）个，以后每次B取k个，则A取（p+q-k）个，那么最后留下1< left – t <=p给B，则A胜。
#include<cstdio>
int main()
{
int n,p,q;
while(~scanf("%d%d%d",&n,&p,&q))
{
n%=(p+q);
if(n==0||n>p) printf("WIN\n");
else printf("LOST\n");
}
return 0;
}
另外,可以通过观察SG函数得出结果
#include<cstdlib>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAXN=65540;
int fx[MAXN],g[MAXN];
int n,p,q;
void getSG()
{
fx[0]=1;//面对局面0,说明已经赢了
for(int i=1;i<p;i++) fx[i]=0;//小于p个,必须自己取完,先手输
for(int i=p;i<=n;i++)
{
memset(g,0,sizeof(g));
for(int j=p;j<=q;j++)
{
if(i-j>=0)
{
g[fx[i-j]]=1;
}
}
for(int j=0;j<=n;j++)
{
if(!g[j])
{
fx[i]=j;
break;
}
}
}
for(int i=0;i<=n;i++)//打印结果
{
if(fx[i]==0) printf("%d %d\n",i,fx[i]);
}
}
int main()
{
while(scanf("%d%d%d",&n,&p,&q)!=EOF)
{
getSG();
if(fx[n]) printf("WIN\n");
else printf("LOST\n");
}
}
（二 ）威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同
时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
我们用（ak，bk）（ak ≤ bk ,k=0，1，2，…,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）（12，20）
可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有
如下三条性质：
1。任何自然数都包含在一个且仅有一个奇异局势中。
由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak-1 + k-1 =
bk-1 > ak-1 。所以性质1成立。
2。任意操作都可将奇异局势变为非奇异局势。
事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
3。采用适当的方法，可以将非奇异局势变为奇异局势。
假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）；如果a = ak ，b > bk，那么，取走b – bk个物体，即变为奇异局势；如果a = ak ， b < bk ,则同时从两堆中拿走 ak – ab – ak个物体,变为奇异局势（ ab – ak , ab – ak+ b – ak）；如果a > ak ，b= ak + k,则从第一堆中拿走多余的数量a – ak 即可；如果a < ak ，b= ak + k,分两种情况，第一种，a=aj （j < k）,从第二堆里面拿走 b – bj 即可；第二种，a=bj （j < k）,第二堆里面拿走 b – aj 即可。 从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。
那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：
ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括号表示取整函数)
奇妙的是其中出现了黄金分割数（1+√5）/2 = 1。618…,因此,由ak，bk组成的矩形近似为黄金矩形，由于2/（1+√5）=（√5-1）/2，可以先求出j=[a（√5-1）/2]，若a=[j（1+√5）/2]，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，bj+1 = aj+1+ j + 1，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。
https://vjudge.net/problem/HDU-1527
#include <cstdio>
#include<algorithm>
using namespace std;
int main()
{
int a,b,k;
while(scanf("%d%d",&a,&b)!=EOF)
{
if(a>b) swap(a,b);
k=b-a;
b=(int)(k*(1+sqrt(5))/2.0);
if(a==b) printf("0\n");
else printf("1\n");
}
}
题意：在威佐夫博奕的基础上新增加了一条要求：就是如果在赢得条件下，输出第一步怎么走。如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜，先输出取走相同数量的石子的情况。
https://vjudge.net/problem/HDU-2177
#include <cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double val=(1+sqrt(5))/2.0;
int main()
{
int a,b,k,ak,bk,x,y;
while(scanf("%d%d",&a,&b)!=EOF,a+b)
{
if(a>b) swap(a,b);
k=b-a;
ak=(int)(k*val);
bk=ak+k;
if(a==ak) printf("0\n");
else
{
printf("1\n");
if(abs(a-ak)==abs(b-bk)&&a>ak)
{
printf("%d %d\n",ak,bk);
}
for(int i=b-1;i>=0;i--)
{
int x=a,y=i;
if(x>y) swap(x,y);
int num=y-x;
if((int)(num*val)==x)
printf("%d %d\n",x,y);
}
}
}
}
（三 ） 尼姆博奕（Nimm Game）：有三堆各若干个物品，两个人轮流从某一堆取任意多的
物品，规定每次至少取一个，多者不限，最后取光者得胜。我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。 任何奇异局势（a，b，c）都有a（xor）b（xor）c =0。
题目1：
今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
可将一堆全取走，但不可不取，最后取完者为胜，求先手胜负。
题解：设ans为所有数据的xor运算，如果ans=0，则必输；否则，则赢。
题目2：
今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
可将一堆全取走，但不可不取，最后取完者为负，求先手胜负。
题解：全是1的时候，特判，数1的个数，奇数输，偶数赢。否则，设ans为所有数据的xor运算，如果ans=0，则必输；反之，则赢。
https://vjudge.net/problem/HDU-1907
题意：n堆石子，最后一个取完的人输。
Nimm博弈：全是1的时候，特判，数1的个数，奇数输，偶数赢。
#include <cstdio>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,ans=0,flag=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&m);
ans^=m;
if(m>1) flag=1;//当所有数据都为1时的特判
}
if(flag){
if(ans==0) puts("Brother");
else puts("John");
}
else
{
if(n&1) puts("Brother");
else puts("John");
}
}
}
https://vjudge.net/problem/HDU-185
题意：二人小游戏：桌子上有M堆扑克牌；每堆牌的数量分别为Ni(i=1…M)；两人轮流进行；每走一步可以任意选择一堆并取走其中的任意张牌；桌子上的扑克全部取光，则游戏结束；最后一次取牌的人为胜者。 现在我们不想研究到底先手为胜还是为负，我只想问大家：
――“先手的人如果想赢，第一步有几种选择呢？”
#include <cstdio>
const int maxn=110;
int arr[maxn];
int main()
{
int n,res,sum;
while(scanf("%d",&n)!=EOF,n)
{
res=0;
sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",arr+i);
res^=arr[i];
}
if(!res) {
printf("0\n");
continue;
}
//为了让对手输，则自己第一轮应该在某一堆拿走k块石头，使得对手面对奇异状态，即对手的异或为0
//第i堆可以取走石头的前提是，使对手面对奇异状态的石头数<第i堆的石头数
for(int i=1;i<=n;i++)
{
if((res^arr[i])<arr[i]) sum++;//res^arr[i]:除了第i堆石头，其它堆的石头进行xor运算
}
printf("%d\n",sum);
}
return 0;
}
网友评论