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; }
Comments | NOTHING