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

125 Replies

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

代码:
[cpp]#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int hashcode(int *a, int k) {
int p = 0;
for (int i = 0; i < k; i++)
p = ((p << 2) + (a[i] >> 4)) ^ (a[i] << 10);
p %= 99983;
if (p < 0)
p += 99983;
return p;
}

int main() {
int N, K;
scanf("%d%d", &N, &K);

int hash[100000];
memset(hash, 0xff, sizeof(hash));

int (*c)[30];
c = (int(*)[30]) malloc(sizeof(int) * 30 * 100001);
memset(c[0], 0x00, sizeof(c[0]));

hash[hashcode(c[0],K)]=0;

int result = 0;
for (int i = 1; i <= N; i++) {
int data;
scanf("%d", &data);
for (int j = 0; j < K; j++) {
c[i][j]=c[i-1][j];
c[i][j] += (data >> j) & 1;
}
for (int j = K – 1; j >= 0; j–)
c[i][j] -= c[i][0];

int hc = hashcode(c[i], K);
for (;; hc++) {
if (hash[hc] == -1)
break;
bool bingo = true;
for (int j = 0; j < K; j++)
if (c[i][j] != c[hash[hc]][j]) {
bingo = false;
break;
}
if (bingo)
break;
}
if (hash[hc] == -1)
hash[hc] = i;
else
result = (i – hash[hc]) > result ? (i – hash[hc]) : result;
}
printf("%d\n", result);
return 0;
}[/cpp]

125 thoughts on “[ACM] POJ 3274 Gold Balanced Lineup 解题报告, 对数组Hash”

Leave a Reply

Your email address will not be published. Required fields are marked *