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 |
2172MS,一次通过好爽!!!附代码其他不多说,说说如何判重的,把两个数组中的一个复制后接在其后面,形成一个长度为12的长数组,然后另一个短数组与其进行匹配,考虑到顺逆时针的问题,需要把短数组逆置一下再匹配一次,如果有一次匹配成功说明是同一片雪花。 请指教!! #include <stdio.h> #define M 100003 struct node{ int a[6]; struct node* next; }; typedef node snowflake; // 哈希函数 unsigned int hash(int a[]){ int i=0,cnt=0; for(i=0;i<6;i++){ cnt+=a[i]; } return cnt%M; } // 判重函数 int judge(int a[6],int b[6]){ int c[12]={0}; int i,j,k; for(i=0;i<6;i++){ c[i]=c[6+i]=a[i]; } //for(i=0;i<12;i++) printf("%d ",c[i]); for(i=0;i<=6;i++){ j=0; for(k=i;k<=(i+5);k++){ if(c[k]==b[j++]) continue; else break; } if(j==6) return 1; } return 0; } // 逆置函数 int* reverse(int a[6]){ int i; for(i=0;i<3;i++){ a[i]=a[i]^a[5-i]; a[5-i]=a[5-i]^a[i]; a[i]=a[i]^a[5-i]; } return a; } int main() { snowflake* table[M]={NULL}; snowflake* temp; snowflake snow[M]; int i,j,k,n; scanf("%d",&n); for(i=0;i<n;i++){ for(j=0;j<6;j++) scanf("%d",&(snow[i].a[j])); } for(i=0;i<n;i++){ k=hash(snow[i].a); if(table[k]==NULL){ snow[i].next=table[k]; table[k]=&snow[i]; } else{ temp=table[k]; while(temp!=NULL){ if(judge(temp->a,snow[i].a)==0&&judge(temp->a,reverse(snow[i].a))==0){ temp=temp->next; } else{ printf("%s\n","Twin snowflakes found."); return 0; } } snow[i].next=table[k]; table[k]=&snow[i]; } } printf("%s\n","No two snowflakes are alike."); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator