2020ccpc-mianyang-G(博弈论)题解

题目描述

一种叫 0123 的纸牌游戏，桌面上有 张 ， 张 ， 张 ， 张 ，Rabbit 和 Horse 先后取牌（Rabbit 先手），每次选择两张牌，要求数字之和 ，然后将这两张牌替换成数值为两张之和的一张牌，最后无法取牌的玩家输，求赢家。

题解：找规律，SG打表

首先发现，能选的组合有：

因此，在刚开始数量足够的时候，无论先手怎么选，后手都能使两人操作后 或 ，因此如果 为二的倍数且 为三的倍数，先手必败。

因此，只需考虑剩下（数量不够时）的每种情况，当某种情况能转移到必败态，则该情况为必胜态，反之为必败态。经过分析，一共有五种情况。可以用 dfs 实现。

代码

#include <bits/stdc++.h>
using namespace std;

bool dfs(int c0, int c1, int c2, int c3) {
    if (c0 == 0 && c1 == 0) return false;
    if (c0 == 0 && c1 == 1 && c2 == 0) return false;
    if (c0 > 0 && !dfs(c0 - 1, c1, c2, c3)) return true;
    if (c1 >= 2 && !dfs(c0, c1 - 2, c2 + 1, c3)) return true;
    if (c1 > 0 && c2 > 0 && !dfs(c0, c1 - 1, c2 - 1, c3 + 1))
        return true;
    return false;
}

int main() {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++t) {
        int c0, c1, c2, c3;
        scanf("%d %d %d %d", &c0, &c1, &c2, &c3);
        bool f;
        if (c0 + c1 + c2 + c3 == 0) f = false;
        else if (c1 + c2 + c3 == 0 && c0 % 2 == 1) f = false;
        else if (c1 + c2 + c3 == 0 && c0 % 2 == 0) f = true;
        else f = dfs(c0 % 2, c1 % 3, c2, c3);
        printf("Case #%d: ", t);
        f ? puts("Rabbit") : puts("Horse");
    }
}