今天上午是一套题, 而且不知道是谁出的......
题目的下载链接:task0115.pdf
但是题还是比较简单的. 第一题大概看了一眼, 然后想起去年省选上的一道题, 讲的是常数优化, 优化的就是一个排序 (结果我去优化了随机生成器 = =) .
所以第一道题我就果断写了一个基数排序, 差不多是一个常数为十几的 \(O(n)\). 后来说有 这样一种神奇的做法:
我们可以看出这一个序列一定是一个随机生成器, 所以在数学期望上就有一堆很好的性质. 现在我们打算用快排 (但是我们并不要把所有的数据都排一遍序, 而只是要找出 第 \(k\) 大的数字, 所以我们就随机从这段序列里选取一个数, 在期望上它应该恰好大于一半的数字而小于另一半. 我们如此就可以类似二分的找出第 \(k\) 大的数. 那么 这个正解的算法复杂度应该是一个常数很小的 \(O(n)\).
但是然后又有一种做法:
听说 STL 里面有
nth_number()这个函数AuA. ......
然后听说这位同学写成了第 \(k\) 小然后还没有对拍 (样例神级巨坑第 \(k\) 小和第 \(k\) 大居然一样)
第二题发现可以维护这么一堆东西: 靠前的最长连续子段和, 靠后的最长连续子段和, 不一定靠前或靠后的最长连续子段和. 这一堆东西加在区间里维护发现可以在区间内 \(O(1)\) 转移, 然后就想到, 区间查询果断 Splay 啊...... 于是就直接上了 Splay~
出来以后大家接连表示第二题线段树好好写啊 (?) , 然后我就惊呆了 (不是用 Splay 吗). 后来想想没有修改其实线段树也可以的说...... 于是此题被爆成了 70 分.
那么满分做法是什么呢? 其实是这样的. 由于查询次数太多, 而我们的做法在实质上其实是 \(O(m \log n)\) 的. 也就是说查询的复杂度必须压到 \(O(1)\) 以下, 不然最后几个点是无法 拿到分的. 就有了这样一个解法:
考虑一段要查询的区间, 我们发现线段树上很多个分治块都是冗余的, 又考虑到本来这查询都是可以维护的, 而且是 \(O(1)\) 转移, 所以我们试图预处理离线化数据, 然后就可以在常数时间内获得结果.
现在发现这样一个问题. 线段树的每一个小区间上的中点, 是一个有神奇性质的点. 任何一段可在线段树上查询的区间, 必定最多只有必要经过一个中点. 而且经过的这个中点所在区间一定完全包含要查询的区间 (这个可以意会).
于是我们发现, 这个神奇的性质可以让我们预处理每个中点左边、右边一共 \(n \log n\) 个区间的最长连续子段和, 然后最后算法的复杂度是 \(O(n \log n + m)\).
Splay 不是万能的, 但没有 Splay 是万万不能的.
第三题其实是一个树形 DP 加分治. 但是到现在我还是没有搞懂树分治是什么乱七八糟的东西, 所以就不说了.
这次考试我应该大概在 180 分左右, 然后全场排第 14 名.
有点慌, 因为后面还有八九十个人~
下午是余行江老师讲数据结构, 虽然大部分都会了, 但是还是要在这里发一下下午的 演示文稿的. 下载链接:ppt.pdf
求 @hld67890 好强好强的大神帮续实力啊