GG and MM HDU - 3595 Every-SG

$ \color{#0066ff}{ 题目描述 }$

两堆石子，GG和MM轮流取，每次在一堆石子中取另一堆石子的k$(k\ge1)$倍，不能操作的输

现在二人要玩n个这样的游戏，每回合每个人对每个未完成的游戏进行操作，胜负取决于最后一个游戏的结果

问能否先手必胜

$\color{#0066ff}{输入格式}$

多组数据

第一行一个n

接下来n行为每个游戏的两堆石子

$\color{#0066ff}{输出格式}$

每组数据输出谁能赢（MM先手）

$\color{#0066ff}{输入样例}$

$\color{#0066ff}{输出样例}$

MM

GG

$\color{#0066ff}{数据范围与提示}$

数据组数$\le 100$

n和每堆石子数都$\le 1000$

$\color{#0066ff}{题解}$

看到对已存在的游戏都要操作，那就是EverySG了

与普通SG不同的是，多了时间这一维

记录一个step，与sg同维

最后step大的必胜

step的转移

如果当前是必胜态，那么从所有必败态的step取max+1转移过来

如果当前是必败态，那么从所有必胜态的step取min+1转移过来

#include <cctype>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define LL long long

LL in() {

	char ch; LL x = 0, f = 1;

	while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);

	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));

	return x * f;

}

const int inf = 0x7fffffff;

const int maxn = 1050;

int sg[maxn][maxn];

int step[maxn][maxn];

bool vis[maxn * maxn];

int work(int x, int y) {

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

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

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

	int max = 0, min = inf;

	for(int k = 1; k * x <= y; k++) work(x, y - x * k);

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

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

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

		vis[sg[xx][yy]] = true;

		if(sg[xx][yy]) min = std::min(min, step[xx][yy]);

		if(!sg[xx][yy]) max = std::max(max, step[xx][yy]);

	}

	for(sg[x][y] = 0; vis[sg[x][y]]; sg[x][y]++);

	if(sg[x][y]) step[x][y] = max + 1;

	else step[x][y] = min + 1;

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

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

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

		vis[sg[xx][yy]] = false;

	}

	return sg[x][y];

}

int main() {

	int n;

	memset(sg, -1, sizeof sg);

	while(~scanf("%d", &n)) {

		int x, y, GG = 0, MM = 0;

		for(int i = 1; i <= n; i++) {

			x = in(), y = in();

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

			work(x, y);

			if(sg[x][y]) MM = std::max(MM, step[x][y]);

			else GG = std::max(GG, step[x][y]);

		}

		puts(MM < GG? "GG" : "MM");

	}

	return 0;

}

巴特西

GG and MM HDU - 3595 Every-SG

$ \color{#0066ff}{ 题目描述 }$

\(\color{#0066ff}{输入格式}\)

\(\color{#0066ff}{输出格式}\)

\(\color{#0066ff}{输入样例}\)

\(\color{#0066ff}{输出样例}\)

\(\color{#0066ff}{数据范围与提示}\)

\(\color{#0066ff}{题解}\)

看到对已存在的游戏都要操作，那就是EverySG了

与普通SG不同的是，多了时间这一维

记录一个step，与sg同维

最后step大的必胜

step的转移

如果当前是必胜态，那么从所有必败态的step取max+1转移过来

如果当前是必败态，那么从所有必胜态的step取min+1转移过来

最新文章

热门文章