2022暑期杭电多校第一场1012Alice and Bob（博弈论）

问题描述

爱丽丝和鲍勃喜欢玩游戏。
有m写在黑板上的数字，所有这些都是介于0和n.
游戏规则如下：
如果黑板上还有数字，并且没有带值的数字0在黑板上，爱丽丝可以将黑板上剩余的数字分成两组。
Bob 选择其中一组并擦除该集中的所有数字。然后将所有剩余的数字减去一。
在任何时候，如果有一个值为0在黑板上，爱丽丝获胜;否则，如果黑板上的所有数字都被擦除，则鲍勃获胜。
请确定如果爱丽丝和鲍勃都以最佳方式玩游戏，谁将赢得游戏。

输入

第一行包含整数T(T≤2000)- 测试用例的数量。
每个测试用例的第一行包含单个整数n（1≤∑n≤106).
每个测试用例的第二行包含n+1整数一个0,一个1,一个2。。。一个n(0≤一个我≤106，∑一个我=m)— 有一个我带值的数字我在黑板上。

输出

对于每个测试用例，如果爱丽丝将赢得游戏，请打印“Alice”，否则打印“Bob”。 

示例输入

2

1

0 1

1

0 2

示例输出

Bob

Alice

思路：站在Alice的角度想，为了保存更多的数字她必定要把数字尽可能均分，这样在Bob消除后Alice得到的i-1的个数至少是a[i]/2（也就是至少有一半（下取整）个数可以转移到i-1）

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
const int mod=1e9+7;
const int N=1e6+5,M=15;
typedef long long LL;
typedef pair<double,double> PDD;
LL a[N];
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=0 ; i<=n ; i++ ) cin>>a[i];
		for(int i=n;i>0;i--){
			a[i-1]+=a[i]/2;
		}
		if(a[0]) puts("Alice");
		else puts("Bob");
	}
	return 0;
}