问题描述

$Alice$和$Bob$在玩取石子游戏，摆在他们面前的有$n$堆石子，第$i$堆石子有$a_i$个，两人轮流取石子，每次只能从一堆中取，而且每堆石子都有各自的限制，就是第i堆石子每次只能取$1-k_i$个。
如果$Alice$先手，他会赢吗？

输入输出格式

输入格式：

• 第一行一个数$n$。
• 第二行$n$个数，分别是每堆石子的个数，
• 第三行$n$个数，分别是每堆石子限制取的个数。

输出格式：

• 如果$Alice$获胜输出$Alice$，否则输出$Bob$

输入输出样例

输入样例#1：

5
3 7 5 19 16
3 4 10 7 5

输出样例#1：

Alice

提示信息

$1\le n\le 1000；1\le a_i，k_i\le 100000$。

算法

尼姆博奕

有$N$堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。这种情况最有意思，它与二进制有密切关系，我们用 $(a,b,c)$ 表示某种局势，首先 $(0,0,0)$ 显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是 $(0,n,n)$，只要与对手拿走一样多的物品，最后都将导致 $(0,0,0)$。仔细分析一下，$(1,2,3)$ 也是奇异局势，（我先拿之后，）无论对手如何拿，接下来都可以变为 $(0,n,n)$ 的情形。

计算机算法里面有一种叫做按位模 2 加，也叫做异或的运算，我们用符号 $(+)$ 表示这种运算。这种运算和一般加法不同的一点是 $1+1=0$。先看 $(1,2,3)$ 的按位模 2 加的结果：

$$\begin{gathered} 1=\text{二进制 }01 \\ 2=\text{二进制 }10 \\ 3=\text{二进制 }11 \\ 1\text{ (+) }2\text{ (+) }3=0\text{ (注意不进位)} \end{gathered}$$

对于奇异局势 $(0,n,n)$ 也一样，结果也是 $0$。任何奇异局势 $(a,b,c)$ 都有 $a\text{ (+) }b\text{ (+) }c=0$。

如果我们面对的是一个非奇异局势 $(a,b,c)$，要如何变为奇异局势呢？假设 $a<b<c$，我们只要将 $c$ 变为 $a\text{ (+) }b$ 即可，因为有如下的运算结果：

$$a\text{ (+) }b\text{ (+) }(a\text{ (+) }b)=(a\text{ (+) }a)\text{ (+) }(b\text{ (+) }b)=0\text{ (+) }0=0$$

要将 $c$ 变为 $a\text{ (+) }b$，只要从 $c$ 中减去 $c-(a\text{ (+) }b)$ 即可。

代码

#include <iostream>
using namespace std;
int n,a[2000],b[2000],ans;
int main() {
	cin >>n;
	for (int i=1; i<=n; i++) {
		cin >>a[i];
	}
	for (int i=1; i<=n; i++) {
		cin >>b[i];
	}
	for (int i=1; i<=n; i++) {
		ans^=a[i]%(b[i]+1);
	}
	if (ans)
		cout <<"Alice";
	else
		cout <<"Bob";
	return 0;
}