bzoj 1702: [Usaco2007 Mar]Gold Balanced Lineup 平衡的队列【hash】

我%&&……&（）&%？？？？？

双模hashWA，unsigned long longAC，而且必须判断hash出来的数不能为0？？？？

我可能学了假的hash

这个题求个前缀和，然后目标是找到距离当前位置最远，且能使这两个数组差分后2—k位相同

hash把差分后数组的2到k位压起来即可，用map存这个hash值最早出现的位置

但是我还是不明白为啥hash值不能为0啊？？

#include<iostream>

#include<cstdio>

#include<map>

using namespace std;

const int N=200005,m1=1e9+7,m2=1e9+9;

int n,m,c[35],a[35],ans;

// map<pair<int,int>,int>mp;

map<unsigned long long,int>h;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int zhao(int x)

{

    unsigned long long sum=0;

    for(int i=2;i<=m;i++)

		sum=sum*233+(unsigned long long)a[i];

    if(!h[sum]&&sum)//?????为啥sum不能为0????

		h[sum]=x;

    return h[sum];

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<=n;i++)

	{

		int x=read(),p=0,q=0;

		for(int j=1;j<=m&&x;j++,x>>=1)

			if(x&1)

				c[j]++;

		for(int j=2;j<=m;j++)

			a[j]=c[j]-c[1];

		//为啥双哈希是错的啊？？？

		for(int j=2;j<=m;j++)

			p=(7ll*p+1ll*a[j])%m1,q=(7ll*q+1ll*a[j])%m2;

		if(mp[make_pair(p,q)])

			ans=max(ans,i-mp[make_pair(p,q)]);

		else

			mp[make_pair(p,q)]=i;

		ans=max(ans,i-zhao(i));

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

bzoj 1702: [Usaco2007 Mar]Gold Balanced Lineup 平衡的队列【hash】

最新文章

热门文章