放牧代码和思想
专注自然语言处理、机器学习算法
    正处于一个非常忙的阶段,抱歉不会经常回应任何联络

POJ 2068 Nim 题解《挑战程序设计竞赛》

目录

POJ 2068 Nim 

团体尼姆赛:传统的尼姆游戏由两名玩家进行,在一堆石头中,双方轮流取走任意合法数量块石头,取走最后一块石头的玩家落败。多人尼姆游戏将参赛人数拓展至两个队伍,每支队伍有n名队员交错入座,单次分别能最多取走Mi块石头,取走S块石头中的最后一块的队伍失败,求第一支队伍是否有必胜策略?

4.2找出游戏的必胜策略 

推理与动态规划算法 

动态规划地搜索整个状态树,定义

win[k][j][i]:=第k支队伍在轮到第j名队员且剩余i块石头的状态

如果i等于0,那么这就是必胜态。以此为初始状态往i=S的方向递推,递推规则为:如果当前状态的后续状态中有一个为必败态,则当前状态为必胜态。理解起来很简单,后续状态指的是对方的状态,只要对方有一个必败态,我方就可以转移到此后续状态,让对方落败,我方取胜。

#include <iostream>
using namespace std;

const int MAX_N = 10;
const int MAX_S = 1 << 13;

int n, S;
int M[2][MAX_N];
bool win[2][MAX_N][MAX_S];             // win[k][j][i]:=第k支队伍在轮到第j名队员且剩余i块石头的状态

bool input()
{
    scanf("%d%d", &n, &S);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d%d", M[0] + i, M[1] + i);
    }

    return n > 0;
}

bool solve()
{
    for (int i = 0; i <= S; ++i)         // 石头数量
    {
        for (int k = 0; k < 2; ++k)          // 队伍编号
        {
            for (int j = 0; j < n; ++j)       // 队员编号
            {
                if (i == 0)
                {
                    win[k][j][i] = true;   // 没有石头,必胜态
                    continue;
                }
                win[k][j][i] = false;
                const int nxt_k = k ^ 1;                     // 下一支队伍的编号
                const int nxt_j = (k == 1 ? (j + 1) % n : j);     // 下一个队员的编号
                for (int t = 1; t <= M[k][j] && i - t >= 0; ++t)   // 尝试拿走1到M[k][j]个石头
                {
                    win[k][j][i] |= !win[nxt_k][nxt_j][i - t];    // 只要后续状态有一个必败态,则当前为必胜态
                }
            }
        }
    }

    return win[0][0][S];
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    while (input())
        puts(solve() ? "1" : "0");
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////
14814280 hankcs 2068 Accepted 288K 32MS C++ 1244B 2015-10-14 19:59:51

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 2068 Nim 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机