牛客小白月赛 83 出题人题解

A. 小天的金银铜铁

按题意模拟，判断 即可。

B. 小天的魔法 Ⅰ

不等长。按照排序不等式，降序排序后，取短的长度。若 不足长，可以在后面补 。

考虑最小操作次数。

对于当前决策是否使用魔法 时，使用两个魔法 的伤害为 ，因为 ，若 ，那么使用一个魔法 和一个魔法 的伤害为 。所以从前往后贪心地使用魔法，如果当前 ，则先用魔法 再用魔法 ，反之就一直使用魔法 。

一个小细节是：如果当前直接使用魔法 就能击败，那么就不用使用魔法 了。

时间复杂度：

验题过程中发现的一个做法是， 降序后，直接枚举用多少魔法 1 即可。

时间复杂度：

C.小天的 Minecraft

按题意分析，只有：

• 16 个铜粒
• 12 个铜粒，4 个银粒
• 12 个铜粒，4 个金粒

三种情况是可以做出铜镐的。

那么计算这三种情况的概率之和即可。

。

直接算也可以（很小不会爆 int），杨辉三角递推也行。

D.小天的子序列

因为题目不要求本质不同，所以要考虑 和 的所有位置。因为开头和结尾确定了，那么子序列可以选择的范围也就确定了。所以，假设 。那么 对答案的贡献即为：。

虽然 是 基本的，但是 是 级别的，所以对每一对字符 计个数，询问时枚举 的长度计算总贡献即可。

组合数使用杨辉三角递推预处理即可。

预处理：，单组询问 。

还有一些 或者 之类的 这里不赘述了。

这里提一下出题人的另一个做法，每次暴力枚举 和 的位置集合，计算答案，然后记忆化。理论上单次询问貌似： 但是出题人认为均摊之后卡不掉。

E.小天的贪吃蛇

对于两种路线，可以预处理成序列。

转换成序列后，那么就是在一个序列上，带修维护从某一个位置开始，连续相同字符的长度。

一个经典的直接的做法是：线段树维护 position，查询使用线段树上二分。

但是没有必要。在此题的范围下，只要维护每种字符的 position 集合。支持增删改查。询问时，枚举所有字符，二分找到出现位置在 之后的最小位置，减 即可。使用 set 维护 position。

时间复杂度：。

F.小天的 A+B

。将 放入 内，且将 展开后，对于一般形式可以发现：

。

同时：。所以实际上系数才是影响结果的核心因素。

• 若区间长度不超过 30 ，直接枚举即可。
• 若区间长度超过 30 ，则需要继续分类讨论：
• 若区间内有正数，那么应该从 中最靠近 的一个正数开始，往后暴力找 个位置。（同时，因为 2^n 过大，所以先提出一个公因式，找到最值后乘回去）
• 若区间内有零且没有正数 ，答案即为 0 。
• 若区间内全是负数，则从 往前找 30 个位置即可（处理同上）。

判断区间内是否有正数、0 同时支持修改，使用 set 分别维护正数、0 的 position 集合即可。