[博弈]HDU-1525

发布于 2019-04-23  145 次阅读


http://acm.hdu.edu.cn/showproblem.php?pid=1525

↑ 题目链接

题目大意:

两个玩家,斯坦和奥利,从两个自然数开始。斯坦,第一个玩家,从两个数中较大的数减去两个数中较小的数的任何正倍数,前提是得到的数必须是非负的。然后第二个玩家奥利,对得到的两个数字做同样的处理,然后是斯坦,交替进行,直到一个玩家能够从较大的数中减去较小的数的倍数,得到0,从而获胜。例如,玩家可以从(25,7)开始:
25 7
11 7
4 7
4 3
1 3
1 0

解题思路:首先这两个人是极度聪明的。
这点非常重要。
非常重要。
a b 两个数字(a>b)
有以下几种情况
1:a%b==0(包含a==b) 那么此时 先手必胜 直接成0了。
2:a>2倍的b 此时 操作后将变为 b a%b(极限操作 就是b<a<2*b) 操作完之后的人清楚这样是胜还是败的
2.1 如果这样是胜的 那么先手操作完就赢了
2.2 如果这样是败的 那么先手操作成a%b+b b后手只能操作成 b a%b 这样回到了2.1的情况 所以还是先手胜
3.b<a<2b 这样的情况就大-小循环 直到满足1/2的条件时 即可判断谁能赢。

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int eps = 1e-7;
const int maxbit = 30;
const int maxn = 1000000;
const double PI = 3.14;
using namespace std;
const int MOD = 998244353;
int main()
{
	ios::sync_with_stdio(0);
	int a,b;
	while(cin>>a>>b,a+b){
	int flag=1;
	if(b>a) swap(a,b); 
	while(1){
		if(a%b==0||a/b>=2) break;
		a=a-b;
		swap(a,b);
		flag=1-flag;
	}
	if(flag) cout<<"Stan wins\n";
	else cout<<"Ollie wins\n";
}
	return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。