zoj 2083 – Win the Game

问题是这样的,两个人玩一个类似 Nim 的游戏。

一共有 N 条线段(线段长度为整数),每条线段长度为 A[i] (0<i<N-1),然后 A 和 B 每次进行移动,每个移动可以从线段的整数位置删掉长度为 2 的整数格,到最后不能移动者输。

那么根据 Sprague Grundy 定理,每条线段等价于一个 Nim 游戏的一堆石子,即对应一个 Nimber 数,把所有单条线段转化成一个 Nimber 数,整个游戏就等价于一个 Nim 游戏了。

具体的 Sprague Grundy 算法可以参照我在博客园的另一篇文章:

http://www.cnblogs.com/fishball/archive/2013/01/19/2866311.html

然后怎么计算单个的 Nimber 数就是一个简单的 DP 问题了。从一条线段可以有很多种办法切分成两条线段(包括0长度的线段),然后就可以得到一个状态转移,从这样就可以应用 Sprague Grundy 的条件了。

// 3853445  2015-01-21 23:38:23 Accepted    2083    C++ 0   272 呆滞的慢板
// 博弈论:Sprague Grundy 定理 

#include <iostream>
#include <set>
using namespace std;

int main() {

    int mex[51] = {0, 0, 1};
    for(int i = 3; i < 51; ++i) {
        set<int> MEX;
        for(int j = 0; j + 2 <= i; ++j) {
            MEX.insert(mex[j] ^ mex[i-2-j]);
        }
        while(MEX.find(mex[i]) != MEX.end()) {
            mex[i] += 1;
        }
    }

    int N, k;
    while(cin >> N) {
        int ans = 0;
        while(N--) {
            cin >> k;
            ans ^= mex[k];
        }
        cout << (ans ? "Yes": "No") << endl;
    }
    return 0;
}

【转载请附】愿以此功德,回向 >>

原文链接:https://www.huangwenchao.com.cn/2015/01/zoj2083.html【zoj 2083 – Win the Game】

发表评论

电子邮件地址不会被公开。 必填项已用*标注