题解：UVA1500 Alice and Bob

1. 状态表示：

• 使用两个变量来表示当前游戏的状态：\(a\) 表示包含 \(1\) 个石子的堆的数量，\(b\) 表示包含多于 \(1\) 个石子的堆的可操作次数。

2. 游戏策略：

• 1. 从包含多个石子的堆中取走一个石子，这会减少 \(b\)。
• 2. 从包含 \(1\) 个石子的堆中取走一个石子，这会减少 \(a\)。
• 3. 合并两个包含 \(1\) 个石子的堆，变成一个包含多个石子的堆。这会减少 \(a\) 并增加 \(b\)。
• 4. 将一个包含 \(1\) 个石子的堆合并到包含多个石子的堆中，这会减少 \(a\) 并增加 \(b\)。

3. 临界情况：

• 如果当前所有堆中石子数量都为 \(1\)（\(a > 0\) 且 \(b = 0\)），那么最终会剩下一个石子，这时轮到操作的玩家输。
• 如果所有堆都包含多个石子，且可操作次数 \(b\) 为奇数，那么先手玩家有必胜策略。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,f[50][N];
//f[i][j]表示有i个1，大于1的堆有j此操作。
int dfs(int a,int b) {
	if(f[a][b]!=-1)return f[a][b];//记忆化
	if(!a)return f[a][b]=b%2;
	//若全是大于1的堆，b为奇数则先手必赢
	if(b==1)return dfs(a+1,0);//没有大于1的堆
	int t=2;
	if(b)t=min(t,dfs(a,b-1));//取走大于1的堆中一个元素
	if(a)t=min(t,dfs(a-1,b));//取走1的堆中一个元素
	if(a>1)t=min(t,dfs(a-2,b+2+(b?1:0)));//将两个1合并
	if(a&&b)t=min(t,dfs(a-1,b+1));//1合并到大于2的堆中
	if(!t)f[a][b]=1;
	else f[a][b]=0;
	return f[a][b];
}
int main() {
	int T;
	cin>>T;
	memset(f,-1,sizeof(f));
	for(int k=1; k<=T; k++) {
		int a=0,tot=0;
		cin>>n;
		for(int i=1; i<=n; i++) {
			int x;
			cin>>x;
			if(x==1)a++;
			else tot+=x+1;
		}
		if(tot)tot--;
		//可操作数==堆数+求和（堆中元素数）-1
		cout<<"Case #"<<k<<": ";
		if(dfs(a,tot))
			cout<<"Alice"<<endl;
		else cout<<"Bob"<<endl;
	}
}