题解 P4136 【谁能赢呢？】

Shallowy · 2018-01-24 21:32:00 · 题解

额...这题似乎也并不需要什么非常严密、谨慎的证明吧...

其实这题是那啥，小红先手，因为石头已经放好了。

想象一下，可以把整个棋盘拆成若干个1*2的格子，那么，

• 很明显，后手只是从一个小格子的一侧走到了另一侧；

• 而先手则找到了一个新的格子。

因为后手只需走，但先手要找，所以在某个时刻游戏结束时，一定是先手找不到格子了...

看上去很对就行

当n为偶数时，棋盘能完美地被拆掉——可是先手会找不到；当n为奇数时，先手才能赢。

代码装饰的有点别扭...

c++

#include <iostream>
#include <cstdio>
#include <cctype>
#define p(x) putchar(x)
using namespace std;
int rd(){int x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
    return x;
}
int n=rd();
void print(){n&1?p('B'),p('o'),p('b'):
                 (p('A'),p('l'),p('i'),p('c'),p('e')); putchar('\n');}
int main(){
    while(print(),n=rd());
    return 0;
}