首页 > 代码库 > Hash poj3349 Snowflake Snow Snowflakes
Hash poj3349 Snowflake Snow Snowflakes
题意:判断是否有两片一样的雪花。 Hash第一题,基本是抄的。
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <stack> #include <queue> #include <vector> #include <map> #include <string> #include <iostream> using namespace std; char str[]={ "No two snowflakes are alike." }; char str1[]={ "Twin snowflakes found." }; const int INF= 9997; struct Node { int a[6]; int hash_val; }node [INF][10]; int len[INF]; int get_hash(Node & a) { a.hash_val=0; for ( int i=0;i<6;i++) a.hash_val+=a.a[i]; return a.hash_val %= INF; } int match(Node a,Node b) { int cw=0; int ancw=0; for ( int i=0;i<6;i++){ if (a.a[0]==b.a[i]){ int cw=1; int ancw=1; for ( int j=1;j<6;j++){ if (a.a[j]!=b.a[(i+j)%6]){ cw=0; } } for ( int j=1;j<6;j++){ if (a.a[j]!=b.a[(i-j+6)%6]){ ancw=0; } } if (cw||ancw) return 1; } } return 0; } int find_hash(Node a) { int val=a.hash_val; for ( int i=0;i<len[val];i++){ if (match(a,node[val][i])) return 1; } return 0; } int main() { Node node1; int flag=0; int n; scanf ( "%d" ,&n); memset (len,0, sizeof (len)); while (n--){ for ( int i=0;i<6;i++) scanf ( "%d" ,&node1.a[i]); int val=get_hash(node1); if (flag) continue ; if (find_hash(node1)) flag=1; node[val][len[val]++]=node1; //printf("%d ",len[val]); } if (flag){ printf ( "%s\n" ,str1); } else printf ( "%s\n" ,str); return 0; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。