一类算法复合的方法

《一类算法复合的方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一类算法复合的方法摘要本文讲了一类算法复合的方法。这种方法是指将一个问题的若干种算法，分别使用于这个问题中若干个互补的部分。本文对两个有意思的问题作了详细的分析，使用了这种算法复合的方法成功解决了这两个问题。问题一中我们将一个ON2和一个ONR的算法复合，分别使用于问题中的两部分询问，得到了一个ONR0.5的算法。问题二中，我们将两个ON2的算法使用于原问题分割得到的三部分，得到了一个ON1.5的算法。本文最后对这类方法进行了总结。每个算法都可能有各自的优势和劣势。而将它们复合，使用于问题中的不同的部分，就有可能会将它们的优势结

2、合起来，取长补短，得出一个总体更优的算法。这种思想是极为重要的。关键字算法复合方法一、问题一题目来源：The2006ACMAsiaProgrammingContest-Shanghai1.1问题描述维护一个集合S，初始时为空。对这个集合有两种操作：1、BX在集合S中插入一个整数X，保证当前集合中X还不存在2、AY询问集合S中，被Y除余数最小的数是多少。如果有多个数余数相等，取任意一个第11页，共11页有N个操作需要依次处理。计算所有询问的答案。允许离线算法。其中1≤N≤40000，1≤X,Y≤5000001.2初步分析这道题让我

3、们设计算法维护一个集合S。我们先考虑一些容易想到的算法。最容易想到的算法是直接模拟问题中规定的操作，我们称其为算法1.0。每当遇到一个询问操作“AY”时，我们枚举当前集合S中的每个数，从中找出被Y除余数最小的。算法的时间复杂度为O插入操作个数×询问操作个数，最坏情况下显然会超时。但当插入操作很少或询问操作很少时，这个算法会很快。另一个略优一些的算法也很容易想到（算法1.1）。设py表示当前集合S中使得xmody最小的数x，也就是询问“Ay”的答案。因为允许离线算法，我们可以事先整理出询问中所有不同的Y组成的集合T，然后我们对每个

4、y∈T维护py的值。每当插入一个数的时候，我们用OT的时间逐个更新这些值。算法的时间复杂度为O插入操作个数×T。T同样是ON级别的，所以也不能完全解决问题。其实，这里的集合T可以理解为我们想维护的询问。我们可以只维护一部分询问中出现的Y，维护需要的时间就会减少，但是将会有一些询问得不到回答。1.3抓住问题的特征得出另一个算法（算法1.2）为了解决这个问题，我们抓住问题的特征，深入思考。当遇到一个询问“AY”的时候，我们要在当前集合S中寻找使得xmodY最小的数x。我们把这里的x写成kY+r，其中0≤r

5、rmodY=r。这就是说，我们要在集合S中，寻找使得r最小的数kY+r。如果把k确定，那么我们就是要在集合S中找区间kY,k+1Y中的最小值。所以我们不难想到一个算法：枚举k，寻找它对应的区间kY,k+1Y中的最小值，最后在这些最小值中取最优的。图1.1形象地描述了这个过程。第11页，共11页012…Y-1YY+1Y+2…2Y-12Y2Y+12Y+2…3Y-13Y…最小值为2最小值为Y最小值为2Y+1图1.1：图中用方格表示所有的自然数，其中集合S中的元素用阴影表示我们从每个区间kY,k+1Y中找出最小值，最后再取其中的最优值。

6、这里的最优值为Y，YmodY=0…设R为最大可能会插入的数，根据题目，R=500000。容易得到这里有ORY个不同的k。我们这样做就把一个找被Y除余数最小的数的问题，转化成了若干个找给定区间内最小数的问题。而这个问题我们很熟悉，可以用线段树解决。关于线段树，可以参见算法导论和国家集训队的相关论文建一棵0,R的线段树。在线段树的每个结点l,r上记录集合S内l,r中的最小数。因为我们事先知道所有要插入的数，我们可以把0,R离散化，只保留要插入的ON个点，这样每次操作就只需OlgN的时间。但在同样的时间内，线段树可以实现更多种操作。而

7、我们用到的操作只有询问一段区间内的最小值和插入一个数，并且插入时只会在位置pos插入pos这个数。所以使用线段树就显得比较“浪费”，我们或许可以找到一个支持的操作较少，但效率更高的算法。询问集合S中区间a,b内的最小数，可以看成是询问大于或等于a的最小数qa。如果没有大于或等于a的数，我们称qa=+∞。显然，如果qa>b，那么说明区间a,b中没有在S中的数，否则qa就是区间a,b内的最小数。图1.2给出了一个具体的例子。0123456789101112131415…图1.2：这里，S当前为2,7,8,12，Y=5qn在方格的下方

8、表示出来22277777812121212+∞+∞+∞…很容易观察到，对很多连续的a，qa是相等的。如果S为空，则对于任意的自然数a，qa=+∞。否则我们把集合S中的数排序，得到p1