在组合博弈论中, Nim 游戏是一个非常经典的问题, Nim 游戏可描述如下:
有 n 堆石子, 每堆石子数分别为 a1, a2, , an (ai0) 现有两人轮流从这 n 堆中取石子, 每次必须从某一堆中取任意多的石子, 至少要取一个, 必须从同一堆中取石子, 并且不能超过这一堆石子的总数如果某一方没有石子可取, 那么他就输了
例如:
有 3 堆石子, 分别有 3, 2, 2 个, A 和 B 两人轮流取
A 先从第 2 堆取 1 个, 然后 B 从第 1 堆取 3 个, 此时石子数分别为 0, 1, 2
A 又从第 3 堆取 1 个, 然后 B 从第 1 堆取 1 个, 此时石子数分别为 0, 0, 1
A 最后从第 3 堆取 1 个, 此时所有石子都被取走, B 无石子可取, 所以 B 输了
C. L. Bouton 给出了 Nim 游戏的解法:
考虑把每堆的石子数 a1, a2, , an 表示成二进制, 那么当前游戏局面的 Nim 数为 a1, a2, , an 的按位异或比如在上面的例子中, 3=11(2), 2=10(2), 2=10(2), 将这 3 个数按位异或得 11(2)=3 所以 3 是当前游戏局面的 Nim 数
这里不加证明地给出结论: 假设游戏双方都非常聪明, 当 Nim 数为 0 时, 当前游戏者必败; 当 Nim 数不为 0 时, 当前游戏者必胜
再考虑上面的例子, A 取走第 2 堆的 1 个石子后, 石子数变为 3, 1, 2, 其 Nim 数为 0, 从而使得 B 必败; 此后 A 每次取石子后总能使得留给 B 的局面的 Nim 数为 0, 所以 A 最终取得了胜利
既然你已经知道了如何判断当前 Nim 游戏局面是否必胜, 那么请完成一个稍稍复杂些的任务:
给定 Nim 游戏的当前局面, 如果必胜, 请找出当前游戏者需要取走多少石子才能让对方必败, 如果有多种取石子的方式, 请给出要取石子数最少的再如上面的例子, 初始时, A 从第 1 堆取 3 个石子, 或从第 2 或 3 堆取 1 个石子都可以保证 B 必败, 但因为后者所取的石子数最少, 所以这种情况下答案为 1
Input
输入包含多组数据
每组数据第一行为 n (1n106), 表示石子的堆数
第二行包含 n 个非负整数, 表示每堆石子的数量, 每堆石子不超过 109 个注意, 可以有空的石子堆
输入以 n=0 结束, 不要处理这个数据
Output
对每组数据输出一行, 为需要取走的最少的石子数, 如果当前局面必败则输出 - 1
- Sample Input
- 1
- 10
- 2
- 17 17
- 3
- 3 2 2
- 4
- 1 2 3 4
- 0
- Sample Output
- 10
- -1
- 1
- 4
由于这道题符合尼姆博弈的规则, 所以写起来还算是简单的, 详细请见我的另一篇有关博弈论的文章吧, 在这就不多加阐述了
要注意异或运算的运算顺序是在加减乘除之后的!!!!!
- #include "stdio.h"
- const int N=1000001;
- int a[N];
- int main()
- {
- int i,t,n,min,p;
- while(scanf("%d",&n)!=EOF,n)
- {
- min=100000001;
- t=0;
- for(i=0;i<n;i++)
- {
- scanf("%d",&a[i]);
- t=t^a[i];
- }
- if(t==0)
- printf("-1\n");
- else
- {
- for(i=0;i<n;i++)
- {
- p=a[i]-(t^a[i]);
- if(min>p&&p>0)
- min=p;
- }
- printf("%d\n",min);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2495749.html