poj 3349本来不想看discuss了,不过因为这道题拖太久了,所以还是看了一下^_^,不过算法还是自己想的。
之前程序已经做好了,但一直WA,估计不是算法的错,而是程序的错。
这道题给了两个启示:
1. 点的哈希函数:我是把坐标值(六个整数值)求和模149997,哈希表长度是150000。严蔚敏的《数据结构》指出:模的数可以选为质数或不包
含小于20的质因数的合数。另外这个数要尽量接近哈希表长度,这样才能有效利用哈希表的空间,而不会使得数据集中在前面。
2. 有大量输入时(100000×6个整数),每个整数最长有7位,这时用getchar()输入字符再转成整数会比scanf()输入整数快很多!(2438ms VS 610ms)
3. 这道题的数据可以是这样:1 2 3 1 5 6 与 1 5 6 1 2 3是同一朵雪花,但我之前的程序没有判断出来。具体看下面程序里的equal函数。
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 // 读入字符并转成整数
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