题解 P4136 【谁能赢呢?】

前言

一开始看到这道题目的时候,以为是一道模拟,结果看数据范围,

肯定是过不了的,更何况还有神奇的多组数据。

分析

于是,我就开始思考。那么在图画上模拟一遍吧!

A 代表 小明 ,B 代表 小红 ,图画的可能不太好,还请各位大佬谅解,首先模拟一下 的格子吧。

石头,s 代表石头在左上角:

1LJzAU.png

然后开始搬石头,小明先来:

1LYaCQ.png

小明选择搬到了 1,1 的地方,由于是每个人都会最优策略所以小红:

1LY5K1.png

然后又是小明:

1Ltrzd.png

很显而易见,小明赢了!

那么我们来分析一下。

小明走一步,小红走一步,然后又是小明走一步。

石头也占一个格子。

你发现了吗? 如果是个奇数那么就是小明到最后一格,也就是小红输了。

如果是个偶数那么就是小红到最后一格,也就是小明输了。

先别急着写代码,因为还可以优化。

如果是奇数那么就是小红输了,也就是 如果是偶数那么就是小红输了。

我们可以根据某个定理知道, 的奇偶性不变,所以可以得出:

如果 n 是偶数那么小明赢,反之就是小红赢了!

结论得出来了,代码就很好写了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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 洛谷的自己的,记得来玩哦!

谢谢观赏!

-------- 本文结束 感谢阅读 --------