Again Stone Game （通过SG函数找规律）

旧城等待， 2022-07-29 11:41 140阅读 0赞

Again Stone Game （通过SG函数找规律）：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=112620\#problem/F][http_acm.hust.edu.cn_vjudge_contest_view.action_cid_112620_problem_F] 传送门：nefu

题面描述：

**Time Limit:**2000MS **Memory Limit:**32768KB **64bit IO Format:**%lld & %llu

Submit [Status][]

Description

Alice and Bob are playing a stone game. Initially there are **n** piles of stones and each pile contains some stone. Alice stars the game and they alternate moves. In each move, a player has to select any pile and should remove at least one and no more than half stones from that pile. So, for example if a pile contains 10 stones, then a player can take at least 1 and at most 5 stones from that pile. If a pile contains 7 stones; at most 3 stones from that pile can be removed.

Both Alice and Bob play perfectly. The player who cannot make a valid move loses. Now you are given the information of the piles and the number of stones in all the piles, you have to find the player who will win if both play optimally.

Input

Input starts with an integer **T (≤ 100)**, denoting the number of test cases.

Each case starts with a line containing an integer **n (1 ≤ n ≤ 1000)**. The next line contains **n** space separated integers ranging in **\[1, 109\]**. The **ith** integer in this line denotes the number of stones in the **ith** pile.

Output

For each case, print the case number and the name of the player who will win the game.

Sample Input

10 11 12

1 2 3 4 5

4 9

1 3 9

Sample Output

Case 1: Bob

Case 2: Alice

Case 3: Alice

Case 4: Bob

Case 5: Alice

题目大意：

同样为n堆石子取石子的游戏，但是此题在取石子时加上了附加条件，取石子时只能取的个数为1~n/2个，最后一个取完石子后不能再取的人赢得比赛。

题目分析：

每堆石子的取法都是相互独立的，这样就属于SG函数的题目，要根据后继出现的情况去打表计算SG函数，但是每一堆石子的数目太多，正常去打表计算SG函数的话肯定不行，所以应该去找规律，通过打表找规律。

最后得到结论如下：

当n为偶数的时候，n要一直除以2，一直到n为偶数为止，sg(n)=n/2;

当n为奇数的时候，sg(n)=sg(n/2);

代码实现：

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        int t,n,a,casenum=0;
        int ans;
        cin>>t;
        while(t--)
        {
            cin>>n;
            ans=0;
            for(int i=0;i<n;i++)
            {
                cin>>a;
                while(a&1) a/=2;
                ans^=a/2;
            }
            if(ans)
                cout<<"Case "<<++casenum<<": Alice"<<endl;
            else
                cout<<"Case "<<++casenum<<": Bob"<<endl;
        }
        return 0;
    }

[http_acm.hust.edu.cn_vjudge_contest_view.action_cid_112620_problem_F]: http://http://acm.hust.edu.cn/vjudge/contest/view.action?cid=112620#problem/F
[Status]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=112620#status//F/0