FJ2016集训 day7

2016年7月9日1,2994

题目来自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 * ival[]的差很快就会大于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存图的程序也容易在这两个数据点超时。