Yet Another Game of Stones

Time limit:1000ms Memory limit:65536kB

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 ai stones and a special constraint indicated as bi.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 bi of that pile.If bi = 0, there are no constraints.If bi = 1, Alice can only remove some odd number of stones from that pile.If bi = 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 ≤ 105), indicating the number of piles.The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 109), indicating the number of stones in each pile.The third line of each test case contains n integers b1, b2, …, bn (0 ≤ bi ≤ 2), indicating the special constraint of each pile.It is guaranteed that the sum of n over all test cases does not exceed 106.
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

Hint

For the first test case, Alice can remove 3 stones from the first pile, and then she will win the game.
For the second test case, as Alice can only remove some even number of stones, she is unable to remove all the stones in the first move. So Bob can remove all the remaining stones in his move and win the game.
For the third test case, Alice is unable to remove any number of stones at the beginning of the game, so Bob wins.


题意

        一共有n堆石子,每堆石子有ai个,每堆石子都一个限制bi,对于bob来说每次可以取任意一堆石子的任何个,但是对于alice来说当bi=0时可以取这一堆石子的任何个,当bi=1的时候只能取奇数个,当bi=2的时候只能取这一堆石子的偶数个,每局游戏都是alice先手,问谁是必胜策略。

思路

        我们对于每堆于alice有限制的石子进行考虑(即bi=1和bi=2的)。对于存在任意一堆石子的bi=2且有奇数个,此时alice永远不能取完这一堆石子,而bob可以,那么bob时必胜的。如果仅仅存在某一堆石子bi=1且这一堆石子有奇数个时,alice必须一次性全部拿走,否则就相当于给了bob一次改变尼姆博弈状态的机会;如果仅仅存在某一堆石子bi=2且这一堆石子为偶数个时,那么alice必须一次性把这堆石子取省1个,否则也是给了bob一次改变尼姆博弈状态的机会;如果存在某一堆石子bi=2且为偶数个时,alice需要一次性全部取走,否则bob可以取成奇数个使得alice必败。对于以上三种情况至多只出现一堆石子符合,否则alice对一堆进行操作,bob便可以改变尼姆博弈的状态。那么结论是:若必败状态存在就可以直接判定游戏结果;三种状态存在两堆及以上是可以直接判定游戏结果;三种状态存在一堆时可以变成alice解决了特殊状态后的bob先手的尼姆博弈;三种状态一个也不存在的时候是简单的尼姆博弈。然后就可以写代码啦。


代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 1e5+5;
int ar[maxn];
int br[maxn];
bool vis[maxn];

int main ()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        memset(vis, 0, sizeof(vis));
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
        {
            scanf("%d", &ar[i]);
        }
        for (int i = 0; i < n; ++i)
        {
            scanf("%d", &br[i]);
        }
        bool bul = 0;
        int sum1 = 0;
        int sum2 = 0;
        for (int i = 0; i < n; ++i)
        {
            if (br[i] == 2 && ar[i] % 2 == 1)
            {
                bul = 1;
                break;
            }
            if (br[i] != 0 && ar[i] % 2 == 0)
            {
                vis[i] = 1;
                ++sum1;
            }
            if (br[i] == 1 && ar[i] % 2 == 1 && ar[i] > 1)
            {
                vis[i] = 1;
                ++sum2;
            }
        }
        if (bul || sum1+sum2 >= 2)
        {
            cout << "Bob" << '\n';
        }
        else
        {
            if (sum2 == 1)
            {
                int v = 0;
                for (int i = 0; i < n; ++i)
                {
                    if (!vis[i])
                    {
                        v ^= ar[i];
                    }
                }
                if (v == 0)
                {
                    cout << "Alice" << '\n';
                }
                else
                {
                    cout << "Bob" << '\n';
                }
            }
            else if (sum1 == 1)
            {

                int v = 0;
                for (int i = 0; i < n; ++i)
                {
                    if (!vis[i])
                    {
                        v ^= ar[i];
                    }
                    else
                    {
                        if (br[i] == 1)
                        {
                            v ^= 1;
                        }
                    }
                }
                if (v == 0)
                {
                    cout << "Alice" << '\n';
                }
                else
                {
                    cout << "Bob" << '\n';
                }
            }
            else
            {
                int v = 0;
                for (int i = 0; i < n; ++i)
                {
                    v ^= ar[i];
                }
                if (v == 0)
                {
                    cout << "Bob" << '\n';
                }
                else
                {
                    cout << "Alice" << '\n';
                }
            }
        }
    }
    return 0;
}

发表评论