Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

哈希表做的跟排序一样快,求解释啊~附AC代码2073ms

Posted by hataksumo at 2012-07-09 01:18:42 on Problem 3349
#include<cstdio>
#include<cmath>
#include<cstring>

#define MN 220000
class snowflake
{
public:
	int lengthes[6];
	bool operator == (const snowflake& other)const;
	int getHashCode();
};
bool snowflake::operator==(const snowflake& other)const
{
	bool b;
	int i,j,k;
	for(i=0;i<6;i++)
	{
		b= true;
		for(j=i,k=0;k<6;j=j+1<6?j+1:0,k++)
		{
			if(lengthes[j]!=other.lengthes[k])
			{
				b= false;break;
			}
		}
		if(b)return true;
		b= true;
		for(j=i,k=0;k<6;j=j-1>=0?j-1:5,k++)
		{
			if(lengthes[j]!=other.lengthes[k])
			{
				b= false;break;
			}
		}
		if(b)return true;
	}
	return false;
}
int snowflake::getHashCode()
{
	int key=0;
	int i;
	for(i=0;i<5;i++)
	{
		key+=lengthes[i];
		key+=abs(lengthes[i]-lengthes[i+1]);
	}
	key+=lengthes[5];
	key+=abs(lengthes[5]-lengthes[0]);
	return key%210011;
}
int hash[MN];
struct
{
	snowflake data;
	int next;
}memor[MN];
int mcount;
void iniHashTable()
{
	memset(hash,-1,sizeof(hash));
	mcount = 0;
}
bool addIfConflict(snowflake& sf)
{
	int key = sf.getHashCode();
	int ads;
	for(ads=hash[key];ads!=-1;ads = memor[ads].next)
	{
		if(sf==memor[ads].data)
		{
			return true;
		}
	}
	memor[mcount].data = sf;
	memor[mcount].next = hash[key];
	hash[key] = mcount;
	mcount++;
	return false;
}
int main()
{
	int n;
	bool b;
	snowflake tmp;
	int i;
	while(~scanf("%d",&n))
	{
		b = false;
		iniHashTable();
		while(n--)
		{
			for(i=0;i<6;i++)
			{
				scanf("%d",&tmp.lengthes[i]);
			}
			if(!b)
				b = addIfConflict(tmp);
		}
		if(b)
		{
			printf("Twin snowflakes found.\n");
		}
		else
		{
			printf("No two snowflakes are alike.\n");
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator