学步园

CODE：

/*AC代码：235ms*/
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#define max(a,b) (a>b?a:b)
#define MOD 19997
#define MAXN 100005
using namespace std;
int head[20000],next[MAXN];
int N,K;
int sum[MAXN][33],c[MAXN][33];
int hash(int v[])//hash函数
{
	int i,h=0;
	for(i=1;i<=K;i++)
		h=((h<<2)+(v[i]>>4))^(v[i]<<10);
	h%=MOD;
	h=h<0?h+MOD:h;
	return h;
}
void Init()
{
	int i,j,temp;
	memset(sum,0,sizeof(sum));
	for(i=1;i<=N;i++)
	{
		scanf("%d",&temp);
		for(j=1;j<=K;j++)
		{
			sum[i][j]=sum[i-1][j]+temp%2;
			temp/=2;
		}
		for(j=1;j<=K;j++)
			c[i][j]=sum[i][1]-sum[i][j];
	}
}
void Solve()
{
	int i,j,k,ans=0;
	memset(head,-1,sizeof(head));
	for(i=0;i<=N;i++)//注意这里从0开始
	{
		int h=hash(c[i]);
		//if(i==0)
		// printf("*%d %d\n",i,h);
		bool ok=false;
		for(j=head[h];j!=-1;j=next[j])
		{
			for(k=1;k<=K;k++)
			{if(c[i][k]!=c[j][k]) break;}
			if(k>K)//find，因为每个都不同，所以不必再往下找了
			{
				ans=max(ans,i-j);//注意不能加一
				ok=true;
				break;
			}
		}
		if(!ok)//已经有相同的就不用再插入了
		{
			next[i]=head[h];
			head[h]=i;
		}
	}
	printf("%d\n",ans);
}
int main()
{
	while(scanf("%d%d",&N,&K)!=EOF)
	{
		Init();
		Solve();
	}
	return 0;
}