hdu 3595 GG and MM 博弈论

时间:2023-09-17 14:12:38

同时进行,必须操作这就是Every-SG的特点

同样在贾志豪的论文中有提到这种游戏:组合游戏略述——浅谈SG游戏的若干拓展及变形

其中这个游戏特点不仅有必胜和必败,而且有时间长短的博弈,对于自己必胜的局面,希望步数越多越好,自己必败的局面,早点结束才有利。显得更加复杂。

其中论文中提到,必胜当且仅当所有的单一游戏步数最大的为奇数。

比较好理解,最大的为奇数,当然是先手赢,其它的都已经提前结束。

在论文中有具体的证明和阐述。

在这题中,可以发现如果X,Y,X>Y而且X/Y==1,则每次从X中取走Y,这步是固定的,但是当X/Y>=2的情况就不一样了。可以控制步数。

在这个游戏中,由于是Every_SG,我们考虑的是步数,那么谁如果拥有第一个X/Y>=2,便具有优先权,可以控制,将所有的X/Y>=2控制在自己手中,到了最后一个,便可以控制奇偶,让自己获胜。以此得到最大的步数,判断奇偶

代码如下:

 #include<stdio.h>
#include<cstring>
#include<algorithm>
#define I(x) scanf("%d",&x)
using namespace std;
int sg[];
int main(){
int s,n,p,q,i,j,l,k;
while(I(n)!=EOF){
s=;
while(n--){
scanf("%d %d",&p,&q);
if(p<q) swap(p,q);
sg[]=p;sg[]=q;
l=;j=-;
while(sg[l]){
sg[l+]=sg[l-]%sg[l];
l++;
}
for(i=,k=l-;i<=l-;i++){
if(sg[i]/sg[i+]>){
if(j>&&i%!=j%) k++;
j=i;
}
}
s=max(s,k);
}
puts(s&?"MM":"GG");
}
return ;
}