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 |
哈希代码。。。#include <iostream> #include <stdio.h> using namespace std; const int M=99991; int n; struct snow { int f[6]; int v; struct snow *next; }; snow s[99992]; void init(snow a) { a.v=0; a.next=NULL; } int hash(int flake[6]) { int i,sum; sum=0; for(i=0;i<6;i++) sum=sum+flake[i]; return sum%M; } void insert(snow *temp,int flake[6]) { int j; if(temp->v==0) { for(j=0;j<6;j++) temp->f[j]=flake[j]; temp->v=1; temp->next=new snow; temp->next->v=0; } else { temp=temp->next; insert(temp,flake); } } int judge(int a[6],int b[6]) { int i,j; for(i=0;i<6;i++) { if(a[0]==b[i]) { for(j=1;j<6;j++) if(a[j]!=b[(j+i)%6]) break; if(j==6) return 1; for(j=1;j<6;j++) if(a[6-j]!=b[(i+j)%6]) break; if(j==6) return 1; } } return 0; } int search(snow *temp,int flake[6]) { while(temp->v) { if(judge(temp->f,flake)==1) return 1; else temp=temp->next; } if(temp->v==0) return 0; } int main() { int i,j,ok; int flake[6]; snow *temp; for(i=0;i<99992;i++) init(s[i]); scanf("%d",&n); ok=0; for(i=0;i<n;i++) { for(j=0;j<6;j++) { scanf("%d",&flake[j]); } if(ok==0) { temp=&s[hash(flake)]; if(search(temp,flake)==0) insert(temp,flake); else ok=1; } } if(ok==0) printf("No two snowflakes are alike.\n"); else printf("Twin snowflakes found.\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