Partitioning Game (SG函数)

喜欢ヅ旅行 2022-07-28 12:38 176阅读 0赞

Partitioning Game ：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=112620\#problem/D][http_acm.hust.edu.cn_vjudge_contest_view.action_cid_112620_problem_D] 传送门：nefu

题面描述：

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

Submit [Status][]

Description

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

1. Initially there are **n** piles.

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 integer **T (≤ 1000)**, denoting the number of test cases.

Each case starts with a line containing an integer **n (1 ≤ n ≤ 100)**. The next line contains **n** integers, where the ith integer denotes the number of cells in the ith pile. You can assume that the number of cells in each pile is between **1** and **10000**.

Output

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

Sample Input

1 2 3

Sample Output

Case 1: Bob

Case 2: Alice

Case 3: Bob

题目大意：

n堆物品，每堆物品有多个组成，Alice和Bob轮流依次对这些物品进行操作，每次都要把其中一堆物品分成不同的个数，最后一个没办法再进行操作的人输掉比赛。

题目分析：

由于每一堆物品的分割都是相互独立的，所以我们可以用SG函数来处理，先计算一堆的，对于一个由a件物品组成的堆，可以分割的后继方法有（1，a-1），（2，a-2），（3，a-3），……，（（a-1）/2，a-（a-2）/2）；

由于由同一堆分割好的两堆也是相互独立的，所以再用SG定理，得到：SG(x)=mex\{SG(1)^SG(a-1),  SG(2)^SG(a-2), SG(3)^SG(a-3), ... ,SG((a-1)/2)^SG(a-(a-1)/2)\};

则最后的答案是：SG(a1)^SG(a2)^SG(a3)^...^SG(an);

代码实现：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    int hashsz[10010],sg[10010];
    void getsg()
    {
        memset(sg,0,sizeof(sg));
        for(int i=1;i<=10000;i++) ///sg[0]=0;
        {
            memset(hashsz,0,sizeof(hashsz));
            for(int j=1;j+j<i;j++)
            {
                hashsz[sg[j]^sg[i-j]]++;
            }
            for(int j=0;j<=10000;j++)
            if(!hashsz[j])
            {
                sg[i]=j;
                break;
            }
        }
    }
    
    int main()
    {
        getsg();
        int t,n,a,casenum=0;
        int ans;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            ans=0;
            for(int i=0;i<n;i++)
            {
                scanf("%d",&a);
                ans=ans^sg[a];
            }
            if(ans)
            printf("Case %d: Alice\n",++casenum);
            else
            printf("Case %d: Bob\n",++casenum);
        }
        return 0;
    }

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