题目简述:
有两个人轮流取石子,每堆石子有 \(a_i\) 个,两人不能连续取同一堆石子,求必胜者
思路:
首先考虑先手必胜的部分情况,显然如果存在 \(a_j\) 大于 \(\prod_{i=1}^n a_i - a_j\) ,则先手只需要一直取这堆,后手就会一直把其他的所有石子取光,显然只有最大值可能出现这种情况(毕竟已经大于总和的一半了),判断最大值是否满足即可;
考虑其他情况,因为两人都采用最优策略,所以如果不存在 \(a_j\) 大于 \(\prod_{i=1}^n a_i - a_j\) ,必然不会在游戏过程中出现 \(a_j\) 大于 \(\prod_{i=1}^n a_i - a_j\) 的情况,只能看谁取走了最后一个石子,判断 \(\prod_{i=1}^n a_i\) 的奇偶即可。
代码:
int main()
{
int t=read();
int n,a[105],tot,maxn;
while(t--)
{
n=read(),tot=0,maxn=-1;
for(int i=1;i<=n;i++)
{
a[i]=read();
tot+=a[i];
maxn=max(maxn,a[i]);
}
if(maxn>tot-maxn) puts("T");
else if(tot%2==0) puts("HL");
else puts("T");
}
}