[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

代码:

#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;
}

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

Leave a Reply

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