题解 P3150 【pb的游戏（1）】

· · 题解

这道题是洛谷博弈论专题的第一道入门题, 然而刚开始我是不会做的, 毕竟是道入门题, 我博弈论还没入门呢.

这道题的做法就是: 如果m为偶数, 那么先手赢(即pb), 如果m为奇数, 那么后手赢(即zs).

<strong> 做法很简单, 可是我们要知道怎么做的</strong>

说实话我对于他们两个都聪明绝顶, 都会按照最优策略来走很不感冒. 既然他们聪明绝顶, 那么先手明知道m为奇数时自己会输, 为什么不洒脱一点走呢? 也许乱走出奇迹?

那我们来试试看. 当m = 13时, 先手为什么会输. 前提是先手知道自己按照最优策略会输(因为轮到他分时为奇数), 所以开始乱走.

先手：１３ = ４ +９
后手：选４, ４ = １ +３
先手：不得已选３，　３＝１＋２
后手：选２，２＝１＋１
后手赢

不服? 再来一把

先手：13＝６＋７
后手：选６，６＝１＋５
先手：选５，５＝１＋４
后手：选４，４＝１＋３
先手：３＝１＋２
后手：２＝１＋１
后手赢

经过了两把测试, 我们不管先手怎么走(乱走或所谓最优策略),只要他手里是奇数,都不得不拆成奇数+偶数, 那么后手只要选择偶数, 他就可以把这个数化成m = n + 1(后手的最优策略), 把奇数转移给先手. 这样经过若干次转移之后, 后手手里一定会是2,然后2 = 1 + 1, 后手就赢了.

所以, 其实手里是奇数的人是没有胜算的, 所以这个状态是必败态. 而手里是偶数的人是有必胜的可能的, 只有他才有最优策略而且只要他按照最优策略走, 他一定会赢, 因此这个状态是必胜态. 当然, 如果他sa, 就可能将必胜态拱手让人.

而理解这个博弈论问题的关键, 就是拥有偶数的策略: 每次减一. 因而可以再次将偶数态(必胜态)转移过来.

事实上, 刚接触此题时, 我对所谓绝顶聪明, 所谓最优策略很困惑, 两个人博弈, 凭什么说我走的是最佳策略结果却输了? 我是不是应该把所有走法都试一遍, 然后都输给你才算我输?

我的理解是: 必败态从来没有最佳策略, 博弈也不是双方的博弈, 而是处在必胜态的那方和自己博弈. 而这场博弈, 由于绝顶聪明的前提, 是必胜的, 而我们要做的, 只是找出谁有跟自己博弈的机会.

此题入门, 然颇有感触, 大佬轻喷.

#include <iostream>
using namespace std;

int main()
{
    int n, x;
    cin >> n;
    while (n--) {
        cin >> x;
        if (x & 1) cout << "zs wins" << endl;
        else cout << "pb wins" << endl;
    }
}