$bzoj$:https://www.lydsy.com/JudgeOnline/problem.php?id=2463
$luogu$ 网址不贴了.
$emmm$,$bzojAC3rd$??
我果然是太弱了,$bzoj$ 才切 $3$ 题..
题目保证是最优策略, 并且小明先走, 所以如果 $n \times n$ 为偶数, 输出 $Alice$. 反之输出 $Bob$.
经典博弈论题目啊.
证明方法:
因为我们可以把这个 $n \times n$ 的矩阵分割成若干个 $1 \times 2$ 的长方形方块, 那么如果 $n \times n$ 为奇数, 很显然, 一开始左上角放石子的地方是唯一一个没有被分割的格子. 所以在这种情况下, 先手必败. 反之先手必胜.
证毕.
我们知道, 如果 $n \times n$ 是奇数,$n$ 就为奇数, 如果 $n \times n$ 是偶数,$n$ 也为偶数.
- $code$
- #include <cstdio>
- int main() {
- int n;
- while(1) {
- scanf("%d", &n);
- if(!n) return 0;
- if(n&1) printf("Bob\n");
- else printf("Alice\n");
- }
- }
来源: http://www.bubuko.com/infodetail-2661079.html