题解 CF1396B 【Stoned Game】

SSerxhs · 2020-09-05 01:31:22 · 题解

对其他题解稍微补充一个证明

不妨设第 i 堆石子最多，sum=\sum\limits_{j\ne i}a_j

当 a_i>sum 时，先手只需要占住第 i 堆必胜

否则，考虑最终状态必定只有一堆石子，现证明双方都可以通过设定操作策略为取走目前可取的石子最多的那堆做到最后一堆石子被拿干净：

假设不被拿干净，必定是出现了最多石子的那堆石子数目大于其他之和的状态（例如最终状态），逆推回去可以发现每两次取石子就有一个人取了这堆，逆推至初始状态与“否则”矛盾，不成立

故 a_i\le sum 时最终状态必定是全部石子被取完，只需判断总石子数奇偶即可

#include <stdio.h>
int a[102];
int i,t,n,j,c;
int main()
{
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d",&n);
        for (i=1;i<=n;i++) scanf("%d",a+i);j=1;
        for (i=2;i<=n;i++) if (a[i]>a[j]) j=i;c=0;
        for (i=1;i<=n;i++) if (i!=j) c+=a[i];
        if ((a[j]>c)||((c^a[j])&1)) puts("T"); else puts("HL");
    }
}