题目来自coolinging （orz）

Problem 1 挑选子序列(sequence.cpp/c/pas)

题目来源：原创

考察要点：搜索与剪枝、dancing links、二分、排序

涉及要点：动态规划、随机化算法、贪心

解题报告：

题目可以理解为在串t中选取m个字母，每个字母覆盖串s1和串s2的部分位置，使串s1和串s2被完全覆盖，求满足如上条件时距离的最小值。

对于数据点1，n <= 10，T <= 10，可以直接枚举选取哪m个字母，简单计算即可。

由此可知，对于本题来说，判定比求解来的容易许多。又本题满足答案单调性（即距离为x时有可行解，则距离为x+1时也必有可行解），故可先二分答案，从“求解所有可行解的最小距离x”转化为“距离为x时是否有可行解”的判定问题。这一判定问题实际上就是经典的重复覆盖问题。

对于数据点2，n <= 20，T <= 10，二分答案后，再使用深度优先搜索解决重复覆盖问题。这里有两个优化要点，其一是对所有可能的答案排序后离散化（即ASCII差+距离差是有限的），其二是先随机几组解作为答案的上界。

对于数据点3、4， val[i] = i * 42， T <= 50，因此时相邻的val[]的差42比字符集大小26来得大，由贪心思想易得，子序列中每个字母覆盖的位置必然是连续的一个区间，故可使用动态规划解决。

f[i][p][j1][j2]表示t[1..i]中已选择p个字母，覆盖s1[1..j1]与s2[1..j2]的最小距离。转移略

对于数据点5， val[i] = i * 42， T <= 100；与数据点3、4做法相同，但数据组数较多，需使用前面所述的两个优化要点，或者程序的常数较小。

对于数据点6、7， val[i] = i * i；val[]的差很快就会大于26，这两组数据点给选手的随机化算法（如模拟退火）、搜索算法、启发式算法、贪心算法（如构造配合搜索）发挥空间。

对于所有数据点，n <= 40, 0 < m <= n， 0 <= val[i] <= 2000， T <= 100；出题人使用的是dancing links。该算法实际上仍属于深度优先搜索，包含了最优性剪枝、可能性剪枝、启发式搜索等。故只要选手的程序足够优异，也可以使用其他做法通过所有数据点（标准程序最大数据点花费了0.78s，约时间限制的50%）。

dfs（用于理解题意。。。）

dancing link：

Problem 2 点对游戏(game.cpp/c/pas)

题目来源：原创

考察要点：树的基于点/边的分治、概率与期望

涉及要点：动态规划、广度优先搜索

解题报告：

对于某位玩家，其占据每个点的概率是相同的（因为点与点之间没有区别）。同样，其占据某对点对的概率也是固定的。不妨设这位玩家最终占据了n个点中的x个点，因为三人轮流选取的顺序固定，所以x可以简单求得。则该玩家占据某对点对的概率可以这么计算：

该玩家从n个点中选取x个点的方案数为C(n,x)。

在这些方案中，选取了某对点对的方案数为C(n-2,x-2)。

与前面分析类似，易得每个方案的概率是相等的，故该玩家占据某对点对的概率为C(n-2,x-2)/C(n,x) = x(x-1)/n/(n-1)。

故问题转换为求距离为某个幸运数的点对对数，将其乘以x(x-1)/n/(n-1)即为答案。

对于数据点1，n <= 1000，bfs即可。

对于数据点2、3、4，第i个幸运数为i，因为幸运数<=10，故可以使用树形动态规划求解。F[x][1..10]表示子树x中与节点x距离为1..10的点数，转移略。

如果在bfs中加入剪枝优化（距离超过最大的幸运数后就不再搜索），亦可通过这三个数据点。

对于数据点5、6、7，n为3的倍数，三人答案相同，方便选手计算。

对于所有数据点，3 <= n <= 50000，m <= 10，幸运数大小 <= n，使用树的基于点/边的分治求解。其中树的基于边的分治需要重建树以防止星形图（数据点7和数据点10）时复杂度退化。另外在不开编译优化的情况下，使用vector等STL存图的程序也容易在这两个数据点超时。