Brief description:
Problem A. Lexicographically Maximum Subsequence
给定一个字符串，求重新排列这个字符串之后所能得到的字典序最大的串。（略。
Problem B. Infinite Maze
给定一个可平铺的迷宫，问出发点所在的区域是否是封闭的。（记录四维状态 BFS() 即可。。。卡步数 TLE 了两次。。
Problem C. Paint Tree
给定一颗树，和平面内一组点集，问是否存在一个对应关系使得，生成的平面图不产生交叉。
Problem D. The Next Good String
。Good String 定义为，不存在长度大于等于 d 的回文子串。给定一个字符串，求该子串的下一个 Good String 。
Problem E. Opening Portals
给定一个 n 个结点，m 条边无向带权图，选中其中 k 个结点作为传送门，
当一个传送门被点亮后，可以在其他已被点亮的传送门之间做无损传送。
问从 1 号结点出发，点亮所有传送门的最少代价。
( .. 1 ≤ k ≤ n ≤ 10^5, m ≤ 10^5 .. .)
Analysis:
Problem C. Paint Tree
。。总是有解。深搜一次得到 sz 数组。之后根据极角序递归构造即可。
。。想明白其实还是简单的一题。
…
Problem D. The Next Good String
。比赛的时候写了个深搜 TLE 了。。。赛后 Sevenkplus 告诉我就是普通的搜索。。。
于是跑去看了一下 7k+ 的代码。。
于是发现这里我的主要错误是没有注意到回文子串的递归性质。(如果存在一个长度为 x 的回文子串，则必然存在一个长度 x-2 的回文子串。。。
于是利用这个性质 bool illegal() 函数只需要判断 d 和 d+1 两个长度即可。。
bool illegal(int x){
++x; FOR_1(l, d, d+1){
if (l > x) continue;
int h1 = A[x] - A[x-l]*P[l], h2 = B[x] - B[x-l];
if (h1*P[x-l] == h2) return true;
}
return false;
}
注意到这里的字符串 hash 需要一些技巧，以避免复杂的修改操作
（官方的题解里面这一步使用了树状数组来维护 Hash。。。
（貌似我的算法框架和官方题解一样。。分为两部。
。。先找到第一个要修改的位置。。随后再 dfs()。。
实际也可以直接 dfs() 。。（参见 Sevenkplus 的代码。。。
Problem E. Opening Portals
首先根据传送门的性质，如果所有点都是传送门的话那么结果就是该图的最小生成树。
对于只有其中 k 个结点是传送门的图，只要在原算法的基础上稍作修改即可。
具体，对每个点求出 P[i] 和 D[i] 。（表示距离这个点最近的传送门和其距离。。。
之后对每条边，再根据 D[x] + D[y] + w 作为关键字跑最小生成树。。
以上分别用一次多源 Dijkstra()，和稍作修改的 Kruskal() 即可。
（因此感觉编码难度上也要弱于 D 题。。。
