国家集训队2008论文集 一类算法复合的方法

《国家集训队2008论文集 一类算法复合的方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一类算法复合的方法江苏省扬州中学张煜承摘要本文讲了一类算法复合的方法。这种方法是指将一个问题的若干种算法，分别使用于这个问题中若干个互补的部分。本文对两个有意思的问题作了详细的分析，使用了这种算法复合的方法成功解决了这两个问题。问题一中我们将一个O()和一个O()的算法复合，分别使用于问题中的两部分询问，得到了一个O(.)的算法。问题二中，我们将两个O()的算法使用于原问题分割得到的三部分，得到了一个O(.)的算法。本文最后对这类方法进行了总结。每个算法都可能有各自的优势和劣势。而将它们复合，使用于问题中的不同的部分，就有可能会将它们的优势结合起来，取长补短，得出

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

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

4、

5、)的时间逐个更新这些值。算法的时间复杂度为O插入操作个

6、数×

7、

8、。

9、

10、同样是O()级别的，所以也不能完全解决问题。其实，这里的集合T可以理解为我们想维护的询问。我们可以只维护一部分询问中出现的Y，维护需要的时间就会减少，但是将会有一些询问得不到回答。1.3抓住问题的特征得出另一个算法（算法1.2）为了解决这个问题，我们抓住问题的特征，深入思考。当遇到一个询问“AY”的时候，我们要在当前集合S中寻找使得xmodY最小的数x。我们把这里的x写成+，其中0≤<。那么mod=(+)mod=。这就是说，我们要在集合S中，寻找使得r最小的数+。如果把k确定，那么我们就是要在集合S中找区间[,(+1))中的最小值。所以我们不难想到一

11、个算法：枚举k，寻找它对应的区间[,(+1))中的最小值，最后在这些最小值中取最优的。图1.1形象地描述了这个过程。第2页，共11页012…Y-1YY+1Y+2…2Y-12Y2Y+12Y+2…3Y-13Y……最小值为2最小值为Y最小值为2Y+1图1.1：图中用方格表示所有的自然数，其中集合S中的元素用阴影表示我们从每个区间[,(+1))中找出最小值，最后再取其中的最优值。这里的最优值为Y，mod=0设R为最大可能会插入的数，根据题目，=500000。容易得到这里有O个不同的k。我们这样做就把一个找被Y除余数最小的数的问题，转化成了若干个找给定区间内最小数的问题。2

12、而这个问题我们很熟悉，可以用线段树解决。建一棵[0,]的线段树。在线段树的每个结点[,]上记录集合S内[,]中的最小数。因为我们事先知道所有要插入的数，我们可以把[0,]离散化，只保留要插入的O()个点，这样每次操作就只需O(lg)的时间。但在同样的时间内，线段树可以实现更多种操作。而我们用到的操作只有询问一段区间内的最小值和插入一个数，并且插入时只会在位置pos插入pos这个数。所以使用线段树就显得比较“浪费”，我们或许可以找到一个支持的操作较少，但效率更高的算法。询问集合S中区间[,]内的最小数，可以看成是询问大于或等于的最小数()。如果没有大于或等于a的数，

13、我们称()=+∞。显然，如果()>，那么说明区间[,]中没有在S中的数，否则()就是区间[,]内的最小数。图1.2给出了一个具体的例子。0123456789101112131415…22277777812121212+∞+∞+∞…图1.2：这里，S当前为{2,7,8,12}，Y=5()在方格的下方表示出来很容易观察到，对很多连续的a，()是相等的。如果S为空，则对于任意的自然数a，()=+∞。否则我们把集合S中的数排序，得到<<<...<2关于线段树，可以参见算法导论和国家集训队的相关论文第3页，共11页(≥1)（因为插入的数保证不会重复）。那么当∈[0,]时()

14、=，当∈[