小白月赛45题解
前言：这场比赛本来应该在去年9月可能就能出来了，但是因为一系列原因，延迟到了现在23333
本场比赛的话，很多题的代码难度都不算特别高，重在思考。
题解代码：
C:https://paste.ubuntu.com/p/jScbM6VzVX/ （qcjj贡献的解法）
A:显然，对于每次跳跃，我们都是跳最远的距离总距离才会最远。
其次，我们发现对于一开始，如果我们能跳到对面墙壁上，我们就能一直跳跃，如果不能那我们只能跳跃一次。
知识点：条件语句
B:通过递归中遍历的先后顺序，我们可以发现他实际上是一个
这个公式用等差数列求和化简后，答案为
直接输出即可。
知识点：等差数列，递归的调用顺序。
C：由于每3个或者4个同级的可以合成为一个高一级的糖果，所以我们为了让高等级的有更多可能性，我们肯定是从低等级往高等级合成。
对于低等级合成高等级，我们一定是尽可能的合成高等级的数量多，其次我们需要尽可能的让低等级的全部消完，所以我们只需要枚举情况即可。
qcjj:思路，对于每3个同级糖果 可以得到剩余的一个糖果减一，所以我们可以求得已有组数和剩余数量，然后消掉之后看最后会剩余多少个即可。
知识点：贪心
D：首先我们发现对于一个合法串进行切割，可能会切出若干个合法串，但是对于不合法串进行切割，那么一定会存在一个不合法串，所以首先可以判断一下整个串是否合法。
其次，我们在切割的过程中，需要保证切割的地方前缀合法，所以我们切的地方一定是前缀左括号和右括号数量相同且该前缀的任意前缀均满足左括号数量大于等于右括号数量的地点，所以我们只需要数有多少个这样的点即可，其次我们每个点可以选择切或不切，所以有两种情况。
所以直接求得
即可。
知识点：前缀和
E:显然对于这个题的思路 就是树上的最大连续子串和。
沿用最大连续子串和的思想，我们对于一个包含根的子树的连通块，如果他产生的贡献大于0，那么我们就可以将它加入到当前连通块上来，所以的收益一定是增大的。
所以我们只需要在树的遍历的过程中求树上连通块和即可。
知识点：树形dp。
F：对于这个题有许多解法，有用map剪枝卡过去的，有hash卡过去的，在这些基础上还有离线的查询，但是这些方法的常数都特别特别大，你要严格算un map是o1的话，那么他们的时间复杂度也能算
（不考虑劣化的情况）。此情况可能在1200ms~4000ms浮动。
还可以使用康托展开来处理hash这样的话可以放在数组中存，不需要un map的常数以及考虑他的劣化，如果离线，会更加快速。
但事实上，数字串匹配也能采用trie树这种数据结构来加速，对于合法前缀的串我们也可以融入trie树的每个节点中，所以这种时间复杂度为，且没有hash的常数。但是在扩展trie的过程中需要开辟
的数组以保证不会越界。此情况800ms。
现在 考虑离线情况的串只有
条，那么扩展的节点数只有
个。极大的减少了定位的时间以及开辟空间的耗时，此情况50ms。详情可以看std。
知识点：trie树 或者康托展开 或者 hash 或者stl优化
投递华为等公司10个岗位 >
