UVA1500 Alice and Bob

Statement:

link

给 \(n\) 个数 \(a_1, a_2 ... ,a_n\)。先手 \(\rm Alice\) 和后手 \(\rm Bob\) 有两个操作。

1. \(del(i)\) 令 \(a_i = a_i - 1\)，必须满足 \(a_i > 0\)。

2. \(merge(i, j)\)，将 \(i, j\) 合并，必须满足 \(a_i, a_j > 0\)

若一个人不能进行操作，则判他输。若两人都足够聪明，问谁会获胜。

Solution:

首先分析没有 \(merge\) 操作的答案，令 \(sum = \sum_{i =1} ^ na_i\)，显然 \(sum\) 为奇数，则先手胜，否则后手胜。

加入 \(merge\) 操作后，可以发现如果先手遇到的是 \(sum\) 为偶数的情况，可以使用 \(merge\) 来将偶数的情况扔给后手。所以我们其实可以转化为判定 \(sum + n - 1\) 的奇偶性。

但是这个时候可以发现有一个特殊的数字会影响答案。就是 \(1\)。

如果你对一个 \(1\) 进行 \(del\)，相当于 \(merge\) 到了另一个 \(j\) 里，然后再进行 \(del\) 操作，这可以成为先手翻盘的关键。

于是我们发现有 \(1\) 的情况十分复杂，注意到这是一个公平组合游戏，于是我们就可以使用 \(\rm SG\) 函数来辅助解题。

观察到题目中 \(a\) 的值域和 \(n\) 都非常小，所以可以直接暴力的设 \(SG(cnt,s)\)，其中 \(cnt\) 是 \(1\) 的个数， \(s\) 是当前局面的 $ sum + n - 1$。

于是可以直接分类讨论转移。细节见下面代码：

Code:

#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 50 + 10, M = 1e3 + 10;
int n, INF; 

int sg[N][M * N];

bool SG(int cnt, int sum){
//	cout << cnt << " " << sum << "\n";
	int& ans = sg[cnt][sum];
	if(ans != INF) return ans;
	if(!cnt) return (ans = (sum & 1));
	if(sum == 1) return (ans = SG(cnt + 1, 0));
	// 1. mer(1, 1) 2.mer(2, 1) 3. mer(2, 2) 4. del(1) 5. del(2)
	ans = 1;
	if(cnt >= 2) ans &= SG(cnt - 2, sum + 2 + (sum ? 1 : 0));
	if(sum && cnt) ans &= SG(cnt - 1, sum + 1);
//	if(sum >= 2) ans &= SG(cnt, sum - 1);
	if(cnt >= 1) ans &= SG(cnt - 1, sum);
	if(sum >= 1) ans &= SG(cnt, sum - 1);
	ans ^= 1;  return ans; 
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T; cin >> T; memset(sg, 0x3f, sizeof sg); INF = sg[0][0];
	for(int t = 1; t <= T; t++){
		cin >> n; int cnt = 0, sum = 0;
		for(int i = 1; i <= n; i++){
			int a; cin >> a;
			if(a == 1) cnt++;
			else sum += a + 1;
		}
		if(sum) sum--;
		cout << "Case #" << t << ": " << (SG(cnt, sum) ? "Alice" : "Bob") << "\n";
	}
	
	return 0;
}