题目
Alice和Bob两个好朋友又开始玩取石子了。
游戏开始时,有(n)堆石子排成一排,然后他们轮流操作(Alice先手),每次操作时从下面的规则中任选一个:
·从某堆石子中取走一个
·合并任意两堆石子
不能操作的人输。Alice想知道,她是否能有必胜策略。
分析
如果不存在大小为1的石堆,则操作次数一定被控制为(sum+n-1),判断奇偶性即可,
若存在大小为1的石堆,它有五种后继状态
- 直接取走大小为1的石堆
- 直接取走大小超过1的石堆中的一颗石子
- 将大小为1的石堆合并至大小超过1的石堆
- 合并两个大小超过1的石堆(不会影响操作次数)
- 将两个大小为1的石堆合并为1个石堆
根据5个后继状态SG函数值求出该状态的SG函数值即可
代码
#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
using namespace std;
int sg[51][60011],Test;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline signed min(int a,int b){return a<b?a:b;}
inline signed dfs(int one,int sum){
if (~sg[one][sum]) return sg[one][sum];
if (!one) return sg[one][sum]=sum&1;
if (sum==1) return sg[one][sum]=dfs(one+1,0);//全都是1
rr int MEX=dfs(one-1,sum);
if (sum) MEX=min(MEX,dfs(one,sum-1));
if (one>1) MEX=min(MEX,dfs(one-2,sum+2+(sum>0)));//合并两堆大小为1的石子
if (sum) MEX=min(MEX,dfs(one-1,sum+1));//将大小为1的石堆与大小超过1的石堆合并
return sg[one][sum]=MEX^1;
}
signed main(){
memset(sg,-1,sizeof(sg)),Test=iut();
for (rr int i=1;i<=Test;++i){
rr int one=0,sum=0;
for (rr int T=iut();T;--T){
rr int x=iut();
if (x==1) ++one;
else sum+=x+1;
}
sum-=(sum>0),dfs(one,sum);
printf("Case #%d: ",i);
puts(sg[one][sum]?"Alice":"Bob");
}
return 0;
}