CF1396B Stoned Game

心路历程：

手玩的时候十分钟猜出要分奇偶，然后看错的样例想出另一个特判点，15分钟爆切，最后才知道为啥要分奇偶。

让我们来手玩几组样例吧！

2                  2                2              3

1 1 后手赢   1 2 先手赢 2 2后手赢 1 1 1 先手赢

注意到%2==0 就是后手赢，否则先手赢。

特判点1(样例看出)：

1

2

注意到如果只有一个数，肯定是先手赢，因为后手无法取先手取的第一堆石子，所以后手啥也取不了。

特判点2(上面两个点写完后你会wrong answer test 4):

看这样两组样例。

3                     3

1 1 4(先手赢)  1 1 2(后手赢)

那为什么和都为偶数赢的人不一样呢？

我们来看第一个先手是怎么赢得(以下记a为先手取的,b为后手取的)：

3

1 1 4

      a

b     

      a

b   

      a

b取不了了。

取法就是先手一直取最多的那一堆，让后手最后把剩下的都取完了，只剩最多的那一堆，让后手因为只剩一堆以及先手已经取过了，所以后手就输了。

所以在 %2==0的情况下，先手也可能赢，如下：

max(a[i])>-max(a[i]),也就是最大值大于剩下的值的和。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5;
int T,n,a[N];
int main(){
scanf("%d",&T);
while(T–){
int res=0,mx=INT_MIN;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
res+=a[i];
mx=max(mx,a[i]);
}
if(n==1){
printf("T\\n");
continue;
}
if(mx>(res-mx)){
printf("T\\n");
continue;
}
if(res%2==0){
printf("HL\\n");
}else printf("T\\n");
}
return ~(-1);
}