poj 3349本來不想看discuss了，不過因?yàn)檫@道題拖太久了，所以還是看了一下^_^，不過算法還是自己想的。
之前程序已經(jīng)做好了，但一直WA，估計(jì)不是算法的錯(cuò)，而是程序的錯(cuò)。
這道題給了兩個(gè)啟示：
1. 點(diǎn)的哈希函數(shù)：我是把坐標(biāo)值（六個(gè)整數(shù)值）求和模149997，哈希表長度是150000。嚴(yán)蔚敏的《數(shù)據(jù)結(jié)構(gòu)》指出：模的數(shù)可以選為質(zhì)數(shù)或不包
含小于20的質(zhì)因數(shù)的合數(shù)。另外這個(gè)數(shù)要盡量接近哈希表長度，這樣才能有效利用哈希表的空間，而不會使得數(shù)據(jù)集中在前面。
2. 有大量輸入時(shí)（100000×6個(gè)整數(shù)），每個(gè)整數(shù)最長有7位，這時(shí)用getchar()輸入字符再轉(zhuǎn)成整數(shù)會比scanf()輸入整數(shù)快很多?。?438ms VS 610ms）
3. 這道題的數(shù)據(jù)可以是這樣：1 2 3 1 5 6 與 1 5 6 1 2 3是同一朵雪花，但我之前的程序沒有判斷出來。具體看下面程序里的equal函數(shù)。
1 #include <iostream>
2 #include <set>
3
4 using namespace std;
5
6 const int maxn=150000;
7 struct node{
8 node(){idx=-1;next=NULL;}
9 node(int id){idx=id;next=NULL;}
10 int idx;
11 node *next;
12 }table[maxn];
13
14 int a[100010][6];
15 int n;
16 int hash(int *a)
17 {
18 //a[6]=0;
19 __int64 sum=0;
20 for(int i=0;i<6;i++) sum+=a[i];//*a[i]);
21 return sum%149997;
22 }
23
24 void init()
25 {
26 for(int i=0;i<n;i++){
27 table[i].idx=-1;
28 table[i].next=NULL;
29 }
30 }
31
32 bool equal(int i,int j)
33 {
34 //if(a[i][6]!=a[j][6]) return false;
35 int x,yy=0,y;
36 int flag=0;
37 while(yy<6){
38 while(yy<6 && a[j][yy]!=a[i][0]) yy++;
39 if(yy==6) return false;
40 y=yy;
41 for(x=0;x<6;x++){
42 if(a[i][x]==a[j][y]){
43 y++;
44 if(y==6) y=0;
45 }
46 else break;
47 }
48 if(x==6) return true;
49 y=yy;
50 for(x=0;x<6;x++){
51 if(a[i][x]==a[j][y]){
52 y--;
53 if(y==-1) y=5;
54 }
55 else break;
56 }
57 if(x==6) return true;
58 yy++;
59 }
60 return false;
61 }
62
63 // 讀入字符并轉(zhuǎn)成整數(shù)
64 void readNumber(int i)
65 {
66 char ch;
67 //ch=getchar();
68 ch=getchar();
69 while(ch==' ') ch=getchar();
70 int x=0;
71 while(ch!=' ') {x*=10;x+=ch-'0';ch=getchar();}
72 a[i][0]=x;
73
74 ch=getchar();
75 while(ch==' ') ch=getchar();
76 x=0;
77 while(ch!=' ') {x*=10;x+=ch-'0';ch=getchar();}
78 a[i][1]=x;
79
80 ch=getchar();
81 while(ch==' ') ch=getchar();
82 x=0;
83 while(ch!=' ') {x*=10;x+=ch-'0';ch=getchar();}
84 a[i][2]=x;
85
86 ch=getchar();
87 while(ch==' ') ch=getchar();
88 x=0;
89 while(ch!=' ') {x*=10;x+=ch-'0';ch=getchar();}
90 a[i][3]=x;
91
92 ch=getchar();
93 while(ch==' ') ch=getchar();
94 x=0;
95 while(ch!=' ') {x*=10;x+=ch-'0';ch=getchar();}
96 a[i][4]=x;
97
98 ch=getchar();
99 while(ch==' ') ch=getchar();
100 x=0;
101 while(ch!=10 && ch!=' ')
102 {
103 x*=10;
104 x+=ch-'0';
105 ch=getchar();
106 }
107 a[i][5]=x;
108 if(ch==' '){
109 ch=getchar();
110 while(ch!=10) ch=getchar();
111 }
112 }
113
114 bool solve()
115 {
116 scanf("%d",&n);
117 getchar();
118 //init();
119 int i,flag=0;
120 node *tmp,*tmp2;
121 for(i=0;i<n && !flag;i++){
122 //scanf("%d%d%d%d%d%d",&a[i][0],&a[i][1],&a[i][2],&a[i][3],&a[i][4],&a[i][5]);
123 readNumber(i);
124 int code=hash(a[i]);
125 if(table[code].idx==-1){
126 table[code].idx=i;
127 }else{
128 //flag=0;
129 tmp2=NULL;
130 tmp=&(table[code]);
131 while(tmp!=NULL){
132 if(equal(i,tmp->idx)) {flag=1;break;}
133 tmp2=tmp;
134 tmp=tmp->next;
135 }
136 if(!flag) tmp2->next=new node(i);
137 }
138 }
139 //printf("%d\n",i);
140 /*
141 int aa,bb,cc,xx,yy,zz;
142
143 if(i<n){
144 for(;i<n;i++) scanf("%d%d%d%d%d%d",&aa,&bb,&cc,&xx,&yy,&zz);
145 }
146 */
147 if(flag) return true;
148 return false;
149 }
150
151 int main()
152 {
153 //freopen("in.txt","r",stdin);
154 if(solve()) printf("Twin snowflakes found.\n");
155 else printf("No two snowflakes are alike.\n");
156 return 1;
157 }
158
159
160