[ACM] POJ 3274 Gold Balanced Lineup 解题报告, 对数组Hash

算法很简单, 就是记录各个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

代码:
Read More

[ACM] POJ 3277 City Horizon 解题报告, 线段树+离散化

第一道线段树.. 略难。 引用忘了哪看的一句话“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了。”

代码:

Read More

[ACM] POJ 1230 贪心, 数据结构

挺简单的算法我没想出来..

考虑最左边的需要移除墙的列。这列是必定要移除一些墙的。
不妨移除右边界较大的那些墙。
实现的时候,可以用基数排序的方式来找到右边界较大的墙。
开两个数组如下:
map[i][j] = { 第i列中,从该列开始向右延伸,长度为j的墙的数目}
cnt[i] = {第i列中墙的数目}
这样代码比较方便,速度也快。          ——荣誉属于糯米

糯米的这个数据结构非常棒, 我做了一点改进: 糯米记录了右边还有多长的墙, 实际上只要记录右边墙的边界就可以了, 省掉一些计算和思维复杂度
所以我的代码精简一点, 看我的吧 🙂

这种题一眼看上去像DP, 我看了点东西说DP和贪心有很多相似之处, 比如都是找最优子结构. 区别在于贪心从最优子结构里选出一个或几个就行. 具体有什么区别也没太搞清楚, 感觉DP有一个图的延伸, 每个状态都可能被多次使用, 而贪心不会.

代码点下面:
Read More