題目描述：
給一個長度為 N<1000 的環。A和B兩個人每次在這個鏈上選一段長度為 M<1000 的未染色區間進行染色。直到某人不能進行此操作時判此人負。假設兩人都足夠聰明，請你判斷誰會取得勝利？吐槽：
1. 真是不太喜歡博弈題，能推出SG函數還好說，關鍵有的題要純靠YY這就很讓人上火了..... 2. 最近感覺狀態還可以，似乎又找到了高中時候的感覺-----為了一個目標不息奮斗！！ 3. SG定理的證明完全不會啊..... 不全部搞懂真不是我性格....思路分析：
明顯和喜聞樂見的NIM游戲是同一類型的.... 推薦兩篇論文 1. 《由感性認識到理性認識 -- 透析一類博弈游戲的解答過程》 張一飛
2. 《組合游戲略述——淺談 SG 游戲的若干拓展及變形》賈志豪
總之SG函數就是對于某局面u有
SG(u) = mex (SG(v)| u可以轉移到v) --- 1
在我們每次只能進行一步操作的情況下,對于任何的游戲的和,我
們若將其中的任一單一 SG-組合游戲換成數目為它的 SG 值的一堆石子,
該單一 SG-組合游戲的規則變成取石子游戲的規則(可以任意取,甚至
取完),則游戲的和的勝負情況不變。
而且如果局面u是游戲的和，由若干個單一游戲 u0,u1,...,un組成的話，那么SG函數滿足
SG(u) = SG(u0) xor SG(u1) xor ... xor SG(un) --- 2
于是就可以解這道題了，雖然我至死都不會證明.....
這道題拿掉一個區間之后，變成了一個長度為n-m的鏈。
然后這個游戲的每個局面都可以變成：對于許多個長度不一的鏈，你可以每次選一個鏈(假設長度為L)，把它拆成兩個長度和為L-M的鏈。
每個單鏈就是一個單一的長度，它有一個SG值SG(L)。它的后繼狀態最多有L-M+1個，而且后繼狀態都是游戲的和，SG(x,L-M-x)。
根據2式得:
SG(x,L-M-x) = SG(x)^SG(L-M-x)。
這樣可以算出L的每個后繼狀態SG(i,L-M-i)，根據1式計算出SG(L)
如果SG(L)沒有后繼狀態的話，即L<M。有SG(L) = 0 (先手必敗)。
1 #include<iostream>
2 #include<cstdio>
3 #include<cassert>
4 using namespace std;
5 int n,m;
6 int dp[1005];
7 int solve(int k){
8 // cout<<k<<endl;
9 assert(k >= 0);
10 if(k<m) return 0;
11 int &ans = dp[k];
12 if(ans != -1) return ans;
13 bool vis[1001] = {0};
14 for(int i = 0; i<= k-m; i++)
15 vis[solve(i) ^ solve(k-i-m)] = 1;
16 for(ans = 0;;ans++)
17 if(!vis[ans]) break;
18 // cout<<k<<" "<<ans<<endl;
19 return ans;
20 }
21 int main(){
22 int t; cin >> t;
23 for(int oo= 1; oo <=t; oo++){
24 cin >> n >> m;
25 for(int i = 0; i<=n ; i++) dp[i] = -1;
26 int sg = m > n ? 1 : solve(n-m);
27 printf("Case #%d: ",oo);
28 puts(sg==0 ? "aekdycoin" : "abcdxyzk");
29 }
30 return 0;
31 }
32
posted on 2012-04-28 23:14
西月弦 閱讀(460)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告