牛客小白月赛 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 集合即可。
