POJ - 3274 Gold Balanced Lineup解题报告

这个题用dp(k*n^2)就超时了。想办法通过转换数据，把原问题转换成在很多数中查找相同数的问题，然后就可以用哈希表，把查找过程由O(n)变为O(1); 

#include<iostream>#include<math.h>#include<string.h>#include<stdio.h>#include<math.h>#define N 100500#define MOD 100000using namespace std;int n,k,m;bool a[N][30]={0};//第i个数的第j个二进制位为a[i][j] int b[N][30]={0};//第1个数到第i个数的第j二进制位一共有b[i][j]个1； int c[N][30]={0};//c[i][j]=b[i][j]-b[i][0]; int hash[N]={0};int next[N]={0};int s=0;void input(){	for(int i=1;i<=n;i++)	{		int x;		scanf("%d",&x);		for(int j=0;j<k;j++)		{			a[i][j]=x&1;			x=x>>1;		}	}}void ceshi1(){	for(int i=0;i<=n;i++)	{		for(int j=0;j<k;j++)		{			cout<<c[i][j]<<" ";		}		cout<<endl;	}}void init(){	for(int i=1;i<=n;i++)	{		for(int j=0;j<k;j++)		{			if(a[i][j]==1)			{				b[i][j]=b[i-1][j]+1;			}			else 			{				b[i][j]=b[i-1][j];			}		}	}	for(int i=1;i<=n;i++)	{		for(int j=0;j<k;j++)		{			c[i][j]=b[i][j]-b[i][0];		}	}}void find(int a,int b){	if(a>b)	{		int t;t=a;a=b;b=t;	}	for(int i=0;i<k;i++)	{		if(c[a][i]!=c[b][i])return;	}	if(s<b-a)s=b-a;	return;}void my_hash()//对c数组建立哈希表 {	for(int i=0;i<=n;i++)	{		int x=0;		for(int j=0;j<k;j++)		{			x=((x+c[i][j]*c[i][j])%MOD);		}		int u=hash[x];		find(0,i);		//cout<<x<<" ";		while(u)		{			find(u,i);//检查c[u]和c[i]是否相等，如果相等，那是否可以更新max;			u=next[u];		}		next[i]=hash[x];		hash[x]=i;			}}int pf(int a,int b){	int x=1;	for(int i=0;i<b;i++)	{		x=x*a;	}	return x;}int main(){	while(cin>>n>>k)	{		s=0;		m=pf(2,k)-1;		memset(a,0,sizeof(a));		memset(b,0,sizeof(b));		memset(c,0,sizeof(c));		memset(hash,0,sizeof(hash));		memset(next,0,sizeof(next));		input();		init();		//ceshi1();		my_hash();		cout<<s<<endl;	}	}