【博弈论】poj2348 Euclid's Game

假设当前b>a。

一、b%a==0 必胜

二、b<2*a,当前我们没有选择的余地,若下一步是必胜(最终能到情况一),则当前必败;反之,当前必胜。

三、b>2*a,假设x是使得b-ax<a的整数,考虑一下从b中减去a(x-1)的情况,例如对于(4,19)则减去12。

此时,接下来的状态就成了前边讲过的没有选择余地的情况二,若该状态是必败态的话,当前状态就是必胜态。

                            若该状态是必胜态的话,其下一步是唯一确定的,因此是必败态,所以我们可以直接到达此态。

∴情况三是必胜态。

∴先达到情况一、三的是必胜的。

#include<cstdio>
#include<algorithm>
using namespace std;
long long a,b;
int main()
{
while(1)
{
scanf("%lld%lld",&a,&b);
if(!a&&!b) break;
bool flag=1;
while(1)
{
if(a>b) swap(a,b);
if(b%a==0||b>(a<<1))
{
puts(flag?"Stan wins":"Ollie wins");
break;
}
b-=a;
flag^=1;
}
}
return 0;
}
上一篇:hdu 1525 Euclid's Game 博弈论


下一篇:hdu 1525 Euclid's Game【 博弈论】