P4136 谁能赢呢？ 题解

· · 题解

P4136 谁能赢呢？

思路

因为是上，下，左，右这四个方向。我们不妨把一回合（小明和小红各走一次）看成一个 1\times2 的纸条，然后画图寻找规律：

当 n=1 时：先手无法移动，后手胜；

注意：1 是先手，2 是后手，x 是起点，箭头是前进方向！！！

虽然后手不一定这么走，但 2 的上，下，左，右中的任意一个方向肯定有 1。

当 n=2 时：

后手无法移动，先手胜；

当 n=3 时：

先手无法移动，后手胜；

当 n=4 时：

后手无法移动，先手胜；

当 n=5 时：

先手无法移动，后手胜。

而且，二分博弈论的模型也大概是这样的。

所以，根据二分博弈论：若起点 A 在该二分图的所有最大匹配中均为匹配点，那么先手必胜，否则后手必胜。

因为是二人轮流，所以在 n 为偶数时，最大匹配数是 n\times n\div2，如下图（n=6）：

最大匹配中均为匹配点，先手胜；

在 n 为奇数时，最大匹配数是 (n\times n-1)\div2，如下图（n=5）：

所以，我们可以发现：

当 n 是奇数时，后手赢，

当 n 是偶数时，先手赢。

所以，很容易得到代码：

#include<bits/stdc++.h>
using namespace std;int n;
int main()
{
    while(cin>>n)
    {       
        if(n==0) return 0;
        if(n%2==0) cout<<"Alice\n";//偶数，先手胜
        else cout<<"Bob\n";//奇数，后手胜
    }
    return 0;
}