Tag Archives: Hash

[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

代码:
Continue reading