算法很简单, 就是记录各个feature的累积和数组, 数组稍作处理, 只要能够比较 [让能够相减得出答案的两个数组] 的”形状”.
比如
111 111 000 110 221<= 110 111 332 110 010 342 120 001 342 120 100 443<= 110 010 453 120
中间一列的221和443的”形状”一样, 也就是相减能得到答案, 所以稍作处理都减去最右边的数即可, 方便比较.
问题是者离散化以后也有100000的数据怎么记录, 好吧我开始用的二叉树后来发现想错了..
无耻的Google以后发现对数组Hash的方法.. 很汗颜 太洋气了.. 跑2xxMS
代码:
Continue reading
第一道线段树.. 略难。 引用忘了哪看的一句话“10亿的的数据规模是任何数据结构都无能为力的，所以必须离散化”。因为略复杂我用class写的…yzhw牛说“线段树编程复杂度太高，一般用树狀数组或者STL set。不要class，class运行爆慢” 但是哥就是用class和链表过了，怎样！！ 1200ms.. 不过后来看了一下Google到用Pascal的蒟蒻牛的代码，发现树狀数组果然好用！
hw给了我篇论文，我发现现在的程度知道了一个数据结构的意思&&一些优化比如“lazy”，写出来的东西details上面大家都差不多的。比如这道题目的lazy我也是加了个-1作标签说明下面的节点需要递归确认，即这一块不是一大块一样的
优化有二：
1. compress() 每次插入完一个building以后沿着树往下看有没有标记为-1但是左右子树height（toLoad）相等的，如果有合并左右子树。实践证明这个优化对这题的数据用处不大，反而拖到了1800ms…
2. 这个厉害了，没它我算5000的数据都要跑半分钟，而还有两组40000的数据，加了这优化4w的秒出。也是刚刚那篇里提到的“观察发现，线段树的建树、统计操作已难以再优化，但插入操作却任可以优化。由于一开始房子的高度无序，所以每次插入如果全部包含不能直接赋值，还需要向下递归左右子树。其实我们可以先将房子的高度排序，然后再依次插入，这样一旦全部包含就可以直接赋值，程序的效率大大提高。这样这道题就可以AC了。”
代码：
挺简单的算法我没想出来..
考虑最左边的需要移除墙的列。这列是必定要移除一些墙的。
不妨移除右边界较大的那些墙。
实现的时候，可以用基数排序的方式来找到右边界较大的墙。
开两个数组如下：
map[i][j] = { 第i列中，从该列开始向右延伸，长度为j的墙的数目}
cnt[i] = {第i列中墙的数目}
这样代码比较方便，速度也快。 ——荣誉属于糯米
糯米的这个数据结构非常棒, 我做了一点改进: 糯米记录了右边还有多长的墙, 实际上只要记录右边墙的边界就可以了, 省掉一些计算和思维复杂度
所以我的代码精简一点, 看我的吧 🙂
这种题一眼看上去像DP, 我看了点东西说DP和贪心有很多相似之处, 比如都是找最优子结构. 区别在于贪心从最优子结构里选出一个或几个就行. 具体有什么区别也没太搞清楚, 感觉DP有一个图的延伸, 每个状态都可能被多次使用, 而贪心不会.
代码点下面:
Continue reading
