POJ 2348 Euclid's Game（博弈）题解

题意：有a，b两个数字，两人轮流操作，每次可以选择两个之中较小的数字，然后另一个数字减去选择数字的任意倍数（不能减到负数），直到其中一个为0，不能操作为败

思路：这题用博弈NP思想，必败点和必胜点之间的转化。

我们假设当前状态为（x，y）其中x>=y，那么必有以下任一状态：

1. x < 2 * y：那么这是只能执行一个操作x - y，如果这个操作之后变成必败态，那么当前为必胜态；反之亦然。

2. x >= 2 * y：显然此时有多种选择，假设x = k * y，如果x - （k - 1） * y就变成了第一种情况，如果x - k * y就变成了第一种情况操作后的情况，显然这其中有一个是必胜态，那么此时情况2必然是必胜情况。

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

typedef long long ll;

const int maxn = 1e6 + ;

const int seed = ;

const ll MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

using namespace std;

int main(){

    ll a, b;

    while(~scanf("%lld%lld", &a, &b) && a + b){

        int times = , num = ;

        while(a !=  && b != ){

            times++;

            if(a > b) swap(a, b);

            num = b / a;

            if(num >= ) break;

            b -= a;

        }

        if(times & ) printf("Stan wins\n");

        else printf("Ollie wins\n");

    }

    return ;

}

秒客网

POJ 2348 Euclid's Game（博弈）题解

相关文章