0%

[CF1396B] Stoned Game

题目

题目链接

题目大意: $t$ 组数据. 有 $n$ 堆石子, 每个人可以选择一个上一回合中未被选中的堆拿走一个石子, 最终不能操作的那个人输, 问谁有必胜策略. $1 \le t, n, a_i \le 100$.

思路

如果存在 $i$ 满足 $\sum \limits_{j \ne i} a_j < a_i$, 显然先手一直取 $a_i$ 这一堆就能胜利.

如果不存在, 显然所有石子最后一定会被拿完.

那么只需要判断 $\sum a_i$ 的奇偶性就行了.

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef unsigned long long uLL;
typedef long long LL;

int a[110];
int T, n, s, max, pos;

int main() {
read(T);
while (T--) {
read(n);
pos = max = s = 0;
for (int i = 1; i <= n; ++i) {
read(a[i]);
if (a[i] > max) max = a[i], pos = i;
s += a[i];
}
if (a[pos] > s - a[pos]) {
puts("T");
} else if (s & 1) {
puts("T");
} else puts("HL");
}
return 0;
}