首页 > 代码库 > POJ 2348 Euclid's Game(博弈)
POJ 2348 Euclid's Game(博弈)
题目地址:POJ 2348
每一步只有如下三种情况:(假设a>=b)
1:a%b==0 这时候自然是必败态。
2:a<2*b 这时候的下一步是别无选择的,只能是变为(a-b,a),由于该步是唯一的,所以必胜态与必败态是交替的。
3:a>2*b 这时候是必胜态。为什么呢?因为此时总可以转移到一个必败态。由于第2情况的时候两种状态是交替的,而这时候由总可以转换成(a,a%b)和(a,a%b+b),而(a,a%b+b)与(a,a%b)又属于第2种情况的相邻的,所以必有一个是必败态。根据只要能达到必败态的就是必胜态,所以此时是必胜态。
这样这个题的做法就可以推出来了。只要找到第一个控制a>2*b或者a%b==0的人即可。
代码如下:
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; #define LL long long int main() { LL a, b, f; while(scanf("%lld%lld",&a,&b)!=EOF&&(a+b)) { f=0; while(1) { if(a<b) swap(a,b); if(a%b==0) break; if(a>2*b) break; a-=b; f=1-f; } if(!f) puts("Stan wins"); else puts("Ollie wins"); } return 0; }
POJ 2348 Euclid's Game(博弈)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。