【题解】牛客小白月赛104文字题解

写在前面的话

因为某不可抗力因素，这场比赛在开赛前三天被拉出来顶班了，于是仓促之中出了6道题，虽说已经尽量保证题目质量了，但C和F两题仍有较板的嫌疑（好在有比较有趣的故事背景），望海涵。

难度方面：本来的顺序是ABDCEF，原C（小红开锁）由于代码细节有可能写的非常多，另外原D由于较板（非常显然的二分答案），所以最终这两题swap了。不过仍然存在了BC之间gap较大的问题。本来准备添加一道新C组一场7题场，最终也因时间仓促未能实现。

A 小红购买装备

难度：400

知识点：枚举

题意：给定初始的装备、商店可购买的装备情况，求最优战斗力。

思路：按题意直接枚举即可。我们可以记录初始不卖装备的战斗力，然后假设卖掉，可以将卖的钱和身上的钱合并来判断是否可以购买每一件装备。

B 小红招募英雄

难度：800

知识点：数学，概率

题意：给出每次单抽的概率，问十连双黄蛋以上的概率。

思路：我们可以将概率分为两类：代表ssr以上，代表sr以下，那么最终答案即为：1-P(十连无金)-P(十连单金)。

C 小红打怪

难度：1400

知识点：二分

题意：个怪物，三种技能，每回合可以全体打1、相邻打1，单体打1各释放一次，问击杀全部怪物的最小回合数。

思路：显然答案满足单调性，因此可以对答案进行二分。二分时我们需要判断给定回合数能否击杀全部怪物，这样总体复杂度为

具体的判断方式是：假设打了回合，我们可以拆分成进行次全体打1，次相邻打1，次单体打1，全体打1和单体打1都比较容易判断：全体打1可以最开始的时候进行，单体打1最后再进行（只要保证剩余怪物血量不超过即可），那么我们需要做的就是用“相邻打1”造成尽可能多的伤害，这部分可以贪心解决：从左到右遍历，如果相邻两个怪物血量都大于0，那么直接进行次即可，直到把“相邻打1”的次用完。

这部分的贪心也是很容易证明的：我们假设，当我们第一次遇到了且不进行“相邻打1”，此时有，那么如果我们对进行相邻打1导致变成0，这样以后每次再用“相邻打1”就都会浪费1点伤害了，而我们每对进行相邻打1，节约出来的“额外伤害”最多也仅有1点，因此这个策略一定不会比优先从左到右贪心的策略更优。

D 小红开锁

难度：1700

知识点：模拟

题意：给一个锁，从中心向外每一层有一圈符号，每次操作可以使一层整体顺时针移动一格，问使得所有'X'在同一象限的最小操作次数。

思路：对于每一层分别处理即可。

一种比较好写的代码是：找到'X'连续段的的开始和结束位置即可，因为保证有解所以一定恰好只有一个'X'连续段。之后枚举4种情况，注意如果减到负数了需要加上这一层的符号数量。

E 小红开宝箱

难度：1900

知识点：dfs，构造，图论

题意：构造一个排列，满足每个位置都符合要求（每个位置要么是指定值，要么是二选一）

思路：首先可以将确定的值先定下来，剩余的二选一进行连边后形成一个图，该图一定为置换环，即每个连通块必为个节点条边的基环树。

对于每个连通块，我们可以先用拓扑排序将所有叶子去掉（所有叶子是必然的结果），所有叶子处理完毕后会剩余一个环，我们可以任意定义一个值，然后按顺序一次赋值给其余的值。

F 小红闯地下城

难度：2200

知识点：lca，树

题意：给一棵树，每个点有一个指定的传送地点，问最多1次传送后，可以最多经历多少不同的点并回到原点。

思路：我们先假设没有传送阵的情况，那么对于初始的体力，我们能击杀的最多怪物数量是，因为除了初始点的怪物外，我们每次多击杀一个怪物就要多花费3体力（2体力走路，1体力打怪）。

对于枚举每个传送，我们先计算击杀1到u到v再回到1的击杀怪物总量和体力消耗，之后如果有额外的体力，可以除3向下取整额外增加击杀怪物的数量。