CF1396B题解

题目简述:

有两个人轮流取石子,每堆石子有 \(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");
    }
}
上一篇:2021牛客多校第四场G(容斥,组合计数)


下一篇:[loj6051]PATH