poj 3349
雪花是否相同
#include#include #include #include using namespace std;#define size 100010int arr[size][6];int n;struct node{ int key; node *next;};node HashTable[size];node HashPool[size];int index = 0;node *getNewNode(){ return &HashPool[index++];}void insert(int key,node *newNode){ node *tmp = &HashTable[key]; newNode->next = tmp->next; tmp->next = newNode;}bool isSame(int a,int b){ sort(arr[a],arr[a]+6); sort(arr[b],arr[b]+6); for(int i = 0; i < 6;i++) { if(arr[a][i] != arr[b][i]) return false; } return true;}int getKey(int a[6]){ int sum = 0; for(int i = 0; i < 6; i++) sum += a[i]; return sum%99991;}bool search(int key,int i){ node *tmp = &HashTable[key]; tmp = tmp -> next; while(tmp != NULL) { int j = tmp->key; tmp = tmp->next; if(isSame(i,j)) return true; } return false;}int main(){ scanf("%d",&n); for(int i = 0; i < n; i++) { for(int j = 0; j < 6; j++) { scanf("%d",&arr[i][j]); } } for(int i = 0; i < n ;i++) { int key = getKey(arr[i]); bool flag = search(key,i); if(flag) { printf("%s\n", "Twin snowflakes found."); return 0; } else { node *newNode = getNewNode(); newNode->key = i; insert(key,newNode); } } printf("%s\n", "No two snowflakes are alike."); return 0;}