A、小蒟和他的乐谱

签到题，将原序列对 取模之后将序列扫描一遍就可以得到答案

B、小琛和他的学校

树是无根的，可以随便选取一个校区作为根节点。不妨设 号校区为根。
对于每一个校区，可以通过 计算出它子树中校区的个数 以及子树中学生的总数 。
然后再次进行 ，假设 为当前遍历到的节点的某一个子节点，那么连接它们的这条边所需支付的维护费用为 。
时间复杂度为 。

C、小魂和他的数列

由于 比较小，所以可以先将原序列离散。
之后通过 棵树状数组分别维护 元、 元、 元... 元的单调上升子序列的个数。
时间复杂度为 。

D、小翔和泰拉瑞亚

首先可以枚举一个位置，尽量使它的高度降低，用掉所有包含该位置的魔法，然后求出全局的最高位
置，用最高位置与当前枚举到的位置的高度差来更新答案。这样必定能够求到最优解。
所以可以从左到右枚举位置，当当前枚举到的位置进入某一个魔法的区间时，就应用它。出来的时候就
撤销它，然后通过线段树来维护最大值。
判断进入某一个魔法的实施区间可以按照左端点排序，实施了之后扔进按照右端点为关键字的小根堆里
判断是否出了区间即可。
时间复杂度 。

E、小雀和他的王国

当图中的割边被断开之后，原图就会不连通。所以要尽量让割边的数量减少。
可以先随便求出原图的一棵生成树。
然后通过树上差分或者 算法求出割边。
新连一条边之后，在生成树上新连边的两端点之间的路径上的割边将不再是割边，所以需要求出一条割
边最长的路径，就是求一棵树的带权直径， 或者 求出即可。

F、小球和新型材料

先考虑如何求出字符串 在每次循环移动过后回文子串的个数。
先把字符串 复制一次接在后面。
然后我们要求的就是区间 这 个区间内的回文子串个数分别有多少个。
可以用马拉车算法求出以每个位置为中心最长的回文串长度。然后考虑对这 个区间的贡献。
先考虑回文长度为奇数的情况:
设当前回文中心的位置为 ，以 为中心的最长的回文串的左端点为 ，右端点为 。那么它对第 个区间到第 个区间都有 的贡献。
对于第 个区间和第 ，贡献为 ；
对于第 个区间和第 ，贡献为 ；
以此类推，直到贡献为 （假设这些区间都存在的话）。
相当于按位加上一个等差数列，线段树维护即可。回文长度为偶数也同理。注意细节即可。
然后就可以判断出回文子串个数之差是否大于 了。
再来考虑如何求最大收益。
把式子用二项式定理展开，就是：

由于 比较小，可以分P次求和，然后再累加起来。
考虑如何求：

把 倒过来，就是：

这就是一个卷积的形式，所以只要把 复制一遍，分别求出 在 次方和 在 次方后的值，然后用
把两个式子卷乘起来，最后乘以 并累加，就能得到每次循环移动后的收益。最后减去 乘以移动次数后取最大值即可。
时间复杂度 。

很走心而且很棒的民间题解

范艺杰的博客