HDU 2177 取(2堆)石子游戏题解

知识：博弈论 威佐夫博弈（Wythoff Game）
题目：HDU 2177 链接

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你胜，你第1次怎样取子?
Input
输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000，且a<=b。a=b=0退出。
Output
输出也有若干行，如果最后你是败者，则为0，反之，输出1，并输出使你胜的你第1次取石子后剩下的两堆石子的数量x,y,x<=y。如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜，先输出取走相同数量的石子的情况.
Sample Input
1 2
5 8
4 7
2 2
0 0
Sample Output
0
1
4 7
3 5
0
1
0 0
1 2

题意：这题是威佐夫博弈（Wythoff Game），只不过进一步要求先手胜输出第一次的取子方案。（这道题有一定的思考，但是并不难，非常建议看完 威佐夫博弈（Wythoff Game）的理论概念后，自己独立敲一遍。）
思路：威佐夫博弈就是在这个规则下，称先拿者必败态为奇异局势。（例：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）···这都是奇异局势）奇异局势判断公式：

a[k]=floor（k*(1+√5)/2]）， b[k]=a[k]+k。(k=0,1,2……）

符合公式的（a[k],b[k]） 即为奇异局势。若要输出第一次的取法，打表是不行的（我刚开始就是打表，慢死了）。可以这样想，按威佐夫博弈（Wythoff Game）先手胜就是非奇异局势，先手想要胜利就是不断把非奇异局势变成奇异局势（博弈论基本观点）。两种取法分类讨论，

1. 若从两堆取相同数石子可以变成奇异局势，则b-a==b[k]-a[k]==k（a[k],b[k]是某个奇异局势）所以依据公式a[k]=floor（k*(1+√5)/2]）求得a[k]，判断一下a是否>a[k]即可。
2. 若只取一堆，依据威佐夫博弈（Wythoff Game）的性质（任何自然数都包含且仅包含在一个奇异局势中。）则a可以分为两种情况，a在a[k]中或a在b[k]中。（1）a在a[k]中，a=a[m]，b>b[m]就从b中直接取b-b[m]个石子；b < b[m]就同时从两堆中取出 a[m]- a[b-a] 个，局势变成( a[ b-a ] , b[ b-a] )的奇异局势.与1.相同（2）a在b[k]中，a=b[m]， a[m] < b[m] && a < b 则a[m] < b，就从b中取走b-a[m]个石子，局势变成( a[m] , b[m] )的奇异局势.（PS：看完思路后尽量自己先去做一下，实在想不到再看具体方法解析）

方法：

1. 先判断是不是奇异局势，是先手必败输出0；不是输出1；
2. 若不是，根据题意要求，先看是否能两堆取相同数石子。再判断a在a[k]还是b[k]中，a在a[k]中有两种情况，但是只剩一种输出（a，a+k）；a在b[k]中，只有一种输出（a-k ，a）；

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int maxab=1000010;
const double flag=(sqrt(5)+1)/2;

bool IsSingularity(int a,int b)  //判断奇异局势 
{
    int k=b-a;
    if(a==(int)(flag*k)) return true;
    else return false;
}

void solve(int a,int b)
{
    if(IsSingularity(a,b)) {
        cout<<0<<endl;
        return ;
    }
    cout<<1<<endl;
    int k=b-a;
    int a1=k*flag;
    if(a>a1) cout<<a1<<" "<<a1+k<<endl;
    //a==a[k]
    k=a/flag;
    int note=0;
    if(a==(int)(k*flag)) note=1;
    else if(a==(int)((k+1)*flag)) {note=1; k+=1;}
    if(note && b>a+k) {
        cout<<a<<" "<<a+k<<endl;
        return ;
    } 
    //a==b[k]
    k=a/(flag+1);
    if(a==(int)((k+1)*(flag+1)))  k+=1;
    cout<<a-k<<" "<<a<<endl;
}
int main()
{
    int a,b;
    while(~scanf("%d%d",&a,&b)&&a&&b)
        solve(a,b);
    return 0;
}

小结：这道题写题解时写了好久，不知道怎么表达清楚，也不知道这样写清楚不。。。想这题时想了很多种方法，这是改进的最终版。刚开始想的是打表，慢死了。根本打不出来虽然代码很好写。然后就想直接按威佐夫博弈的性质3，从非奇异局势到奇异局势的证明枚举，第二天想了想，并不需要那么麻烦，根据性质1写两种即可。博弈重在思考，先想好了再写，会容易很多，大幅减少代码量，及编写难度。思考，思考很重要！！！