2020 CCPC绵阳站G.Game of Cards（博弈搜索）

程序员文章站 2022-03-16 08:41:25

...

G .Game of Cards

Little Rabbit and Little Horse love playing odd card games. Now, they are playing a card game called 0123-game.

There are several cards on the table. c
0
of them are labeled with 0, c
1
of them are labeled with 1, c
2
of them are labeled with 2, and c
3
of them are labeled with 3. Little Rabbit and Little Horse take turns to play the game, and Little Rabbit goes first. In each turn, the player should choose two cards on the condition that the sum of the numbers on the two cards is no more than 3, then replace these two cards with a card labeled with their sum. The player who cannot make a move loses the game.

Little Rabbit and Little Horse wonder who will win the game.

Input
The first line of the input contains an integer T (1≤T≤10
5
) − the number of test cases.

Each test case contains four integers c
0
,c
1
,c
2
,c
3
(0≤c
0
,c
1
,c
2
,c
3
≤10
9
) − the number of cards labeled with 0,1,2,3.

Output
For the x-th test case, if Little Rabbit wins, output Case #x: Rabbit in a single line. Otherwise, output Case #x: Horse in a single line.

Sample Input
2
1 1 1 1
2 2 2 2
Sample Output
Case #1: Horse
Case #2: Rabbit

官方题解截图：

2020 CCPC绵阳站G.Game of Cards（博弈搜索）

我选择了解法2（毕竟搜索不用动脑子

#include<bits/stdc++.h>
int dfs(int c0, int c1, int c2, int c3)
{
    if (c0 == 0 && c1 == 0)return 0;
    if (c0 == 0 && c2 == 0 && c1 < 2)return 0;
    if (c0 > 0 && !dfs(c0 - 1, c1, c2, c3))return 1;
    if (c1 >= 2 && !dfs(c0, c1 - 2, c2 + 1, c3))return 1;
    if (c1 > 0 && c2 > 0 && !dfs(c0, c1 - 1, c2 - 1, c3 + 1))return 1;
    return 0;
}
int main()
{
    int t;
    scanf("%d", &t);
    int cas = 0;
    while (t--)
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        int win = -1;
        if (b == 0 && c == 0 && d == 0) {
            if (a == 0)win = 0;
            else if (a & 1)win = 0;
            else win = 1;
        }
        else win = dfs(a % 2, b % 3, c, d);
        printf("Case #%d: %s\n", ++cas, win ? "Rabbit" : "Horse");
    }
    return 0;
}