HDU2177 取（2堆）石子游戏[威佐夫博弈]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2177

这题是需要输出第一步策略的威佐夫博弈，首先打表求出范围内所有奇异局势(ak=k*(1+sqrt(5))/2), bk=ak+k)，然后二分判断给定局势是否为奇异局势，如果不是，那么根据bk=ak+k的性质，可以令m-n=k并算出这个k对应的ak和bk，这就是m和n同时减去一个数对应的局势。然后分别模拟n减去一个值或m减去一个值的情况，并在表中查找对应的局势即可（需要注意m减去一个值后可能会小于n）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=1000000;
int a[maxn+9],b[maxn+9];
int sa[10],sb[10],t=0;
bool check(int n,int m) {
    for(int i=0;i<t;i++)
        if(sa[i]==n && sb[i]==m) return 0;
    return 1;
}
int main() {
    for(int i=1;i<=maxn;i++) {
        a[i]=i*(1+sqrt(5))/2;
        b[i]=a[i]+i;
    }
    int n,m,p;
    while(~scanf("%d%d",&n,&m)) {
        if(n==0 && m==0) break;
        if(n>m) swap(n,m);
        p=lower_bound(a,a+maxn+1,n)-a;
        if(a[p]==n&&b[p]==m) puts("0");
        else {
            puts("1");
            t=0;
            sa[t]=(m-n)*(1+sqrt(5))/2;
            sb[t++]=sa[0]+(m-n);
            p=lower_bound(b,b+maxn+1,m)-b;
            if(!(p>=maxn+1 || b[p]!=m) && n>a[p] &&check(a[p],b[p]))
                sa[t]=a[p],sb[t++]=b[p];
            p=lower_bound(a,a+maxn+1,n)-a;
            if(!(p>=maxn+1 || a[p]!=n) && m>b[p] &&check(a[p],b[p]))
                sa[t]=a[p],sb[t++]=b[p];
            p=lower_bound(b,b+maxn+1,n)-b;
            if(!(p>=maxn+1 || b[p]!=n) && a[p]<m &&check(a[p],b[p]))
                sa[t]=a[p],sb[t++]=b[p];
            for(int i=0;i<t;i++) printf("%d %d\n",sa[i],sb[i]);
        }
    }
}