0%

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

题目描述

一种叫 0123 的纸牌游戏,桌面上有 c_0 0 c_1 1 c_2 2 c_3 3 ,Rabbit 和 Horse 先后取牌(Rabbit 先手),每次选择两张牌,要求数字之和 \leq3 ,然后将这两张牌替换成数值为两张之和的一张牌,最后无法取牌的玩家输,求赢家。

题解:找规律,SG打表

首先发现,能选的组合有: 0+0,0+1,0+2,0+3,1+1,1+2

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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");
}
}