P4136题解

· · 题解

显然最优策略是走遍所有格子。

没有严格证明，因为我不会。

不要看上面那行字，这篇题解因此被打回了。

我们定义“一轮”对决为小明和小红各移动一次棋子以后的状态。

那么，每一轮过后，棋子都可以认为移动了连续的两个格子。

“连续的两个棋子”只有一种形态，就是 1\times 2 的骨牌。

这样一来问题可以近似转换为：不停往棋盘上放骨牌，且每次放置的骨牌必须和上一次放置的位置紧挨着。如果棋盘上可以刚好放下若干块骨牌铺满，那么后手者胜利；反之先手者胜利。

当棋盘上有偶数个格子的时候，我们一定可以找到方法放置若干块骨牌。相反地，当棋盘上有奇数个格子的时候，我们永远无法找到对应的方法。

现在棋盘上有 n^2 个格子，故，当 n^2 \bmod 2 = 0 时，输出 Alice。

否则，输出 Bob。

观察上式，等价于 n \bmod 2 = 0。

所以本质是判断 n 的奇偶性。

练习 while 循环的好题。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    while(n!=0){
        if(n%2==0)cout<<"Alice\n";
        else cout<<"Bob\n";
        cin>>n;
    }
    return 0;
}