暑假集训Day10 H (博弈论)

题目链接在这里:Problem - H - Codeforces

这个题因为数据不大,可以用贪心去模拟做。就是每一个人都不让对方在剩余的大堆里拿石子,所以每一个人都在自己所能拿到的最大堆里拿(类似于保护这个堆不让别人拿)

正解的博弈论我们先讨论特殊情况,就是有一堆比剩下所有的都大,那只要有一个人一直拿这个堆的石子就能赢。

一般情况下,为了避免这种情况的发生,一定会让每个堆同时的减下去,也就是说,到最后每个堆的石子数是相等的,不用考虑是否是一个堆的情况,只用考虑整个总数的奇偶就行了。

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=105;
 4 int t,n,a[MAX],an;
 5 priority_queue <int> q;
 6 int main(){
 7     freopen ("h.in","r",stdin);
 8     freopen ("h.out","w",stdout);
 9     int i,j,la,zt;
10     scanf("%d",&t);
11     while (t--){
12         scanf("%d",&n);
13         for (i=1;i<=n;i++) scanf("%d",&a[i]);
14         while (!q.empty()) q.pop();
15         for (i=1;i<=n;i++) q.push(a[i]);
16         an=la=0;
17         while (!q.empty()){
18             zt=q.top();q.pop();
19             zt--;
20             if (la!=0) q.push(la);
21             la=zt;
22             an++;
23         }
24         if (an%2==1) printf("T
");
25         else printf("HL
");
26     }
27     return 0;
28 }
未来是什么样,未来会发生什么,谁也不知道。 但是我知道, 起码从今天开始努力, 肯定比从明天开始努力, 要快一天实现梦想。 千里之行,始于足下! ——《那年那兔那些事儿》
原文地址:https://www.cnblogs.com/keximeiruguo/p/15054218.html