B
不会做，自闭了 /kk
考虑走了一个人之后更新他周围的人的最短路，只要能够更新就一直 bfs 更新。
虽然看上去像是 (mathcal O(n^4)) 的，但是每次更新之后 (mathrm {dis}) 至少减少 (1)，而 (sum mathrm {dis}_{i, j} = mathcal O(n^3))，所以时间复杂度就是 (mathcal O(n^3))。
C
和之前出现过几次的原题很像。
从低位到高位建三进制 trie，加法就是将三个儿子换一下，另外那个操作就直接打个标记。
时间复杂度 (mathcal O(3^n + n|T|))。
D
首先想个办法将每种字符的出现次数搞出来，可以每次问 (128) 个一样的字符，如果返回的答案是 (x)，那么这个字符的出现次数就是 (128 - x)。
然后可以发现，如果一个串 (T) 是 (S) 的子序列，那么编辑距离就恰好是 (|S| - |T|)。
进而想到某天的考试题，可是那个题目只有 a、b、c 三种字符，而这里有 (62) 种，直接套用就会爆炸。
考虑对字符种类分治，设 Div(l, r) 表示将第 ([l, r]) 种字符合并起来的字符串。
考虑如何将两个字符串合并，就直接将第二个字符串的字符一个一个插进第一个串中，不停地询问是否是 (S) 串的子序列就能做到了。
询问次数为 (mathcal O(L log 62))，不需要特别精细的实现也能过。
E
这个环就非常离谱，但是可以发现如果从 (A_i) 最大的那个位置开始的话，最优策略一定是马上结束，所以可以从 (A_i) 最大的位置处分开，断环为链，然后令 (A_{n + 1} = A_1)。
dp，设 (f_i) 表示从点 (i) 开始最多能获得的期望收益，有 (f_i = maxleft( A_i, frac {f_{i - 1} + f_{i + 1}} 2 - B_i ight))。
然后以 (A_i) 为初值迭代个几百次就能过样例（
这个有后效性的 dp 可以优化，先来看一个简单一点的转移方程是如何优化的：
结论：对于形如 (g_i = maxleft( A_i, frac {f_{i - 1} + f_{i + 1}} 2 ight)) 的转移方程，可以考虑将 ((i, A_i)) 当做点来求一个上凸包，然后将所有在凸包内的点上移到凸包的边上，最后求出来的点就是 ((i, g_i))。
可以这样感性理解：首先在凸包上的点一定不会再被更新，然后考虑迭代的过程，可以发现一个点受到别的点的影响之后会上移，但是一定不会移出凸包，最多就只能更新到凸包的边上，而这就是最终的答案。
考虑如何将 (f) 变成和 (g) 类似的转移，定义序列 (c) 满足 (c_{i - 1} + c_{i + 1} = 2 (B_i + c_i))，然后令 (h_i = f_i - c_i)，就有：
大功告成。