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