前言
一开始看到这道题目的时候,以为是一道模拟,结果看数据范围,
$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 是偶数那么小明赢,反之就是小红赢了!
结论得出来了,代码就很好写了。
代码
1 |
|
写在后面的话
我这篇题解如果有错误,那么请在评论区里留言,我将会很感谢反映的人。
最后,宣传一下我的两个blog 洛谷的,自己的,记得来玩哦!
谢谢观赏!