洛谷P3150 pb的游戏（1）题解博弈论入门

2024-09-07 22:43:27

题目链接：https://www.luogu.org/problem/P3150

这道题目是博弈论的入门题。

我们以 必胜态 和 必败态 来讲解这个问题。

首先，下面的图片演示了前8个数的必胜态和必败态：

可以发现：

当 \(m=1,3,5,7\) 的时候都是必败态；
当 \(m=2,4,6,8\) 的时候都是必胜态。

我们不妨用数学归纳法来证明一下：

对于任意一个大于8的 \(m\) ，假设我已知它前面的 \(m-1\) 个数的状态已经确定，并且奇数都是必败态，偶数都是必胜态。则：

如果 \(m\) 是奇数，则它无论如何分，都是分成一个小于 \(m\) 的奇数和一个小于 \(m\) 的偶数，也就是无论如何分都会留给对手一个必胜态（偶数），则 \(m\) 对我就是必败态；
如果 \(m\) 是偶数，则它可以分成两个奇数（此时留给对手两个必败态），也可以分成两个偶数（此时留给对手两个必胜态），然而因为我绝对聪明，所以我肯定会分成两个奇数，所以此时 \(m\) 对我就是必胜态。

综上所述，可以得到结论：所有的偶数都是必胜态，所有的奇数都是必败态。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

int n, m;

int main() {

    cin >> n;

    while (n --) {

        cin >> m;

        puts( m % 2 ? "zs wins" : "pb wins");

    }

    return 0;

}

最新文章

热门文章