[ACM] hdu 2177 取(2堆)石子游戏（威佐夫博弈）

1 2 
5 8
4 7
2 2
0 0

0
1
4 7
3 5
0
1
0 0
1 2

解题思路：

(a,b)奇异态先手必败，非奇异态先手必胜。先判断初始状态，如果为奇异态，则先手必败，否则，要输出先手第一次取石子后，两堆石子各剩下多少个，即由非奇异态转到奇异态。 做法是枚举所有的状态。比如测试数据中的 初始 5  8 是非奇异态，

则先手第一次取石子两堆可能剩下的状态有

一。两堆取相同的石子数

4  7

3  6

2  5

1  4

0   3

二。在第一堆里取

4 8

3 8

2 8

1 8

0 8

三。在第二堆里取

5 7

5 6

5 5

5 4

5 3

5 2

5 1

5 0

代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <string.h>
using namespace std;

bool solve(int a,int b)//判断(a,b)是否为奇异态
{
    double x=(1+sqrt(5))/2;
    int n=b-a;
    if(a==(int)(x*n))
        return 1;
    return 0;

}

int main()
{
    int a,b;
    while(cin>>a>>b&&(a||b))
    {
        if(solve(a,b))
        {
            cout<<0<<endl;//奇异态，先手必败
            continue;
        }
        cout<<1<<endl;
        for(int i=1;i<=a;i++)
        {
            int n=a-i;int m=b-i;
            if(solve(n,m))
                cout<<n<<" "<<m<<endl;
        }
        if(a!=b)//相同时，可能会出现相同的状态，比如取第一堆会出现2 ，3 取第二堆也会出现 2 ，3
        {
            for(int i=1;i<=a;i++)
            {
                int n=a-i;int m=b;
                if(solve(n,m))
                    cout<<n<<" "<<m<<endl;
            }
           for(int i=1;i<=b;i++)
            {
                int n=a;int m=b-i;
                if(n>m)
                    swap(n,m);
                if(solve(n,m))
                    cout<<n<<" "<<m<<endl;
            }
        }
    }
    return 0;
}

[ACM] hdu 2177 取(2堆)石子游戏（威佐夫博弈）,布布扣,bubuko.com

[ACM] hdu 2177 取(2堆)石子游戏（威佐夫博弈）

原文：http://blog.csdn.net/sr_19930829/article/details/23202855