Misere Nim （Nim博弈）

- 日理万妓 2022-07-28 09:46 151阅读 0赞

Misere Nim （Nim博弈）：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=112620\#problem/B][http_acm.hust.edu.cn_vjudge_contest_view.action_cid_112620_problem_B] 传送门：nefu

题面描述：

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

Submit [Status][]

Description

Alice and Bob are playing game of **Misère Nim**. Misère Nim is a game playing on **k** piles of stones, each pile containing one or more stones. The players alternate turns and in each turn a player can select one of the piles and can remove as many stones from that pile unless the pile is empty. In each turn a player must remove at least one stone from any pile. Alice starts first. The player who removes the last stone **loses** the game.

Input

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

Each case starts with a line containing an integer **k (1 ≤ k ≤ 100)**. The next line contains **k** space separated integers denoting the number of stones in each pile. The number of stones in a pile lies in the range **\[1, 109\]**.

Output

For each case, print the case number and **'Alice'** if Alice wins otherwise print **'Bob'**.

Sample Input

2 3 4 5

1 1 2 4 10

Sample Output

Case 1: Bob

Case 2: Alice

Case 3: Bob

题目大意：

在K堆石子的任意堆中任取>0个石子，Alice为先手，Bob为后手，先取完者输掉比赛。

题目分析：

此题满足Nim博弈的条件，：1、有两名选手；2、两名选手交替对游戏进行移动(move)，每次一步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动；3、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素； 4、如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负。根据这个定义，很多日常的游戏并非ICG。例如象棋就不满足条件3，因为红方只能移动红子，黑方只能移动黑子，合法的移动集合取决于轮到哪名选手操作。

此题属于Nim博弈的第二种题型，其中属于必胜点的情况有：S1，S2，T0（即非奇异形式下，充裕点的个数>0个和奇异形式下，充裕点的个数==0个）；属于必败点的情况有：S0，T2。

代码实现：

#include <iostream>
    
    using namespace std;
    
    long long data;
    int main()
    {
        int t,num,ans,k;
        int casenum=0;
        cin>>t;
        while(t--)
        {
            num=0;
            ans=0;
            cin>>k;
            for(int i=0;i<k;i++)
            {
                cin>>data;
                if(data>=2)
                num++;    //充裕堆的数量
                ans=ans^data;
            }
            if((ans!=0&&num!=0)||(ans==0&&num==0))  //S1,S2,T0必胜
            cout<<"Case "<<++casenum<<": Alice"<<endl;
            else
            cout<<"Case "<<++casenum<<": Bob"<<endl; //S0,T2必败
        }
        return 0;
    }

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