Stoned Game

tech2022-09-15  82

努力也成功不了的话也太心酸了啊

题目地址

题目挺好的,就是想不出来。

这道题目有点博弈论的意思,一般没有学过博弈论的话是很难想出来博弈论的题目的,基本上是不可能的。

但是这道题目好像没有博弈论那种味,仔细分析下还是可以的。

题目大意,给你n堆石子,每轮玩家可以选择某一堆石子然后拿走其中一个石子,其中在每轮游戏中玩家不能选择同一堆石子,到最后那位玩家动不了就是失败。

思路:我们首先想假设有一堆石子数量特别多,其余的堆石子的数量特别少,那么先手拿的人肯定是赢的(因为它可以死赖在这堆石子上),那么剩下的情况呢,我们想一下我们是否能够给双方玩家构造一种选择方式使得玩家在这种方式下一定能够将石子全部取完。这里我想了一个方式,对于先手玩家来说,我们一直在数量最多的堆上选,按照这种想法接下去无论后手怎样选择,我们一定会选择完所有的堆。(求证明呜呜呜 || 求推翻),对于后手来说,我们也是一样的套路,假设前手不选择最多的那一堆,那么我们就选择最多的那一堆,否则我们随便选择一堆就可以。

代码:

#include <iostream> #include <cstring> #include <map> #include <vector> #include <algorithm> using namespace std; const int N = 1e5 + 10; int a[N]; int main() { int T; scanf ("%d", &T); while (T --) { int n; scanf ("%d", &n); int sum = 0; for (int i = 1; i <= n; i ++) { scanf ("%d", a + i); sum += a[i]; } int Max = *max_element (a + 1, a + 1 + n); if (Max > sum - Max || sum & 1) { puts ("T"); } else puts ("HL"); } return 0; }
最新回复(0)