【问题描述】
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
【要求】
【数据输入】输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。
【数据输出】输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。
【样例输入】
2 1
8 4
4 7
【样例输出】
0
1
0
新手求教

这个问题逻辑思维比较强~
可以分析必输条件~

由1得两堆石子数量分别为2 1或者1 2是必输的~
所以要必胜~则要造成对方2 1或者1 2的局面~
而两堆石子的关键数据是两堆石子的数量差|a-b|~

而每次最少也要取1颗石子~
这样就会分两种情况讨论~

当|a-b|为奇数并(a!=0&&b!=0)时轮到你取~除了其中一堆石子被取光(此时已经输了~可以排除)的极端情况下~对手总能保持|a-b|的新值为奇数~
也就是说下一次取石子时|a-b|仍然为奇数~
这种情况迭代下去极限是a=2 b=1或者a=1 b=2--此时必输~
相反~
当|a-b|为偶数时上面的你便成了"对手"~此时必胜~

还有~后一种情况已经包含了a=b的必胜情况了~判别完成~
看上去高大上的题目判断代码出奇地简短~

 if (abs(a-b)%2==0||a==0||b==0)
    pringf("1\n");
  else
    printf("0\n");

分析到这里这题很明显是取牙签的翻版~

就是这样~解读完毕~

[此贴子已经被作者于2017-2-27 22:51编辑过]

谢大神赐教，有思路了呢

不对，比如

(只考虑前数小)
（0，0）（0，1）（1，1）（1，2）（n，n）不做分析

（1，n）(n > 2) 时，先手赢，取 n-2 可以（1，2）
（2，n）时，先手赢，取 n-1 可以（1，2）
（3，4）时，先手赢，各取 2 个可以 （1，2）
考虑（3，5），无论怎么取，都不会变成（1，2），所以先手必输。
（3，n）时，先手变成（3，5）赢
（4，m）(m < 7)时，先手赢，（45）-> （12）(46) -> (35)
同上（4，7）不能变成 (1，2)和（3，5）先手必输。
（4，n）(n > 7)时，取 n-7 可以 （4，7）
（5，m）(m < 9)，先手赢，（56）-> （12）(57) -> (35)  (58) -> (47)
（5，n）(n > 8)，先手赢，取 n-3  变成（5，3）即可

最后的结果为 (1,2)，(3,5)，(4,7)，(6,10)

差值依次递增，左数为之前没出现过的数。

int p = dis = 1;
bool visit[MAX] = {false};
while (p < MAX) {
    ans.add(p, p + dis);
    visit[p] = visit[p + dis] = true;
    while (visit[p]) p++;
    dis += 1;
}

威佐夫博弈论。

[此贴子已经被作者于2017-2-28 18:09编辑过]

收到的鲜花

• 九转星河 于 2017-02-28 18:05 送鲜花  10朵   附言：我很赞同

佩服我还是考虑不周看来还是功夫不够……~

谢谢大神

学习....