算法合集之《浅析信息学中“分”与“合”》75406

《算法合集之《浅析信息学中“分”与“合”》75406》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅析信息学中的“分”与“合”福建省福州第三中学杨沐16目录【摘要】3【关键字】3【正文】3一、引言3二、例题分析3[例一]牛奶模版4[例二]树的重建6[例三]最优序列9三、总结12【感谢】12【参考文献】13【附录】1316【摘要】本文就“分”与“合”的思想在信息学中的应用进行讨论与研究。“分”与“合”思想的精髓在于通过在“分”与“合”之间的转化中找到问题的本质从而解决问题，该思想的应用并非仅限于传统意义上的“分治法”。本文通过分析例题《牛奶模版》、《树的重建》与《最优序列》来介绍“分”与“合”思想在解题中的具体

2、应用。【关键字】“分”与“合”、转化、辨证关系【正文】一、引言——“话说天下大势，合久必分，分久必合”，这富有辨证意味的第一句话可以说是《三国演义》的精髓。浩浩中华几千年的历史，充分说明了“合久必分，分久必合”这一观点的正确性。“合久必分，分久必合”是从低级到高级，螺旋式发展的过程，纵观天下事，无不是在“分”与“合”之间互相转化下发展的。“分”与“合”的规律不仅在社会发展上得到应验，在信息学中的许多题目的解题过程中也有着充分的体现。“分”的思想是将一个难以直接解决的大问题，分成一些规模较小或限制某些条件的子问题来

3、思考，以求将问题解决。“合”的思想与“分”相对，是将“分”出的一些零碎的小问题合并成一个大问题，从而理清关系，得出解法。在当今信息学竞赛中，我们常常会碰到各种问题，由于规模过大而难以思考，无从入手，又或情况过于纷繁复杂导致思考难度骤增，这时不妨尝试使用“分”与“合”的思考方式来帮助分析问题。二、例题分析下面，作者通过介绍三个例题《牛奶模版》、《树的重建》和《最优序列》，结合各题自身特性利用“分”与“合”的思想解题，希望能起到抛砖引玉的作用。16[例一]牛奶模版选自usacocontestDEC06GOLD《Mil

4、kPatterns》问题简述由于奶牛们的产奶品质波动不定，FJ决定找出奶牛产奶品质波动的规律。FJ用一个由到的整数组成的长度为的序列记录了各天奶牛们的产奶品质，FJ希望从中找出最长的一段模版串，使得该模版串在序列中出现至少次，请输出最长模版串的长度。（例如，12323231中2323出现了2次，最长的模版长度为4。）问题分析本题是一道与串匹配有关的问题，我们很自然的想到使用解决字符串问题的利器——后缀树，事实上，使用后缀树确实可以在线性时间内解决本题，但后缀树的高编程复杂度使我们很难在限定时间内完成解题任务。那么

5、，是否存在简单而又行之有效的算法呢？普通枚举法解决此题最简单的方法莫过于枚举法了，我们可以枚举出原串的所有子串，互相比对并统计出它们各自出现的次数，从中选出出现次数不少于次的最长子串。由于原串的子串数达到的级别，而字符串比较的时间复杂度为因此该枚举法的时间复杂度高达，完全无法在限定时间内出解。上述枚举法之所以低效，很重要的一个原因是重复比较过多。这时我们又想到了高效的串匹配算法——KMP算法。在枚举原串的子串后，我们可以使用KMP算法在的时间内算出该串在原串中的出现次数，因而将总算法复杂度降为。但是，当我们试图使

6、用串匹配算法继续优化算法时间复杂度的时候遇到了重重困难，在多次尝试无果后，不得不回到问题的起点，换一角度思考问题。16枚举法改进观察普通的枚举法，我们发现其实枚举所有子串的做法存在许多冗余，因为对于任意两个子串，相等的先决条件是它们的长度必须相同，这提示我们可以枚举子串的长度。而题目中存在着一个很明显的单调性，即在原串中若存在一个长度为的子串出现了至少次，则对于任意长度，必然能找到一个长度为的子串在原串中出现至少次（只需取为的子串即可）。根据此单调性，我们可以二分枚举答案，之后只判断相同长度的子串是否相等，效率大

7、大提升，时间复杂度优化为。转换枚举方式后，低效的子串判等方法成为了算法新的瓶颈。但我们发现，确定了子串的长度后，符合要求的子串只有个，可以使用hash表来存储各串，并用以判等。根据题目特点，我们设计如下hash函数：对于子串可以取任意素数，为大素数，表示在hash表中的位置，使用代替的内容（使得冲突时的比较时间复杂度降为）。若二子串的与值分别相同，则认为这两个子串相同（由于设置了两个函数，误判的概率大约仅为，可以忽略）。由于与只有个元素不同，因此，同理。这样就能在的时间内算出所有长度为的子串所对应的与值，因此在理

8、想情况下本方法的时间复杂度已经优化为了，并且正确率极高，足以通过所有数据。小结“分”16的思想在很多场合都有应用，在本题的求解过程中，先后尝试了多种方法，最终利用“分”的思想二分答案，巧妙地将限制下的最优化问题转化成限制下的存在性问题，从而得出了一个十分简便而有效的可行算法。[例二]树的重建选自ZOJ2701的《Restorethetree》问题简述给出一棵树的叶子节点数