2020.7.12 2020牛客暑假多校训练营（第一场） prob:4/7/10 rank:56/1115

2020.7.13 2020牛客暑假多校训练营（第二场） prob:4/9/11 rank:162/1158

LCA问题

2020.07.11 AIsing Programming Contest 2020 prob:4/5/6 rank:933

• Educational Codeforces Round 91 C - Create The Teams
  • 分类：贪心
  • 题目大意：有$n$个程序员要进行分组，每个程序员有能力值$a_i$，现在要求一个组能力值最低的程序员的能力乘以总人数至少要有$x$，问最多能分几个组
  • 数据范围：多组数据，$T \le 1000$，$1 \le n \le 10^5$，$1 \le a_i,x \le 10^9$
  • 解题思路：显然每个组人越少越好，所以我们从大到小开始贪心，能一个人就一个人，不能就看能不能两个人、三个人，以此类推即可，时间复杂度$O(n \log n)$
  • Comment：比较简单的贪心题
• Educational Codeforces Round 91 D - Berserk And Fireball
  • 分类：分类讨论，模拟
  • 题目大意：有$n$个士兵排成一排，每个士兵有能力值$a_i$且各不相同，你可以进行两种操作，一种是花费$x$消灭连续的$k$个士兵，一种是花费$y$使两个相邻的士兵中能力值较低的被消灭，问能不能把给出的士兵消灭成特定位置的士兵留下来的排列，如果能，最小化花费
  • 数据范围：$1 \le k \le n \le 2 \times 10^5$，$1 \le x,y \le 10^9$
  • 解题思路：由于保证了士兵能力值各不相同，我们先确定哪些士兵被留下了，然后以区间的形式消灭不留下的。对于一个区间，如果长度小于$k$，那么区间两端的值必须有一个大于最大值，否则删不干净，这时只能用第二种操作。如果区间长度大于等于$k$要分类讨论，如果$y \times k < x$，那么显然应该用最大值一直删，否则把区间长度删成$k$的倍数然后删光，这时还是要判断能不能用最大值删干净，如果不行就必须删到只剩$k$然后用一次第一种操作
  • Comment：题目本身的操作并不是很难，只要从士兵能力值各不相同的条件能够想到以区间为单位删掉不用留下的士兵，接下来就只需要注意细节了

林星涵：

陶吟翔：

郭衍培：