HDU_7149

链接

• 点此跳转
• 参考

思路

考虑 $Alice$ 。

对于一个数 $i$ ，如果当前只存在若干这个 $i$ ，那么至少要 $2^i$ 个数，$Alice$ 才会获胜。

如果存在不同的数，只需要使 ${\sum }_{i=0}^n\frac{a_i}{2^i}\ge 1$ 即可，即从后向前扫一遍，判断 $a[0]$ 是否大于 $0$ 。

代码

// #pragma GCC optimize(3)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define endl '\n'
#define fi first
#define se second
#define PI acos(-1)
// #define PI 3.1415926
#define LL long long
#define INF 0x3f3f3f3f
#define lowbit(x) (-x&x)
#define PII pair<int, int>
#define ULL unsigned long long
#define PIL pair<int, long long>
#define mem(a, b) memset(a, b, sizeof a)
#define rev(x) reverse(x.begin(), x.end())
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;

const int N = 1e6 + 10;

int n;
int a[N];

void solve() {
	int tt;
    cin >> tt;
    while (tt -- ) {
    	cin >> n;
    	for (int i = 0; i <= n; i ++ ) {
    		cin >> a[i];
    	}	
    	for (int i = n; i; i -- ) {
    		a[i - 1] += a[i] / 2;
    	}
    	if (a[0]) puts("Alice");
    	else puts("Bob");
    }
}

int main() {
	IOS;
	
	solve();
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63