2020-2021:teams:manespace:2020_08_15-2020_08_21周报_week15
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:2020_08_15-2020_08_21周报_week15 [2020/08/20 23:39] quantumbolt 创建 |
2020-2021:teams:manespace:2020_08_15-2020_08_21周报_week15 [2020/08/21 18:15] (当前版本) iuiou |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| =====本周推荐===== | =====本周推荐===== | ||
| + | ====by iuiou==== | ||
| + | * **题源**：[[https://codeforces.com/contest/1398/problem/E]] | ||
| + | |||
| + | * **题意**：有火焰魔法和闪电魔法两种魔法，第i个魔法会对怪物产生$a_i$的伤害，一旦一个魔法跟在闪电魔法后面，则该魔法造成的伤害会翻倍。问累计一共能造成多少伤害？要求支持插入一个新魔法，和插入后即时查询得操作。 | ||
| + | | ||
| + | * **知识点**:set,贪心 | ||
| + | | ||
| + | * **题解**：首先可以确定的一点是，当前只要存在火焰魔法，假设现在一共有$k$个闪电魔法，则一共会有$k$次翻倍的机会，如果没有火焰魔法则只有$k-1$次翻倍机会。可以用set维护两个数组一个是可以翻倍得数，还有一个是一倍的数，再维护一下火焰魔法，之后每次操作先按照要求删去或者添加，添加时比对一倍的最大数，若比它小则加入，若比他大则加入两倍的数组。每次操作完之后，比对闪电魔法的数量和翻倍数组中数的数量，多减少补，最后比较火焰魔法最大$a_max$(若没有则为0)和翻倍魔法最小$b_min$的大小，若翻倍魔法最小大，则需要减去$b_{min}-a_{max}$,因为最小的闪电魔法无法被算进去。否则则不用算，因为最小的闪电魔法一定不会被算进去。输出答案即可。 | ||
| =====团队训练===== | =====团队训练===== | ||
| 行 13: | 行 21: | ||
| ====比赛==== | ====比赛==== | ||
| - | * | + | * [[Edu round 93]] |
| ====题目==== | ====题目==== | ||
2020-2021/teams/manespace/2020_08_15-2020_08_21周报_week15.1597937966.txt.gz · 最后更改: 2020/08/20 23:39 由 quantumbolt
