【HDU3595】GG and MM（博弈论）

题面

HDU

一个游戏由多个游戏组成，每次每个操作者必须操作所有可以操作的游戏，操作集合为空者输。

每个游戏由两堆石子组成，每次可以从较多的那一堆中取走较小那堆的数量的倍数个石子。

判断胜负。

题解

\(Every-SG\)，所以我们只需要分开考虑两堆。

这题有点性质，假设两堆石子为\(x,y,x<y\)，那么令\(k=\lfloor\frac{y}{x}\rfloor\)

如果\(k=1\)，显然操作唯一，直接取反后继的\(sg\)函数即可。

如果\(k>1\)，显然先手可以控制是把所有倍数都取完还是强制将\(k\)变成\(1\)，让后手做一次确定操作，所有此时先手必胜，那么只需要考虑\(k=1\)时的后继状态的\(N/P\)情况，做出相应的抉择就好了。

同理维护\(step\)值即可。

最后判断\(step\)最大值来判定胜负情况。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAX 1010

int n,m,sg[MAX][MAX],step[MAX][MAX];

int Getsg(int x,int y)

{

	if(x>y)swap(x,y);

	if(~sg[x][y])return sg[x][y];

	if(!x||!y)return sg[x][y]=0;

	int r=y%x,d=y/x;

	if(d==1)

	{

		sg[x][y]=Getsg(r,x)^1;

		step[x][y]=step[r][x]+1;

		return sg[x][y];

	}

	else

	{

		step[x][y]=Getsg(r,x)+1+step[r][x];

		return sg[x][y]=1;

	}

}

int main()

{

	memset(sg,-1,sizeof(sg));

	ios::sync_with_stdio(false);

	while(cin>>n)

	{

		int mx=0,a,b;

		while(n--)

		{

			cin>>a>>b;if(a>b)swap(a,b);Getsg(a,b);

			mx=max(mx,step[a][b]);

		}

		if(mx&1)cout<<"MM"<<endl;

		else cout<<"GG"<<endl;

	}

	return 0;

}