洛谷 [P1290] 欧几里得的游戏

SG函数的应用

看到这题就想到了SG函数

那么可以考虑最终情况：一个数是x，另一个是0，那么先手必败（因为上一个人已经得到0了，其实游戏已经结束了）

剩下的情况：一个数n，一个数m，假设n>m

那么根据题意，SG(n,m)=mex{SG(n - m, m), SG(n - 2m, m), ......, SG(m, n%m)（此处交换了顺序，因为 m>n%m ）}

考虑里面的SG怎么求。

可以发现，SG(n-m, m)=mex{SG(n-2m, m), SG(n-3m, m)........SG(m, n%m)}

SG(n- 2m, m)同理

所以除了SG(m, n%m)以外的SG都可以由SG（m, n%m）得来

假设SG(m, n%m)0，设n/m=k， SG(n-(k-1)*m,m)mex{SG(m, n%m)}=1

从此往上一直到SG(n, m)的值为2,3,4,5...，即一直必胜，简单记为1

如果SG（m, n%m）1，那么 SG(n-(k-1)*m,m)mex{SG(m, n%m)}=0

剩下的依旧为2,3,4,5,6...，也可记为1

那么可以看出，如果n/m==1，SG(n, m)=！SG(m, n%m)，不然是1

这是一个标准的辗转相除的一个递推式，用GCD的写法即可实现

归纳一下用SG函数解决博弈问题的一般步骤：

找到终止状态
找出任意一个状态，并把它的SG的值用它的后继表示
化简SG之间的关系，递归求解

直观的理解一下本题

首先题目的描述让我们感觉本题与GCD肯定有某些联系

我们发现如果在一个人的手里, \(a > 2b\) 那么这个人必胜，因为他可以选择是在自己进入下一步，还是对手进入下一步

所以第一个出现这个情况的人必胜，如果始终都没有这种情况，就GCD计数

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

using namespace std;

int init() {

	int rv = 0, fh = 1;

	char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') fh = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		rv = (rv<<1) + (rv<<3) + c - '0';

		c = getchar();

	}

	return fh * rv;

}

int n, a, b;

bool SG(int a, int b) {

	if(!b) return 0;

	if(a / b == 1) return !SG(b, a % b);

	return 1;

}

int main() {

	freopen("in.txt", "r", stdin);

	n = init();

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

		a = init(); b = init();

		if(SG(max(a, b), min(a, b))) {

			printf("Stan wins\n");

		}else printf("Ollie wins\n");

	}

	fclose(stdin);

	return 0;

}

巴特西

洛谷 [P1290] 欧几里得的游戏

SG函数的应用

最新文章

热门文章