信息学集训队作业2in

1、一个简单题及一个简单题-版本 2的解题一个简单题由于题目描述比较简洁明了，这里直接给出原题：一个简单题Time Limit:1s Memory Limit:32768k有 N 个数字，从中选择出连续 M(L1=M=L2)个数，求出他们之和的最大值Input本题有多组测试数据。输入文件第一行有一个数K，表示测试数据的组数。接下来有K 组数据，每组数据第一排有三个数N, L1, L2。接下来的一行有N 个数，每个数之间用一个空格隔开。 1=L1=L2=N, 1=N=200000, -2*109=每个数=2*109Output一个数字，表示求出来的和的最大值S2le Input5 1 34 -1 2

2、 7 -55 3 31 2 7 -9 3S910le OutputSourceSuperMKR（Tongji Online Judge 1071）算法分析：首先最简单的算法当然是枚举所有可能的范围，然后分别求和，取最大值。当然任何人都不会这样做，因为对于同一个左端点，长度相差 1 的两个和，可以轻而易举地由其中一个推出另一个。这样，算法复杂度就只有 O(n(m2-m1)了。但是显然这样的复杂度是无法通过的。刚才的优化是对于左端点相同的和的计算中减少冗余而达到的。那么左端点不同的时候呢？让来看一个例子（第一组样例）：左端点为 1：44-14-1+2左端点为 2：-1-1+2-1+2+7左端点为

3、3：22+72+7-5已经算出了第一行的值，先把所有的数减去 4， 再把 0 改成-1+2+7，就能假如得到第二行。同理，把第二行所有数减去（-1），再把 0 改成 2+7-5，就得到了第三行。并不是每一个数都会对结果产生影响，关心的只是每行的最大值。这样，就想到了一个有力的工具堆！每一次减去的值会被为一个修正值。对于每一个左端点，首先更新出修正值，假如当前左端点在这排书中左数的位置已经大于 m2，那么我们就把最旧的结点删去，因为这个结点并不能对应符合条件的部分和。同样的，如果左端点右数的位置还不小于 m1，就可以再一个新结点。由于每次的新结点之间也有联系，因此计算第一个新结点的时间复杂度是(

4、m2-m1)，后面每一次都是 O(1)，因此总复杂度还是 O(n)级的。在当前的最大值。及删除结点以后，用堆根的值加上修正值得到的结果来刷新这个算法的时间复杂度是 O(n log n)，空间复杂度是 O(n)，足以通过此题。一个简单题版本 2Time Limit:1s Memory Limit:2000k本题描述与 TJU1071“一个简单题”描述完全一样。Input本题中 1=L1=M=L2=N=300000。结果及中间运算过程数字大小的绝对值小于 100000。Output一个数字，表示求出来的和的最大值。S2le Input5 1 34 -1 2 7 -55 3 31 2 7 -9 3S

5、910le OutputH大数据完全随机生成。算法分析：让来比较一下本题与上一题的不同之处：第一：数据范围变大了一些，上限从 200000 增加到 300000。第二：内存限制变小了，只有 2000kB，以至于根本无法一个堆或者类似的数据结构。第三：多了一个重要的提示：大数据完全随机生成。那么，这些条件用处呢？它们会给本题的解法带来哪些变化呢？首先，由于内存限制的缘故，单单输入数据就需要 1200kB 了，就是说，没有条件去开辟另外一个数组了。但是，好在又有这句提示：大数据完全生成。于是就容易想到，仅仅需要一个在平均情况下效率很高的算法，并要求一个在情况下也要达到相同的：效率，就像拉斯维算法那

6、样。仍然列出上题中列出的那当然，现在不可能算出这个表里的所有的值了（时间不够），甚至不能像上题一样下这些和（空间不够）。在上一题中，每一次循环仅仅是删除至多一个结点，再添加至多一个结点，然后用最大值加上“修正值”来求出当前左端点的最优解。那么，容易想到很多情况下这个“最大值”根本没有发生变化，发生变化的情况只有两种：一种是原来的最大值被删去，另一种情况是加入的新结点更大。后一种情况可以直接求出新的最大值，前一种情况呢？由于无法堆，仅仅知道原来的最大值，想在很短的时间求出新的最大值是很难的。但是并不是没有办法！其实方法很简单：对于当前左端点，枚举一遍右端点求最小值即可。也许有人会说，这样的算法难

7、道不是 O(n2)的吗？当然是，但这只是情况的复杂度。而对于本题，只关心平均情况。让来大致地分析一下这个算法平均情况下的复杂度吧：枚举左端点，一共有 O(n)个。每一次假如没有遇到原来的最大值被删去的情况，则时间复杂度为 O(1)，否则为 O(m2-m1)。但是出现这种情况的概率只有 1/(m2-m1)。因此平均情况下整个算法的时间复杂度只有 O(n)！通过这个算法，本题被轻松地解决。这两题有着一样题目描述，大致相当的数据范围，却有着截然不同的算法，原因在哪里？一是空间的限制，二是数据的特点。这也就启示，解决题目的时候不但要抓住题目本身的特点，还要利用数据的特点和时空的限制，选择合适的算法。附

8、录：在写完这片解题的第二天，我在网上听说有方法可以用情况下 O(n)的同学 2004 年冬令营中的时间复杂度的算法来通过这两题。通过参考。这里简单地写一下。，我找到了这里仍然需要选择一个合适的数据结构来“最大值”。但是，这里并不是堆最合适，而是线性表！每次操作，向线性表后端一个元素。如果它比它前面一个元素大，那么它前面一个元素不可能成为最大值，直接删去，将最后一个元素向前移。这样，整个线性表就成为了单调下降。当删去结点（一定从最前面删除），直接后移指针即可。因为线性表单调下降，后一个元素一定就是新的最大值。然后再说一下空间问题。这样的做法在第二题中至少需要大约 2400kB 的内存(数左 端点为 1：44-14-1+2左 端点为 2：-1-1+2-1+2+7左 端点为 3：22+72+7-5最大值的线性表共享 1200kB，然后时间需要 1200kB)，会溢出。据和结点的对于这个问题我还没有找到很好的解决办法。目前想出来的最好的方法就是对于结点插入时间的数组，不妨大胆地开小一点。因为本题大数据由随机生成，虽然数组不够大，但并的时间复杂度由 O(n2“) 降”的空间使用“大大节约”。不会溢出。这样，前一个