【题解】牛客练习赛61

A.打怪

签到题，根据勇士的攻击力、毛球怪的攻击力和血量计算出打掉一只毛球怪需要损血的回合数，从而计算出打掉一只怪需要的损血量，然后根据这个值和勇士的血量就可以计算出能打掉多少毛球怪了。注意特判的情况。

B.吃水果

贪心操作，若,输出,否则不妨设，不断将直到且，若一直吃光水果，否则一直选择吃水果直到恰好等于，此时再将，然后继续吃水果直到吃光即可。
因此总的操作次数为
很容易发现操作最少需要的就是这么多次，因为随着与的一起下降，是在增大的（），所以越早增加越好，而让去逼近只有乘法一种方法，且下降到一定需要次。
下面证明这么做一定是有解的：
首先第一步的不断乘和最后的吃水果一定是可以的，只需要证明一定存在使得
由知
由知，则，则即
由于数据量较小，直接模拟整个过程也是可以通过的。

C.四个选项

首先一遍求出每个联通块的大小，然后把每一个联通块当做一个体积等于联通块内点的个数的物品，问题就是要求有若干物品，要求恰好填满四个体积分别为的背包有多少方案。
设为枚举到第个物品，四个背包被装填的体积分别为的方案数，直接枚举填哪个背包转移即可。
由于数据量较小，也是可以的。
如果数据量再大一点，可以把所有背包的体积的所有状态哈希一下，变成一个二维，再滚动一下第一维即可。

D.最短路变短了

从点跑出到其他点的最短路数组
建反向图，从点跑出到其他点的最短路数组
设我们要反向的边为，那么原图实际上可能更优的路径多了一条，也就是
，所以只需要看一下是否成立即可。
注意，有的人可能会觉得由于这条边被反向了，所以或者的值可能被改变了，但是我们想一下：
假设答案是并且经过了这条边，那么他再走回来实际上相当于走了一个环，而题目边权都是正数，所以最短路不会变短（还不如不走这个环），与假设相矛盾。
如果答案是，注意到这两个值不会变小，那么这两个值是否变化不影响答案。

如果还要判断最短路长度是否不变该怎么做？

E.相似的子串

取出的子串如果最长公共前缀为,那么每个子串除了前个字符都可以去掉，问题转化为取出个位置不相交且完全相同的子串，求最长长度。
很显然答案具有可二分性，那么我们二分答案。
设为字符串长度。
倒着,设代表从开始长度为的子串哈希值。
设代表考虑从到范围，取和这个位置开始的子串相同的子串最多能取多少个。
则
所以我们开一个，
从后往前枚举，令。
或者可以每一个哈希值开了一个队列，每次取可行的位置更新就可以了。
最后取所有值的最大值，判断和的大小关系即可。
时间复杂度：

F.苹果树

前置技能：线段树、点分治。
如果你会动态点分治，那么这个题就是一个模板题了，出这个题的初衷是想让会点分治的人了解一下点分树的概念，又不需要去考虑去掉点分树中子树的影响。
如果我们将点分治里所有求出的重心向他上一层分治的重心连边，就形成了一个树状结构，我们称这棵树为点分树，根据点分治的性质可以知道点分树的树高是级别的。
我们给每一个结点动态开点一棵线段树，维护从到在点分树中子树的所有苹果的最小距离，每次在节点加入一个苹果的时候，在点分树上从向上的每个节点更新一个苹果。
查询的时候从往上跳，，其中代表查询这个点的线段树苹果成熟度从到的最小值。
最后别忘了给结果乘以。
求任意两点间距离可以用。
时间复杂度：