題干：

有兩堆石子，數量任意，可以不同。游戲開始由兩個人輪流取石子。游戲規定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數量的石子。最后把石子全部取完者為勝者。現在給出初始的兩堆石子的數目，如果輪到你先取，假設雙方都采取最好的策略，問最后你是勝者還是敗者。

Input

輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個非負整數a和b，表示兩堆石子的數目，a和b都不大于1,000,000,000。

Output

輸出對應也有若干行，每行包含一個數字1或0，如果最后你是勝者，則為1，反之，則為0。

Sample Input

2 1 8 4 4 7

Sample Output

0 1 0

解題報告：

? ?威佐夫博弈。注意向下取整。二分尋找k。找到后再判斷是否還會有比k大的數也滿足向下取整以后是a。（反正這個for循環也不會執行很多次，于是乎果斷暴力了一下）（因為我才可能會有多個k滿足這個要求，畢竟qq的值是1.618左右，，也不算很大）然后看看可不可以找到b滿足即可。

? ?主要就是用到了威佐夫博弈的公式。

AC代碼：

#include<bits/stdc++.h> #define ll long long using namespace std; int a,b; double qq; bool ok(int mid) {if(floor(mid*qq) >= a) return 1;return 0; } int main() { qq = (1+sqrt(5))/2;int l,r,mid;while(~scanf("%d%d",&a,&b)) {int flag = 0;if(a > b) swap(a,b);l=1,r=b;mid = (l+r) /2;while(l<r) {mid = (l+r)/2;if(ok(mid)) r=mid;else l=mid+1;}int tmp = floor(l*qq);if(tmp == a) {for(int i = l; i<=l+100; i++) {if(floor(i*qq) > a) break;if(b==a+i) flag=1;}}if(flag) puts("0");else puts("1");}return 0 ; } //ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，...n 方括號表示取整函數)

AC代碼2：（直接用庫函數去xjbg）（題解）

/* 任給一個局勢（a，b），怎樣判斷它是不是奇異局勢呢？我們有如下公式：ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括號表示取整函數)奇妙的是其中出現了黃金分割數（1+√5）/2 = 1。618…,因此,由ak，bk組成的矩形近 似為黃金矩形，由于2/（1+√5）=（√5-1）/2，可以先求出j=[a（√5-1）/2]，若a=[ j（1+√5）/2]，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，bj+1 = aj+1 + j + 1，若都不是，那么就不是奇異局勢。然后再按照上述法則進行，一定會遇到奇異 局勢。 */#include<stdio.h> #include<math.h> #include<algorithm> using namespace std; int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF){if(n>m)swap(n,m); // printf("n=%d,m=%d\n",n,m);int k=(int)(n*(sqrt(5)-1)/2.0);if((int)(k*(sqrt(5)+1)/2.0)==n&&m==n+k)printf("0\n");//奇異局勢else if((int)((k+1)*((sqrt(5)+1)/2.0))==n&&m==n+k+1)printf("0\n");//奇異局勢elseprintf("1\n");//非奇異局勢}return 0; }

AC代碼3：（同上）

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std;int main() {int n,m,k,t;while(scanf("%d%d",&n,&m )==2){if(n<m)//交換n，m的值。使n>m ;{n^=m;m^=n;n^=m; }k=n-m;t=k*(1+sqrt( 5 ))/2;if(t==m)printf("0\n"); else printf("1\n"); }return 0; }

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【HDU - 1527】【POJ - 1067】取石子游戏 （威佐夫博弈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。