P/N态推断博弈训练

1.欧几里得博弈

题意：给你两个数 \(a\) 和 \(b\) ，\(Alice\)，\(Bob\) 轮流操作，每次选择大的数减去小的数的任意整数倍，谁减的到一个0就获胜。

Sample Input

34 12
15 24
0 0

Sample Output

Stan wins
Ollie wins

思路： 设大的为 \(a\)，小的为 \(b\) 。

我们注意到当 \(a/b==1\) 时，此时只有一次操作，我们就设想他是 \(N\) 态，\(N\) 态只能转移到 \(P\) 态。

但是会发现 \(5\)，\(3\) 的时候，转移到 \(2\)，\(3\)，\(N\) 态转移到 \(N\) 态？说明 \(a/b==1\) 时并不是一个 \(N\) 态，但是可以认为他是一个准N态，因为他始终只有一次操作，谁拿到都没得选，直到他们轮流操作到再操作一次就有得选了，就说明这个准N态变成了一个N态，他让对手有的选了，这里用一个循环去判断最后\(Alice\) 到底是从准N态到N态还是到P态就可以了。

#include<iostream>
#include<cstring> 
using namespace std;
int main()
{
	int a,b;
		while(cin>>a>>b)
		{
			if(a==0&&b==0) break;
			int x=max(a,b),y=min(a,b);
			if(x==y) cout<<"Stan wins\n";
			else if(x/y>=2) cout<<"Stan wins\n";
			else{
				int flag=1;
				while(x/y==1)
				{
					int tmp=x;
					x=y;
					y=tmp-x;
					flag^=1;
				} 
				if(flag) cout<<"Stan wins\n";
				else cout<<"Ollie wins\n";
			} 
		}
}

心得：当遇到这种数据范围特别大的博弈题，找出那个只有一种选择的状态，判断他直接是 \(N\) 态还是是一个准N态。

准N态是有可能转移到 \(P\) 态也有可能转移到 \(N\) 态。