A.ACCEPT

知识点：模拟

思路：按照题意统计出各个字母的出现次数，再联系相应字母在 ACCEPT 中的出现次数计算即可。

时间复杂度：

B.咕呱蛙

知识点：思维、规律

思路：当新增加的青蛙数为偶数时，则本层青蛙可以两两配对，不会对之前的青蛙产生影响。而新增加的青蛙数为奇数时，会导致本层多出一只青蛙。所有青蛙能否两两配对，本质上只和每层青蛙的奇偶性有关，因此我们可以将每层中的青蛙先尽量两两配对，此时每层剩余的青蛙个数如下所示：

因此总青蛙数的变化规律为：

• 奇、奇、偶、偶、奇、奇.......

我们只需要判断第 个偶数在原序列是第几个即可。

时间复杂度：

C.得分显示

知识点：二分/枚举

思路：本题实质上是给定一个首项为 0，公差为 的等差数列整数部分，问公差 的最大可能值是多少。

方法1：很显然，等差数列满足二分的性质，可以直接二分 ，判断当前的 是否合法，在保证其合法的情况下，让其尽量大。当然，采用二分时应特别注意边界和精度问题。

方法2：由于一定存在合法的公差 ，所以我们可以直接枚举等差数列每一项的可能最大值，直接计算出对这一项而言最大合法的公差 。最终的答案 就应该是所有 的最小值。

时间复杂度： /

D.阿里马马与四十大盗

知识点：思维、贪心

思路：本题实际上是个诈骗题。

题目给定了中经过安全区的两种操作：要么回满血，要么不回血。思考如果能成功逃出，那么最后一次回血地点显然越靠前越好（在保证之后血量大于0的前提下）。因为花费的时间显然和路径长度以及总回血量有关，路径长度是固定的，我们只需要让总回血量尽量小。

那从开始逃跑到最后一次回血，总共恢复了多少血量呢？其实这个值刚好等于这之间总共扣除的血量！由于每次选择回血时只能回满，在上一次回血之后，到下一次回血为止，这之间扣除的血量刚好在下一次回血时回满了。因此，只需要将最后一次回血的时机选的尽量早，最终答案就是整体路径长度+从开始逃跑到最后一次回血这之间扣除的血量。至于无法成功逃出的情况，只要特判一下血量上限是否可能两个相邻安全区之间扣除的血量之间即可。

时间复杂度：

E.烙饼

知识点：构造

思路：

定义：平均烙饼时长 = 。

结论：当耗时最长的饼，其烙制时间低于平均烙饼时长时，最短耗时就应该为平均烙饼时长；否则最短耗时应为该饼的烙制时长。

为什么呢？思考最短耗时为平均烙饼时长时，也就是说耗时最长的饼，其烙制时长小于等于平均烙饼时长，此时我们可以依次给烙饼机安排任务，比如我们先给 号烙饼机安排烙饼，当烙制到某个饼时该烙饼机的占用时间超过了平均烙饼时长，此时我们可以将多余的部分分配给下一个烙饼机并错开烙制时间，以此类推，这样能保证所有烙饼机都处于工作状态；而如果耗时最长的饼超过了平均烙饼时长，仍按上述方式分配会导致这个饼同时在多个烙饼机烙制，这显然是不可能的，因此在这种情况下答案应为耗时最长饼的烙制时间。

因此，先计算出最短耗时，再依照以上构造方案输出，每个饼的烙制时间最多被拆成两块分到两个烙饼机上，构造结果总数不会超过 。

时间复杂度：

F.龙吸水（EASY）

知识点：DP

思路：由于每次对河流操作后，都会对河流将来的水位造成影响，考虑使用DP解决本问题。虽然前面的操作会对后面造成影响，但我们仅需要知道前一天使用魔法后水位的变化情况，就可以推断出下一天水位的合法区间。

具体来说，如果第 天水位 下降了,那么受之前影响，第 天水位也应至少下降，合法的水位区间应该为。反向考虑，假定第 天水位下降了,如果，那么前一天下降的水位必然要小于等于。当然，可能是等于 的，这时前一天下降的水位就可能为的任意值。

因此，可以考虑 维护当前为第天，水位下降高度为时的最大无灾日数，状态转移方程为

中间取公式可以用前缀和预处理，时间复杂度不会超过

G.龙吸水（HARD）

知识点：DP、线段树

思路：先思考如何解决。由于范围扩大，直接沿用EAZY版的方法是行不通的，主要原因在于该方法需要枚举每天水位的所有情况。是不是可以省略掉一些不必要枚举的水位呢？我们考虑题目中降低水位这个操作，显然在较早时刻降低水位可能会导致后面水位降低。换句话说，在较早时刻降低不必要的水位会导致后续水位，这显然是不优的，因此在不必要的情况下，水位降低的越晚越好。那什么情况是必要的呢？就是当前水位时。

分类讨论，如果当前水位时，显然降低水位是不必要的，不可能出现更优的结果；如果当前水位时，我们有两种选择：一种是维持不动，舍弃当前而保证后续有更高的水位、能出现更多的无灾日；另一种是将当前水位下降到。

到此为止，我们就能获得一个新的状态转移方程了。

改写的状态转移方程：

仍然维护当前为第天，水位下降高度为时的最大无灾日数。

这个状态转移方程仍然难以解决本问题，观察到其瓶颈主要在于两个较为复杂的取公式。继续分析这两个公式：和，你会发现，这其实是两个区间求最值，再看看的情况，这就是一个区间加。所以可以选择用动态开点线段树加速DP的过程，即可解决本题。

Bonus：当然，上述方法由于水位取值范围较大，使用动态开点线段树会使用较多空间。如果进一步分析，我们还有更加稳妥的方法：

根据之前推导的结论，我们会发现，水位的下降值最多只有种取值是有效的,即,和，除此之外的值都不会对答案产生贡献。因此考虑预处理所有可能的水位下降值，将其离散化后再使用线段树加速DP。

离散化后的状态转移方程与上述保持一致，唯一不同点在于将其中对应的值转化为离散后的值。这样由于我们提前进行了离散化，线段树不需要进行动态开点了，维护的叶子节点数量不会超过个，可以在较小的空间范围内通过本题。

时间复杂度：