自动搬运

查看原文

来自洛谷，原作者为

	Special_zyy **

搬运于2025-08-24 21:23:24，当前版本为作者最后更新于2018-10-19 20:13:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于这道题，我们考虑什么样的状态（假设状态为（$x$，$y$）假定$y>=x$）可以使当前操作的这个人胜利，显然，当$x==y$时，当前操作的这个人必胜了；或者当y为x的倍数是，当前这个人也会获胜。除此之外呐？于是，我们接下来要考虑$x>y$（去掉$x==y$的情况）的情况。

假设$y=kx+z$（z为余数）

如果$k>=2$，那么该状态可以转移到（$x$,$y$-($k$-1)$x$）即($x$,$x$+$z$)，而($x$,$x$+$z$)(z要小于x的，因为z是余数)，只能转移到($x$,$z$)这一个状态，这个应该很好理解的。而（$x$,$y$）也可以直接转移到这个状态（$y$-$kx$），所以不论（$x$,$x$+$z$）这个状态还是其下一个状态（$x$,$z$）为必胜状态，($x$,$y$)均可到达，所以当$k>=2$时，当前操作者必胜。

如果$k<2$呢？那我们只好转到下一个人操作，我们再尝试在下一个人的状态中判断这个人是否必胜。因为$k<2$, 所以($x$,$y$)只能转到($z$,$x$)这个状态。那我们只要递归下去，知道找到必胜状态，返回当前操作者即可。

代码如下：

#include <cstdio>
#include <iostream>
using namespace std;
int m,n,q;
//当前操作者为p,p为0时代表Stan操作,p为1时代表Ollie操作。
int find(int x,int y,int p)
{
	if(x==y) return p;//返回胜者.
	if(y/x>=2) return p;//返回胜者.
	else return find(y-x,x,p^1);//向下一个状态查找.
}
int main()
{
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>m>>n;
		if(m>n) swap(m,n);
		if(find(m,n,0)==0) cout<<"Stan wins"<<endl;//如果返回0,胜者为Stan,反之则为Ollie.
		else cout<<"Ollie wins"<<endl;
	}
	return 0;
	
}