这题没必要那么麻烦, 只需要推理一下即可:
假设我们有两个数 \(x,y\), 先把 \(x\)设为较大值,\(y\)设为较小值. 现在分成三种情况:
\(1\). 若两数为倍数关系, 操作的一方赢.
\(2\). 若两数商 \(>1\), 那么还是操作一方赢.
\(why?\)
比如就拿 \(25,7\)来说. 这时的操作方有三种选择:\(18\) \(7\),\(11\) \(7\),\(4\) \(7\)
如果他选 \(18\) \(7\), 那后者就面对的是 \(11\) \(7\)或 \(4\) \(7\); 而如果他不选 \(18\) \(7\), 那么他面对的还是 \(11\) \(7\)或 \(4\) \(7\).
此时你会发现,\(11\) \(7\)和 \(4\) \(7\)是必有一个能赢的, 而两人都足够聪明, 所以谁有选择权谁就能赢! 也就是说他不能选 \(18\) \(7\)!
再来举一个栗子:\(31\) \(6\)
这时你会发现, 先手方只有选 \(7\) \(6\)或 \(1\) \(6\)才能保证控制权在他手里, 而显然 \(1\) \(6\)是不行的, 所以只能选 \(7\) \(6\). 于是 \(7\) \(6\) \(--\) \(6\) \(1\) \(--\) \(6\) \(0\), 结果是先手赢!
这时你应该知道了: 谁有选择权 (两种或以上的选择) 谁就能赢!
\(3\). 商为 \(1\), 则继续
举个栗子, 如 \(6\) \(4\), 这时先手没有选择权, 那就只能继续咯, 如 \(2\) \(4\).
- \(Code:\)
- #include<bits/stdc++.h>
- using namespace std;
- bool check(int x,int y){
- for(int i=1;;i++){
- int ma=max(x,y);
- int mi=min(x,y);
- x=ma,y=mi;
- //x 为两数较大值, y 为两数较小值
- if(x%y==0){
- return i%2;// 若两数为倍数关系, 操作的一方赢
- }else if(x/y>1){
- return i%2;// 若两数商 > 1, 那么还是操作一方赢
- }else{
- x-=y;// 否则说明商为 1, 那就继续
- }
- }
- }
- int main(){
- int n;
- cin>>n;
- for(int i=1;i<=n;i++){
- int x,y;
- cin>>x>>y;
- if(check(x,y))cout<<"Stan wins"<<endl;
- else cout<<"Ollie wins"<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3345017.html