嘘~ 正在从服务器偷取页面 . . .

CF1396B Stoned Game 题解

发布日期: 2024-01-20

更新日期: 2024-01-20

文章字数: 426

CF1396B Stoned Game 题解

题意：

有 \(n~(1 \le n \le 100)\) 堆石子，每堆分别有 \(a_i~(1 \le n \le 100)\) 个石子。

两者轮流取其中一个石子。但不能取上次对手取过的那一堆。特殊的，第一次取可以取任何一堆的石子。

当前先手取完要取的石子之后使对手无路可走时，先手获胜。

\(T(T \le 100)\) 组数据，每组数据给出 \(n\) 和 \(a\) ，输出谁必会胜利。若先手胜利输出 T，若后者胜利输出 HL。

萌萌的博弈论题。

设最大的那一堆为 \(a_p\) ，并记 \(S = (\sum_i a_i) - a_p\) 。

当 \(a_p > S\) 时，显然先手必胜
否则，\(a_p\) 一定被全取完，同时 \(S \gets S - a_p\) 。

然而这并没有改变 \(S\) 的性质，也就是说，一定还剩下一堆最大的，先手依然会选择它。

因此其实这道题几乎只需要判断奇偶性即可。

时间复杂度 \(\mathcal{O}(T\cdot n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int n,p,c,a[114];
void solve()
{
    cin >> n; p = 1; c = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 2; i <= n; i++) if(a[i] > a[p]) p = i;
    for(int i = 1; i <= n; i++) if(i != p) c += a[i];
    if((a[p] > c) || ((c ^ a[p]) & 1)) cout << "T\n"; else cout << "HL\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}