【题解】HDU-1527 HDU-2177 取(2堆)石子游戏

HDU-1527 HDU-2177 取(2堆)石子游戏

【HDU-1527】HDU：https://acm.hdu.edu.cn/showproblem.php?pid=1527
【HDU-2177】HDU：https://acm.hdu.edu.cn/showproblem.php?pid=2177

题目

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你胜，你第1次怎样取子?

思路

这道题是关于威佐夫博弈的题，威佐夫博弈抛去理论（理论附在Ref里了），我们只需要知道如何判定先手必败

$$ (y-x)\times \frac{\sqrt5 +1}{2} = x \qquad(x>y)$$

其中x和y分别表示两堆石子的数目，知道这个内容后这个代码就非常简单了。

但是有一个需要注意的地方：第一次你拿了之后，下一次是对手拿，而我们这时候就不能再判先手必胜为胜利情况了，而是先手必败为胜利情况

还有，我们不需要考虑第几回合这种情况，就拿同时取石子举例，如果同时取3个石子我们就能赢，但我们非要先拆成取1次再取2次，那跟第一次取3次有区别吗？并没有，要考虑的是奇数次还是偶数次的情况

代码

HDU-1527

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
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * @author OZLIINEX
 * @brief HDU - 1527  取石子游戏 Wythoff博弈
 * @date 2022-05-04
 */

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

typedef long long ll;

using namespace std;

int a, b;
double g = (sqrt(5.0) + 1) / 2;

bool check(int x, int y, bool print) //返回先手是否会获胜的情况
{
    if (x > y)
        swap(x, y);
    bool ans = !(int((y - x) * g) == x);

    if (!ans && print)
        printf("%d %d\n", x, y);

    return ans;
}

int main()
{
    while (~scanf("%d %d", &a, &b) && a + b)
        puts(check(a, b, false) ? "1" : "0");
    return 0;
}

HDU-2177

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * @author OZLIINEX
 * @brief HDU - 2177  取(2堆)石子游戏 Wythoff博弈
 * @date 2022-05-04
 */

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

typedef long long ll;

using namespace std;

int a, b;
double g = (sqrt(5.0) + 1) / 2;

bool check(int x, int y, bool print) //返回先手是否会获胜的情况
{
    if (x > y)
        swap(x, y);
    bool ans = !(int((y - x) * g) == x);

    if (!ans && print)
        printf("%d %d\n", x, y);

    return ans;
}

int main()
{
    while (~scanf("%d %d", &a, &b) && a + b)
    {
        if (check(a, b, false))
        {
            puts("1");

            //两边同时取石子
            for (int i = 1; i <= a; i++)
                check(a - i, b - i, true);

            //从任意一堆里取，这里我们只需要选择大的堆
            for (int i = 1; i <= b; i++)
                check(a, b - i, true);
        }
        else
            puts("0");
    }
    return 0;
}

References

https://www.cnblogs.com/zwfymqz/p/8469863.html
https://zh.m.wikipedia.org/zh-sg/威佐夫游戏