HDU 3595 every-sg模型

多个子游戏同时进行，每个子游戏给出两个数a,b，可以将大的数减去k倍小的数，不能操作者输。

策略就是对于一个必胜的游戏要使得步数更长，对于一个必败的游戏使得步数最短。

以下都来自贾志豪的论文..

对于Every-SG 游戏先手必胜当且仅当单一游戏中最大的step 为奇数。

/** @Date    : 2017-10-15 01:36:47

  * @FileName: HDU 3595 every-sg模型.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

int sg[1010][1010];

int step[1010][1010];

int get_sg(int x, int y)

{

	if(x > y)

		swap(x, y);

	if(sg[x][y] != -1)

		return sg[x][y];

	if(x == 0)

	{

		sg[x][y] = step[x][y] = 0;

		return 0;

	}

	int ma = -1, mi = INF;

	for(int i = 1; i * x <= y; i++)

	{

		int tsg = get_sg(x, y - i * x);//后继点SG

		int xx = y - i * x, yy = x;

		if(xx > yy) swap(xx, yy);

		if(tsg == 0)//后继为终止 最慢

			ma = max(ma, step[xx][yy]), sg[x][y] = 1;

		else //后继为先手必胜 此时必败 最快

			mi = min(mi, step[xx][yy]);

		//cout << tsg << endl;

	}

	if(sg[x][y] >= 1)

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

	else

		step[x][y] = mi + 1, sg[x][y] = 0;

	return sg[x][y];

}

int main()

{

	int n;

	while(cin >> n)

	{

		int ma = 0;

		MMG(sg);

		MMF(step);

		for(int i = 0; i < n; i++)

		{

			int x, y;

			scanf("%d%d", &x, &y);

			if(x > y)

				swap(x, y);

			get_sg(x, y);

			ma = max(ma, step[x][y]);

		}

		printf("%s\n", ma%2?"MM":"GG");

	}

    return 0;

}

//EVERY-SG 单一游戏SG=0 说明必败找后继步数最少的， SG>0 说明必胜找后继步数最多的

巴特西

HDU 3595 every-sg模型

最新文章

热门文章