算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

给一个长度为 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
    而且如果u是游戏的和,那么就有个很牛b的Sprague–Grundy定理:
        在我们每次只能进行一步操作的情况下,对于任何的游戏的和,我
        们若将其中的任一单一 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 西月弦 阅读(410) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理