Yet Another Game of Stones

---

Time Limit: 1 Second       Memory Limit: 65536 KB

---

Alice and Bob are playing yet another game of stones. The rules of this game are as follow:

• The game starts with n piles of stones indexed from 1 to n. The i-th pile contains a_i stones and a special constraint indicated as b_i.
• The players make their moves alternatively. The allowable moves for the two players are different.
• An allowable move of Bob is considered as removal of some positive number of stones from a pile.
• An allowable move of Alice is also considered as removal of some positive number of stones from a pile, but is limited by the constraint b_i of that pile.
  • If b_i = 0, there are no constraints.
  • If b_i = 1, Alice can only remove some odd number of stones from that pile.
  • If b_i = 2, Alice can only remove some even number of stones from that pile.
  Please note that there are no constraints on Bob.
• The player who is unable to make an allowable move loses.

Alice is always the first to make a move. Do you know who will win the game if they both play optimally?

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n (1 ≤ n ≤ 10⁵), indicating the number of piles.

The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹), indicating the number of stones in each pile.

The third line of each test case contains n integers b₁, b₂, ..., b_n (0 ≤ b_i ≤ 2), indicating the special constraint of each pile.

It is guaranteed that the sum of n over all test cases does not exceed 10⁶.

We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.

Output

For each test case, output "Alice" (without the quotes) if Alice will win the game. Otherwise, output "Bob" (without the quotes).

Sample Input

3
2
4 1
1 0
1
3
2
1
1
2

Sample Output

Alice
Bob
Bob

问题概述：

有n堆石子，Bob每次可以在其中一堆中取走任意数量的石子，但不能不取，而对Alice却有额外要求，对于某些石子

堆，Alice只能取走偶数个石子（也不能不取），对于某些石子堆，Alice只能取走奇数个石子，现输入一个数n表示

有n堆石子，接下来n个数分别表示每堆石子的个数，再接下来的n个数表示对Alice的限制，第i个数为1表示对于第i堆

石子Alice只能取走奇数个，第i个数为2表示对于第i堆石子Alice只能取走偶数个，第i个数为0表示没有限制（Alice和

Bob一样可以随便取）现必定Alice先手，不能取者输，问谁必胜

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3964

很好考虑到两种情况：

①如果没有限制显然是Alice必胜

②如果有一堆有奇数个石子，但Alice只能取偶数个，那么Bob必胜，因为这堆石子最后剩下1个的时候只有Bob

能取而Alice不能取，这样当Bob面临必输态的时候取这颗石子就变成Bob面临必赢态了，而Alice束手无策

从②可以看出，一旦出现某堆石子Alice只能取偶数个，Alice必须在第一次取得时候就把它取光，否则就一定

输，因为Bob可以把这堆石子取成奇数个，这样Alice就输定了，同理，一旦出现某堆石子Alice只能取奇数个，而

这堆石子的个数又大于1时，Alice也必须在第一次的时候就把这堆石子取光或只留1个，因为如果不这样，Alice

就永远不可能再只花一次就把这堆石子取光了，这样当Bob面临必输态的时候取这堆石子就好了！

这样就可以推出结论：这种对Alice有限制的石子堆如果Alice不首先取光或只留一个，Alice就必输，所以如果这

种石子堆个数如果超过1堆就一定是Bob赢！否则Alice第一次取就只有唯一一种操作，并且取完之后就变成了Bob先

手且非常普通的尼姆博弈了，全部异或一下就好了！

#include<stdio.h>
int a[100005], b[100005];
int main(void)
{
	int T, n, i, c, d, ls;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		for(i=1;i<=n;i++)
			scanf("%d", &a[i]);
		for(i=1;i<=n;i++)
			scanf("%d", &b[i]);
		c = d = ls = 0;
		for(i=1;i<=n;i++)
		{
			if(a[i]%2==1 && b[i]==2)
				ls = 1;
			if(a[i]>1 && b[i]==1)  c++;
			if(b[i]==2)  d++;
		}
		if(ls || d+c>1)
			printf("Bob\n");
		else if(c==0 && d==0)
		{
			ls = 0;
			for(i=1;i<=n;i++)
				ls ^= a[i];
			if(ls!=0)  printf("Alice\n");
			else  printf("Bob\n");
		}
		else if(c==0 && d==1)
		{
			ls = 0;
			for(i=1;i<=n;i++)
			{
				if(b[i]!=2)
					ls ^= a[i];
			}
			if(ls!=0)  printf("Bob\n");
			else  printf("Alice\n");
		}
		else if(c==1 && d==0)
		{
			ls = 0;
			for(i=1;i<=n;i++)
			{
				if(b[i]==1 && a[i]>1)
				{
					if(a[i]%2==0)
						ls ^= 1;
				}
				else
					ls ^= a[i];
			}
			if(ls!=0)  printf("Bob\n");
			else  printf("Alice\n");
		}
	}
	return 0;
}

阅读更多

更多精彩内容