这次的题目的代码可以在这里找到。Training-2016.08.10
过了的题目：A、C
已经补了的题目：B、E
计划补的题目：H、J(已补)
A题
给定n个串的字典序，问是否可以通过修改字符的大小顺序使得其合法。
做法：考虑两个串在字典中的大小关系相当于是规定了某两个字符的大小关系，只要判断一下是否会产生环即可。需要注意的是可能会出现【abc】【ab】这样的情况，即前缀的字典序比原串大，这样是永远无法合法的……
B题
德州扑克，给定局面，问获胜概率，做法就是枚举所有可能的情况。代码量很大，写+调花了4h+仍旧未过……
C题
给一个简单无向图，问生成树的权值的中位数最小是多少，做法：按照Kruskal求最小生成树的方式加到第 $ \frac{n}{2} $ 条边就是答案
E题
50×50的迷宫，只能向下或向右走，有26种宝石(‘a’~’z’)，26种坑(‘A’~’Z’)，你有一个无限大的栈型背包，每次可以将一个宝石放在最上面或是将最上面的宝石放在坑里，问从(1,1)走到(n,m)最多可以将多少颗宝石放进坑里。每种字母出现次数不超过10。
做法：我们可以将宝石看做左括号，坑看做右括号，即求最长的合法的括号序列。
由于关键点只有500多，对于从(x1, y1)到(x2, y2)的矩形，我们可以O(260)枚举我们第一个走到的左括号，再O(10)枚举它匹配的右括号，现在我们就将原问题转化成了与原问题相同的两个子问题：(x,y)->(tx,ty) (tx,ty)->(x2,y2)
转移的时候：
- 考虑当前的左上角和右下角是匹配的，要选的，那么我们就从左上角相邻的两个点中枚举一个起点，再相应地枚举一个终点，4种情况取个最大值再+1
- 左上角是个坑，跟之前的某个宝石匹配，那么我们只需要枚举2个起点，走到(x2, y2)这个终点就好了。
预处理一下连通性，记忆化搜索即可解决。
J题
题意：给你三个串，求出一个字典序最小的串，满足三个串到该串的Hamming Distance均不超过d，无解输出-1。
先考虑我们如何判断合法性，即是否存在可行方案。
发现每一位上只有5种情况：
- a[i] == b[i] == c[i] ——- 3
- a[i] != b[i] != c[i] ——- 1 + 1 + 1
- a[i] == b[i] != c[i] ——- 2 + 1 (有三种)
其中第一种我们可以不用考虑了= =不会影响我们的合法性。
对于第二种情况，它相当于是使我们的d1,d2,d3中的两个-1，那么我们可以反过来考虑，先将所有的d都-1，然后有n1次+1的机会。
对于第三种情况，我们有两种决策：
- 使字符相等的两个的d减一
- 使单独的那个的d减一
容易发现，如果有两种情况3都选择了决策1，不妨是(1,2),(1,3)，那么我们一定可以让他俩都选择相反的决策，即(3),(2)，这样一定不会使答案变差。
也就是说，对于三种情况3，一定至多只有一种是采用了两种决策，另外两种情况一定是都选择了决策2。
所以我们可以O(3)枚举选择决策1的情况，那么剩下的两项要消耗多少的d都是可以直接算出来的。现在我们只剩下两坨没有解决了：枚举的那个情况3，以及可以使某个d加一的情况2。
对于剩下的d1,d2,d3我们可以使其中两个-1，或是剩下的那个单独-1，那么在不会产生负数的情况下，我们可以随便减，如果会产生负数的话，我们就让那个单独的来-1，因为减两个的那个可能会需要消耗两个+1来救，而减一个的永远只会消耗一个。最后只需要判断总共的+1次数和d够不够用就可以了。
以上验证方法只跟情况1和情况3的出现次数，以及剩余的d1,d2,d3有关，而且是可以O(1)计算的，所以我们就可以从前往后枚举每一位放什么字母，然后check放了以后是否还能构出合法串，这样就可以贪心了。
WA：当d1,d2,d3会减出负数的时候要小心处理，是需要先消耗+1救回来的。。。
An undergraduate at Shanghai Jiao Tong University who studies CS.