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