题解 P4136 【谁能赢呢？】
cstdios
2020-02-13 18:53:56
## 前言
一开始看到这道题目的时候，以为是一道模拟，结果看数据范围，
$o \big( n^2 \big)$肯定是过不了的，更何况还有神奇的多组数据。
## 分析
于是，我就开始思考。那么在图画上模拟一遍吧！
A 代表 小明 ，B 代表 小红 ，图画的可能不太好，还请各位大佬谅解，首先模拟一下 $2 \times 2$的格子吧。
石头，s 代表石头在左上角：
然后开始搬石头，小明先来：
小明选择搬到了 1,1 的地方，由于是每个人都会最优策略所以小红：
然后又是小明：
很显而易见，小明赢了！
那么我们来分析一下。
小明走一步，小红走一步，然后又是小明走一步。
石头也占一个格子。
你发现了吗？$n \times n -1$ 如果是个奇数那么就是小明到最后一格，也就是小红输了。
如果是个偶数那么就是小红到最后一格，也就是小明输了。
先别急着写代码，因为还可以优化。
$n \times n -1$ 如果是奇数那么就是小红输了，也就是 $n \times n$ 如果是偶数那么就是小红输了。
我们可以根据某个定理知道，$n \times n$ 和 $n$ 的奇偶性不变，所以可以得出：
**如果 n 是偶数那么小明赢，反之就是小红赢了！**
结论得出来了，代码就很好写了。
## 代码
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
int n;
//定义变量+头文件，不说了。
int main()
{
n=1;//这里非常要注意，n必须有个值否则进入不了循环。
while (n)//循环开始
{
scanf("%d",&n);
if (n==0) break;//如果n=0那么退出
if (n%2==0) printf("Alice\n");
else printf("Bob\n");//这个判断看上面的结论
}
return 0;
}
```
## 写在后面的话
我这篇题解如果有错误，那么请在评论区里留言，我将会很感谢反映的人。
最后，宣传一下我的两个blog [洛谷的](https://www.luogu.com.cn/blog/dgt/solution-p4136)，[自己的](http://localhost:4000/uncategorized/solution-p4136/)，记得来玩哦！
**谢谢观赏！**