LIGHT OJ 1199 - Partitioning Game

傳送門

 

1199 - Partitioning Game PDF (English) Statistics Forum Time Limit:4 second(s) Memory Limit:32 MB

Alice and Bob are playing a strange game. The rules of the game are:

1.Initially there arenpiles.

2.A pile is formed by some cells.

3.Alice starts the game and they alternate turns.

4.In each tern a player can pick any pile and divide it into two unequal piles.

5.If a player cannot do so, he/she loses the game.

Now you are given the number of cells in each of the piles, you have to find the winner of the game if both of them play optimally.

Input

Input starts with an integerT (≤ 1000), denoting the number of test cases.

Each case starts with a line containing an integern (1 ≤ n ≤ 100). The next line containsnintegers, where the i^thinteger denotes the number of cells in the i^thpile. You can assume that the number of cells in each pile is between1and10000.

Output

For each case, print the case number and'Alice'or'Bob'depending on the winner of the game.

Sample Input

Output for Sample Input

3

1

4

3

1 2 3

1

7

Case 1: Bob

Case 2: Alice

Case 3: Bob

Explanation

In case 1, Alice has only 1 move, she divides the pile with 4 cells into two unequal piles, where one pile has 1 cell and the other pile has 3 cells. Now it's Bob's turn. Bob divides the pile with 3 cells into two piles, where one pile has 1 cell and another pile has 2 cells. So, now there are three piles having cells 1, 1, 2. And Alice loses, since she doesn't have any moves now.

  題目大意：

有n堆石子(1<=n<=100)，每一堆分別有ai個石子(1<=ai<=10000)，一次操作可以使一堆石子變成兩堆數目不相等（注意是不相等）的石子，最後不能操作就算輸，問先手贏還是後手贏。

解題思路:

就是一個SG函數，提到SG函數這個就是求一下 當前狀態的下一個狀態，又因為 這 n 堆石子是相互獨立的，沒有影響 所以說 可以開用SG函數，

根據SG定理，假設 當前堆中有 m塊石子 那麼他的下一狀態就可能有{1,m-1},{2,n-2},...,{(m-1)/2,m-(m-1)/2}（把每一種情況都想到 並且分析出來），

然後分完的那些 a和b塊石子又可以進行分，以此類推，那麼SG(x) = mex{ SG(1)^SG(x-1), SG(2)^SG(x-2),..., SG((x-1)/2)^SG(x-(x-1)/2) }，

然後我們要求的就是 SG[a[0]]^SG[a[1]]^...^SG[a[n-1]],如果結果是0就是 後手贏，否則 先手贏

My Code：

#include 
#include 
#include 
using namespace std;
const int MAXN = 10000+5;
int sg[MAXN];
int hash[MAXN];
void Get_sg()///模板
{
    memset(sg, 0, sizeof(sg));
    for(int i=1; i