程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 1378 - A Funny Stone Game sg博弈

uva 1378 - A Funny Stone Game sg博弈

編輯:C++入門知識

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 
#include 
#include 
#include 
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
#define zero(_) (_<=eps)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=100010;
const LL INF=0x3FFFFFFF;
int sg[100];
bool rem[100];
int n;
void init()
{
    sg[0]=0;
    for(int i=1; i<=25; i++)
    {
        memset(rem,0,sizeof rem);
        for(int j=i-1; j>=0; j--)
            for(int k=j; k>=0; k--)
            {
                rem[sg[j]^sg[k]]=1;
            }
        int t=0;
        while(rem[t]) t++;
        sg[i]=t;
    }
}
bool help[100];
//0 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42
int main()
{
    init();
    int kk=1;
    while(cin>>n&&n)
    {
        memset(help,0,sizeof help);
        int ans=0;
        for(int i=0; i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved