博弈——通过博弈思想解决的问题（hdu1847，2147）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1847

题目描述：

1、  总共n张牌；
2、  双方轮流抓牌；
3、  每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…）；
4、  抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；

我们可以把他当成一个只能取2^n数的一个取石子游戏，很像巴什博弈，但是由于没有明确的可取周期，

我们无法构造必胜态的路径。

采用博弈论的思想，先观察底层的状态，0为必败态，1为必胜态，2为必胜态，3为必败态……

我们知道 通过一次操作能将当前状态变成必败态的操作都为必胜态。那么4（3+1），5（3+2）也都是必胜态，6为必败态。

不难发现，必败态为3的倍数。我们来证明一下

首先我们可取的数是2的n次方，所以不可能整除3。那么任何一个3的倍数无论怎么拿也不可能变成3的倍数

反之，由于我们可以取1，2两种数，当我们面对一个非3的倍数时，可以通过去1或者2将其变为3的倍数，然后接下来无论对方怎么取，

我都将其保持在3的倍数。直至30

#include<stdio.h>int main(){int n;while(scanf("%d",&n)!=EOF){if(n%3)printf("Kiki\n");else printf("Cici\n");}return 0;}

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2147

题目描述：

在一个矩阵棋盘中，合法的操作是，左移1步，下移1步，左下移1步。走到最左下点是为必败态

即必败态点为（1，1）（1，3）（3，1）（3，3）……

我们把棋盘看成一个坐标，我们能做的操作是改变其x轴的奇偶性（左移），改变y轴的奇偶性（下移），改变x、y轴的奇偶性（左下移）

也就是，当我们面对一个x，y都是奇数时，无论我们采取什么策略，都无法转移当前状态，而我们走完改变其奇偶性后，对手可以再让我们保持x，y

均为奇数的状态，直至（1，1）

所以，当x，y均为奇数是，为必败态。

#include<stdio.h>int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){if(m*n%2)printf("What a pity!\n");elseprintf("Wonderful!\n");}return 0;}