題目鏈接：http://poj.org/problem?id=3922

題意：兩人取一堆石子，石子有n個(gè)。 先手第一次不能全部取完但是至少取一個(gè)。之后每人取的個(gè)數(shù)不能超過另一個(gè)人上一次取的數(shù)的K倍。拿到最后一顆石子的贏。先手是否有必勝策略？若有，先手第一步最少取幾個(gè)？

思路：

（1）首先k=1的時(shí)候，必?cái)B(tài)是2^i,因?yàn)槲覀儼褦?shù)二進(jìn)制分解后，拿掉二進(jìn)制的最后一個(gè)1，那么對(duì)方必然不能拿走倒數(shù)第二位的1，因?yàn)樗荒苣玫谋饶愣唷Ｄ阒灰凑者@個(gè)策略對(duì)方一直都不可能拿完。所以你就會(huì)贏。

（2）k=2的時(shí)候，必?cái)B(tài)是斐波那契數(shù)列。因?yàn)槿魏我粋€(gè)整數(shù)n都可以寫成若干項(xiàng)不相鄰的斐波那契數(shù)的和，所以我們拿掉1，對(duì)方永遠(yuǎn)取不完再高位的1。因?yàn)殪巢瞧鯏?shù)列兩項(xiàng)f[i]和f[i+2]滿足f[i+2]>2*f[i]。比如設(shè)斐波那契數(shù)列為1,2,3,5,8,13……12=8+3+1，化成二進(jìn)制就好比是10101,那么你拿走最右邊的1(其實(shí)就是1)，那么對(duì)方不可能拿走第三位的1(這個(gè)1其實(shí)是3)，這樣就和 k=1一個(gè)道理，對(duì)方不可能拿完，所以你就能拿完； （3）k>=3的時(shí)候，我們必須構(gòu)造數(shù)列，將n寫成數(shù)列中一些項(xiàng)的和，使得這些被取到的項(xiàng)的相鄰兩個(gè)倍數(shù)差距>k 那么每次去掉最后一個(gè)1 還是符合上面的條件。設(shè)這個(gè)數(shù)列已經(jīng)被構(gòu)造了i 項(xiàng),第i項(xiàng)為a[i],前i項(xiàng)可以完美對(duì)1到b[i] 編碼使得每個(gè)編碼的任意兩項(xiàng)倍數(shù)>K 那么有a[i+1]=b[i]+1;這是顯然的。因?yàn)閎[i]+1沒法構(gòu)造出來。只能新建一項(xiàng)表示。然后計(jì)算b[i+1]。 既然要使用 a[i+1] 那么下一項(xiàng)最多只能是某個(gè)a[t] 使得 a[t]*K<a[i+1] ，于是b[i+1]=b[t]+a[i+1]。

最后判斷n是否在數(shù)列a里面。如果在，那么先手必?cái)　７駝t不停的減掉數(shù)列a中的項(xiàng)構(gòu)造出n的分解，最后一位就是了。

const int MAX=2000000; int a[MAX],b[MAX],n,m,C,num=0;int main() {for(scanf("%d",&C);C--;){scanf("%d%d",&n,&m);a[0]=b[0]=1;int i=0,j=0;while(a[i]<n){i++;a[i]=b[i-1]+1;while(a[j+1]*m<a[i]) j++;if(a[j]*m<a[i]) b[i]=b[j]+a[i];else b[i]=a[i];}printf("Case %d: ",++num);if(a[i]==n){puts("lose");continue;}int ans;while(n){if(n>=a[i]) n-=a[i],ans=a[i];i--;}printf("%d\n",ans);}return 0; }

　　

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的POJ 3922 A simple stone game（K倍减法游戏）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。