HDU2177----取(2堆)石子游戏博弈

威佐夫博弈
输出1的时候，接下来输出的第一次取之后剩下的，就是让我们输出取一次后能达到的奇异状态。有两种方法：1、只取一堆；2、两堆都取相同数量的石子。我们可以先确定小于初始状态的奇异状态有哪些，然后再判断这些奇异状态是否能够由以上两种方法达到。（注意：输出的时候取两堆的排在前面）

#include #include #include #include using namespace std; struct Node//用结构体Node来记录取一次能达到的奇异状态，flag=0代表取一堆,flag=1代表取两堆 { int a,b; int flag; }node[100000]; bool cmp(Node x,Node y) { return x.flag>y.flag; }int main() { int a,b; while(scanf("%d%d",&a,&b)!=EOF) { if(a==0 && b==0) break; double k=(1+sqrt(5.0))/2; if((int)((b-a)*k) == a) printf("0\n"); else { printf("1\n"); int s=0; for(int i=0; i<=a; i++) { int m=(int)(i*k); int j=m+i; if(j>b) break; if(j==a || j==a || m==a) { s++; node[s].a=m,node[s].b=j,node[s].flag=0; } else if((a-m) == (b-j)) { s++; node[s].a=m,node[s].b=j,node[s].flag=1; } } sort(node+1,node+1+s,cmp); //按flag从大到小进行排序，然后按顺序输出即可 for(int i=1; i<=s; i++) printf("%d %d\n",node[i].a,node[i].b); } } return 0; }

【HDU2177----取(2堆)石子游戏】