学步园

Problem Address：http://poj.org/problem?id=3274

【前言】

本来打算用二分去做。

WA了一次后发现那样是错误的。

参考了别人的文章，第一次用到了哈希。

【思路】

具体参考：http://hi.baidu.com/aconly/blog/item/9d1ed1122a29af876538db0b.html

里面的转换很巧妙。

主要要注意数组的哈希。

要使用开放寻址法，因为哈希不能解决冲突，所以要注意对冲突串的重判。

然后设计一个比较好的哈希函数就可以了。

此外还要注意对cow[0]哈希为0。

【代码】

#include <iostream>
using namespace std;

const int maxn = 100000;
const int maxk = 30;
const int big_prime = 99983;

int cow[maxn+1][maxk+1] = {0};
int hash[1000000];

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

int main()
{
	int n, k, x;
	int i, j;
	int p, ans;
	memset(hash, -1, sizeof(hash));
	scanf("%d %d", &n, &k);
	for (i=1; i<=n; i++)
	{
		scanf("%d", &x);
		for (j=0; j<k; j++)
		{
			cow[i][j] = x%2;
			x >>= 1;
		}
	}
	for (j=0; j<k; j++)
	{
		for (i=1; i<=n; i++)
		{
			cow[i][j] += cow[i-1][j];
		}
	}
	for (i=1; i<=n; i++)
	{
		for (j=1; j<k; j++)
		{
			cow[i][j] -= cow[i][0];
		}
		cow[i][0] = 0;
	}
	ans = 0;
	hash[hashcode(cow[0], k)] = 0;
	for (i=1; i<=n; i++)
	{
		p = hashcode(cow[i], k);
		while(hash[p]!=-1)
		{
			for (j=1; j<k; j++)
			{
				if (cow[i][j]!=cow[hash[p]][j])
					break;
			}
			if (j==k)
			{
				if (i-hash[p]>ans)
					ans = i - hash[p];
				break;
			}
			p++;
		}
		if (hash[p]==-1)
			hash[p] = i;
	}
	printf("%d\n", ans);
	return 0;
}