POJ - 3274 Gold Balanced Lineup解题报告

题目大意：

给你n（100,000）个数，让你把他们都变成k位（30）2进制的数，然后，让你找到最长的该数列的一个子串（连续的），该子串满足：这些数化为2进制的数之后，这k位，每位的1的个数相同。

思路：

这个题用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 100000
using 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;
	}
	
}