题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2177
1 2 5 8 4 7 2 2 0 0
0 1 4 7 3 5 0 1 0 0 1 2
题目大意:有两堆石子,两人轮流取石子,对于取石子有两种取法,1、从两堆石子中同时取出相同数量的石子,2、只从一堆中取任意数量的石子,另外一堆不变,直至不能取的人为输。
解题思路:
下面各种大神博弈中的一种,定义如下:
威佐夫博奕(Wythoff
Game):有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
对比可以发现,神相似。
列出如下奇异局势:
k:(a,b)
0:(0,0)
1:(1,2)
2:(3,5)
3:(4,7)
4:(6,10)
...
可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k,奇异局势有如下三条性质:
1、任何自然数都包含在一个且仅有一个奇异局势中。
由于ak是未在前面出现过的最小自然数,所以有ak > ak-1 ,而 bk= ak + k > ak
-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。
2、任意操作都可将奇异局势变为非奇异局势。
事实上,若只改变奇异局势(ak,bk)的某一个分量,那么另一个分量不可能在其
他奇异局势中,所以必然是非奇异局势。如果使(ak,bk)的两个分量同时减少,则由
于其差不变,且不可能是其他奇异局势的差,因此也是非奇异局势。
3、采用适当的方法,可以将非奇异局势变为奇异局势
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int main() { int a,b; while(scanf("%d%d",&a,&b),a||b) { if(a>b) swap(a,b); if(a==0) //无论b值是什么,一定赢。因为一次性可以把b所有石头取完,使对方面临奇异局势 { printf("1\n0 0\n"); continue; } int k=b-a;//差值表示第几个奇异局势 int aa=k*(1.0+sqrt(5.0))/2;//根据公式求得该个奇异局势的a值 if(aa==a)//面临该个奇异局势必输 { printf("0\n"); continue; } printf("1\n");//其他情况一定赢 int bb=aa+k;//aa和bb是奇异局势,即石子的剩余情况。 if(a-aa==b-bb&&a>aa)//判断是否可以取相同得使石子数是对方面临奇异局势 printf("%d %d\n",aa,bb); k=2*a/((1+sqrt(5.0)))+1;//只取b,a不变,根据a的值利用公式得到k的值,k为第几个 bb=a+k;//根据次数k和a得到奇异局势的b值 aa=k*(1.0+sqrt(5.0))/2;//根据次数k得到奇异局势的a,来验证不变的a是否就是奇异局势的a值 if(aa==a&&b>bb) printf("%d %d\n",a,bb); k=2*a/(3+sqrt(5.0))+1;//只取b,a不变,根据a的值利用公式得到k的值,k为第几个!!与上面不同的a的位置,上面将a看成是奇异局势的a,现在将a看成的是奇异局势的b,其他均相同 bb=a; aa=k*(1.0+sqrt(5.0))/2; if(bb-k==aa) printf("%d %d\n",aa,a); k=2*b/(3+sqrt(5.0))+1;//只取a,b不变,根据b的值利用公式得到k的值,k为第几个 bb=b; aa=k*(1.0+sqrt(5.0))/2; if(bb-k==aa&&aa<=a&&a!=b) printf("%d %d\n",aa,b); } return 0; }
hdu 2177 取(2堆)石子游戏(威佐夫博奕(Wythoff Game))
原文:http://blog.csdn.net/qiqi_skystar/article/details/50293999