C. Even Number Addicts

本人没学过博弈论
在https://zhuanlan.zhihu.com/p/569862415的指导下写一些自己的理解

首先我们可以想到的就是搜索！
最坏情况下应该是2^50次方
这样我们就可以用一些优化来暴力这道题
这里我们想到的是记忆化搜索
我们设dp[i][j][0/1][0/1]我们还剩i个偶数j个奇数Alex现在是0/1现在是0/1(Alex Bob)的回合并且表示这个状态下（Alex Bob）赢
这样显然是可以表示全的
我们思考转移 因为我们是搜索顺序 我们先考虑最终状态
要是我们当前Alex的回合 我们为偶数 显然是返回1 表示赢！
要是我们当前Alex的回合 我们为奇数 显然是返回0 表示输！
要是我们当前Bob的回合 我们为奇数 显然是返回1 表示赢！
要是我们当前Bob的回合 我们为偶数 显然是返回0 表示输！
当然我们递归回去的时候 就是另一个人的另一个状态 要是我们返回Bob输 那么Alex就一定赢
我们每次都play optically 显然我们要能抓住对面把柄 我们就直接抓住！
所以我们转移时直接|起来即可 别忘了因为传递给的是另一个人 显然我们要取一次反！

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
int dp[110][110][2][2];
bool dfs(int x,int y,int cur,int turn){
    int &v = dp[x][y][cur][turn];
    if(~v) return v;
    if(!x && !y) return !cur ^ turn;
    int res = 0;
    if(x) res |= !dfs(x - 1, y, cur, !turn);
    if(y) res |= !dfs(x, y - 1, cur ^ !turn, !turn);
    return v = res;
}
void solve() {
    int n;cin>>n;
    memset(dp,-1,sizeof dp);
    vector<int>a(n+1);
    int n1=0,n0=0;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        a[i]=x%2;
        a[i]?n1++:n0++;
    }
    puts(dfs(n0,n1,0,0)?"Alice":"Bob");
}
signed main(){
    fast
    int T;cin>>T;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}