题目描述：
给一个长度为 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
西月弦 阅读(428)
评论(0) 编辑 收藏 引用 所属分类:
解题报告