P4136题解

LEle0309 · 2023-05-07 11:09:25 · 题解

话说在 CSP 前写题解可以 RP++

2023.9.15 感谢 \texttt{\color{black}{f}\color{red}{ast\_photon}} 神仙的帖子，把我的题解撤下了让我意识到了之前思路是错的。

于是乎我看了看传说中的二分图博弈。

然后，我发现，这不又是小奥必胜策略中的一种方法吗（万物皆可小奥）？

2023.9.19 换了张好看一点的图。

题目思路：

我们知道，如果 n 是偶数，则方格一定能被 1 \times 2 的骨牌覆盖。而奇数个骨牌去掉一个格子后一定能被 1 \times 2 的骨牌覆盖（奇数情况的解释看这里）。

给张不怎么好看的图（ 5 \times 5 ）：

其中一根横线表示这两个格子是同一块骨牌。

先手先走多余的一个格子，然后只要后手走一块骨牌的一格，先手就能走这块骨牌的另一格，然后后手只能走新的骨牌。所以后手有路走，先手就一定有路走，即先手必胜。

这是奇数的情况，先手必胜。反之，后手必胜。

于是乎，我们就完成了这道绿题。

AC 记录 & AC 代码：

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//先输入第一个n
    while(n)
    {
        if((n*n-1)%2==1)cout<<"Alice"<<endl;//先手胜  
        else cout<<"Bob"<<endl;//后手胜，注意换行
        cin>>n;//循环最后输入
    }
    return 0;//养成好习惯
}

祝各位 CSP 初赛 RP++！