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:12] iuiou |
2020-2021:teams:manespace:2020_08_15-2020_08_21周报_week15 [2020/08/21 18:15] (当前版本) iuiou |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| * **题源**：[[https://codeforces.com/contest/1398/problem/E]] | * **题源**：[[https://codeforces.com/contest/1398/problem/E]] | ||
| - | * **题意**：给出两颗有根树，编号不相同，问最少需要改变多少编号能使这两棵有根树完全相同。 | + | * **题意**：有火焰魔法和闪电魔法两种魔法，第i个魔法会对怪物产生$a_i$的伤害，一旦一个魔法跟在闪电魔法后面，则该魔法造成的伤害会翻倍。问累计一共能造成多少伤害？要求支持插入一个新魔法，和插入后即时查询得操作。 |
| - | * **知识点**:网络流，数哈希 | + | |
| - | + | * **知识点**:set,贪心 | |
| - | * **题解**：要判断两棵树是否相同，首先要判断两棵树是否同构，可以先对两颗树用树哈希预处理一遍。之后对树进行dfs，在同一深度时，要将同构的子树相互批配以达到完全相同，显然匹配方法不会只限于一种，可以换种思路，批配完全相同的子树，完全相同子树匹配完成后，就可以得到最多多少节点不需要批配就可以相互对应，递归求出网络流边的边权。 | + | |
| + | * **题解**：首先可以确定的一点是，当前只要存在火焰魔法，假设现在一共有$k$个闪电魔法，则一共会有$k$次翻倍的机会，如果没有火焰魔法则只有$k-1$次翻倍机会。可以用set维护两个数组一个是可以翻倍得数，还有一个是一倍的数，再维护一下火焰魔法，之后每次操作先按照要求删去或者添加，添加时比对一倍的最大数，若比它小则加入，若比他大则加入两倍的数组。每次操作完之后，比对闪电魔法的数量和翻倍数组中数的数量，多减少补，最后比较火焰魔法最大$a_max$(若没有则为0)和翻倍魔法最小$b_min$的大小，若翻倍魔法最小大，则需要减去$b_{min}-a_{max}$,因为最小的闪电魔法无法被算进去。否则则不用算，因为最小的闪电魔法一定不会被算进去。输出答案即可。 | ||
| =====团队训练===== | =====团队训练===== | ||
2020-2021/teams/manespace/2020_08_15-2020_08_21周报_week15.1598004764.txt.gz · 最后更改: 2020/08/21 18:12 由 iuiou
