| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
哈希表做的跟排序一样快,求解释啊~附AC代码2073ms#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator