放牧代码和思想
专注自然语言处理、机器学习算法

POJ 3537 Crosses and Crosses 题解《挑战程序设计竞赛》

目录

挑战程序设计竞赛第二版.jpg

POJ 3537 Crosses and Crosses 

画叉叉:两人在1*N的格子纸上轮流打叉,最先打出连续3个叉者获胜,问必胜者是谁?

4.2找出游戏的必胜策略 

Nim与Grundy数

任何玩家在位置i处打叉后,纸条一分为二,游戏可划分为两个子游戏i-3和x-i-2。两个子游戏的Grundy数XOR一下得到游戏和的Grundy。Grundy为0则必败,否则必胜。

#include <iostream>
using namespace std;

#define MAX_N 2000 + 16
int sg[MAX_N];

int dfs(const int& x)
{
    if (x < 0) return 0;
    int& g = sg[x];
    if (g >= 0) return g;
    int s[MAX_N] = {0};
    for (int i = 1; i <= x; ++i)
    {
        s[dfs(i - 3) ^dfs(x - i - 2)] = 1;   // // 游戏的和的Grundy是它的子游戏的Grundy的异或
    }
    while (s[++g]);
    return g;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int n;
    memset(sg, -1, sizeof(sg));
    while (~scanf("%d", &n))
    {
        puts(dfs(n) ? "1" : "2");
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

有个小插曲,这种题目不要用set,比数组慢会超时。

15572697 hankcs 3537 Accepted 5460K 469MS C++ 642B 2016-05-30 20:55:48

Reference

https://software.intel.com/zh-cn/blogs/2014/03/06/nim-sg

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

分享到:更多 ()

评论 欢迎留言

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

我的开源项目

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