题目描述

输入$T(≤100)$表示$T$组数据。每组数据输入$n(1≤n≤100)$和长为$n$的数组$a(-1e9<a[i]≤1e9)$。$Alice$和$Bob$轮流从$a$中取数,$Alice$先。游戏直到$a$为空时停止。如果$Alice$所取数字之和为偶数，输出$Alice$，否则输出$Bob$。

样例

输入样例1

4
3
1 3 5
4
1 3 5 7
4
1 2 3 4
4
10 20 30 40

输出样例1

Alice
Alice
Bob
Alice

算法1

(枚举+sg函数) $O(n^2)$

这道题目在博弈论中是一道典型的取石子问题，在处理这一类问题时，数据量不大的情况下有一种通用的做法，就是用sg函数，处理每一次取石子的情况，有点类似于记忆化搜索。
这道题的数据量比较小，可以使用记忆化搜索。记录每一种情况下Alice是否获胜，枚举每一种情况，dfs中第一位是奇数的个数，第二位是偶数的个数，第三位是当前Alice当前取到的数mod2，因为我们只需要知道是奇是偶就够了，第四位是当前是谁取数。
如果当前是Alice取数，那么有两种可能，取奇数或者取偶数，只要结果有一种为true，结果就为true；如果当前为Bob取数，只要结果有一种为false，那么结果就为false。

C++ 代码

#include<bits/stdc++.h>

#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 110, M = N * 2, INF = 0x3f3f3f3f;

int n, m;
int w[N];
int st[N][N][2][2];

inline int dfs(int odd, int even, int s, int own)
{
    if(st[odd][even][s][own]!=-1) return st[odd][even][s][own];
    int f1=-1, f2=-1;
    if(odd){
        int t = s;
        if(own==0) t = (t+1)%2;
        f1 = dfs(odd-1, even, t, own^1);
    }
    if(even){
        f2 = dfs(odd, even-1, s, own^1);
    }
    if(own==0)
        if(f1==1 || f2==1) st[odd][even][s][own]=1;
        else st[odd][even][s][own]=0;
    else
        if(f1==0 || f2==0) st[odd][even][s][own]=0;
        else st[odd][even][s][own]=1;
    return st[odd][even][s][own];
}

inline void solve()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>w[i];
    int odd = 0, even = 0;
    for(int i=0;i<n;i++)
        if(w[i]%2) odd++;
        else even++;
    if(dfs(odd, even, 0, 0)) cout<<"Alice"<<endl;
    else cout<<"Bob"<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    memset(st, -1, sizeof st);
    for(int i=0;i<2;i++) st[0][0][0][i]=true, st[0][0][1][i]=false;
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

    return 0;
}

算法2

(分类) $O(n)$

$odd$表示奇数的个数，$even$表示偶数的个数。
我们可以直接分类讨论。如果$(odd+1)/2%2==0$，那么$Alice$一定赢；如果$odd$是偶数或者$even$是偶数，那么一定是$Bob$赢，其余情况都是$Alice$赢。下证此做法正确。
如果$(odd+2)/2=k$，$k%2$为0，如果$even$是偶数，$Alice$先取奇数，之后$Bob$取什么数，$Alice$取什么数，那么奇数先取完的话，$Alice$已经赢了，因为$Alice$取了偶数对奇数，并且剩下的全是偶数；如果是偶数先取完的话，那么一定是$Alice$拿到了最后一个偶数，结局又回到了轮流拿奇数的情况，最终$Alice$拿到了$k$个奇数。如果$even$是奇数，那么$Alice$还是先拿偶数，这样偶数的个数就变成偶数，接下来$Bob$拿什么，$Alice$拿什么，并且$Alice$拿到的奇数个数为$k$个。
如果偶数的个数和奇数的个数都为奇数的话，$Alice$先拿偶数，接下来$Bob$拿什么，$Alice$拿什么，最后$Alice$一定拿了偶数个奇数。
如果偶数的个数为偶数，或者奇数的个数为偶数，无论$Alice$先取什么，$Bob$都和$Alice$取一样的，最后$Alice$只能取到奇数个奇数

C++ 代码

#include<bits/stdc++.h>

#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 110, M = N * 2, INF = 0x3f3f3f3f;

int n, m;

inline void solve()
{
    int odd = 0, even = 0;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(x%2) odd++;
        else even++;
    }
    if((odd+1)/2%2==0 || odd%2 && even%2) cout<<"Alice"<<endl;
    else cout<<"Bob"<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

    return 0;
}