现在的位置: 首页 > 综合 > 正文

HDOJ1525 [找规律博弈]

2013年11月23日 ⁄ 综合 ⁄ 共 1008字 ⁄ 字号 评论关闭

题目;题目链接

题目的意思是说:

两个人玩游戏,给出a和b,每次一个人都可以从大的数当中减去小的数的倍数。当一个人把某一个数变成1时,这个人就赢了。先手是Stan,问最后是谁赢了....

分析:

假设两个数为a,b(a>=b)


如果a==b.那么肯定是先手获胜。一步就可以减为0,b


如果a%b==0.就是a是b的倍数,那么也是先手获胜。


如果a>=2*b.  那么 那个人肯定知道a%b,b是必胜态还是必败态。如果是必败态,先手将a,b变成a%b,b,那么先手肯定赢。如果是必胜态,先手将a,b变成a%b+b,b.那么对手只有将这两个数变成a%b,b,先手获胜。


如果是b<a<2*b  那么只有一条路:变成a-b,b  (这个时候0<a-b<b).这样一直下去看谁先面对上面的必胜状态。


这样的话就加判断a,b的关系...属于前3种就ok,否则就继续减,直到减成前三种情况就ok...代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;
int min(int a, int b)
{
    if(a<=b)
        return a;
    return b;
}
int max(int a, int b)
{
    if(a>=b)
        return a;
    return b;
}
double min(double a, double b)
{
    if(a<=b)
        return a;
    return b;
}
double max(double a, double b)
{
    if(a>=b)
        return a;
    return b;
}

int main()
{
    int m, n;
    while(cin >> m >>n)
    {
        if(!m && !n)
            break;
        int ans = 1;
        while(1)
        {
            if(m < n)
                swap(m, n);
            if(n == 0 || m == 0 || m%n == 0 || m/n  >= 2)
                break;
            m = m%n;
            ans++;
        }
        if(ans % 2 == 1)
            printf("Stan wins\n");
        else
            printf("Ollie wins\n");

    }
    return 0;
}

努力努力...


抱歉!评论已关闭.