发表文章

[最新] POJ - 2348 Euclid's Game (博弈)

a54665sdgf 1月前 0

版权声明:本文为博主原创文章,未经博主允许不得转载。 http://blog.csdn.net/a54665sdgf/article/details/81627079

题目大意:给你两个正数,两个人轮流从较大的数中减去较小的数的倍数,减到其中一个数为0的人获胜。

分析:设较大的数为b,较小的数为a。可以发现,b总是当且仅当减去(b/a)次a之后,才会比a小,然后与a交换,再进行下一轮......无论双方如何操作,游戏的历程总是不变的。因此,可以把每轮游戏的b/a抽象成一堆石子的个数,则游戏规则可以视为:一共有n堆石子,两人轮流从最左边的堆中取走一定数量的石子,取完所有石子的赢。

那么先手的人在什么情况下可以赢呢?

可以分两种情况进行讨论:

(1)如果每一堆石子的个数都为1,那么若堆数为奇数,则先手胜,反之则后手胜。这个结论是显而易见的。

(2)如果至少有一堆石子的个数大于1,则先遇到第一堆个数大于1的石子的胜。因为如果一个人一旦面临了堆数大于1的石子,就能够自由选择以先手或者后手的状态进入下一堆石子的游戏,从而扭转乾坤。如果下一堆石子的先手为必胜态,则可以留一块石子给对方,反之则取光这一堆的所有石子。

AC代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define FRER() freopen("i.txt","r",stdin)
#define FREW() freopen("o.txt","w",stdout)

using namespace std;
typedef long long LL;
int a,b;

int main()
{
    //FRER();
    while(scanf("%d%d",&a,&b)&&a)
    {
        if(a>b)swap(a,b);
        int flag=1;
        while(b%a!=0&&b/a==1)
        {
            int t=b%a;
            b=a;
            a=t;
            flag^=1;
        }
        puts(flag?"Stan wins":"Ollie wins");
    }
    return 0;
}

 

相关推荐
最新评论 (0)
返回
发表文章
a54665sdgf
文章数
39
评论数
0
注册排名
990755