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

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，比数组慢会超时。

Reference

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

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