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

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;
}