uva 1378 - A Funny Stone Game sg博弈
題意:David 玩一個石子游戲。游戲中,有n堆石子,被編號為0..n-1。兩名玩家輪流取石子。 每一輪游戲,每名玩家選取3堆石子i,j,k(i
解法:看上去是將石子都往右移,直到所有都到了n-1堆不能移為止。首先是考慮每堆石子其實是獨立的一個子游戲,堆與堆之間不相互影響。然後就是個數是偶數的對不會影響必勝必敗態,必敗態無法通過移動偶數堆得石子來扭轉局面,因為必勝者只需對稱操作即可。所以每堆石子就成了01的狀態,sg值只是跟位置有關系了。預處理出每個位置的sg值即可。計算第一個可行步驟時候,暴力判斷ijk即可。
代碼:
/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include
#include
#include