题目描述
输入$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;
}