欧美成年人视频,欧美日韩一区二区精品,亚洲国产精品va在线看黑人

對于蝸牛來說，狂奔雖不代表極速，但展現的卻是一種拼盡全力的姿態........

pku 3349

2009年7月17日

題目鏈接:PKU 3349 Snowflake Snow Snowflakes

分類:哈希+最小表示

題目分析與算法模型
先hash,然后在哈希解決沖突時根據最小表示法判斷哈希表中的同一地址的雪花是否同構即可,若同構則退出,否則一直找,找到鏈表的末尾,加入該雪花,直到n片雪花都已經hash過,若還沒有找到,說明不存在同構的雪花了.......關于Hash,我是采用將雪花的六條邊長的和模上一個素數作為關鍵字,當然Hash的方法有很多種,應該有更好的,呵呵.......關于最小表示法可參考周源的國家隊論文---><<淺析“最小表示法”思想在字符串循環同構問題中的應用>>

Code:

1

#include<stdio.h>
2

#include<string.h>
3

#include<math.h>
4

#define max 250000
5

#define prime 129997
6

bool finish;
7

int n,i,j,sum,he,len,pos;
8

char ch;
9

struct node
10

{
11

int next,zhi[7];
12

}hash[max];
13

void init()
14

{
15

for(i=0;i<max;i++)hash[i].next=-1;
16

}
17

bool compare(int a[],int b[])
18

{
19

bool res;
20

int p1=0,p2=0,p3=0,t1[15],t2[15],t3[15],q1=0,q2=0,q3=0;
21

for(i=0;i<6;i++)
22

{
23

t1[i]=a[i];
24

t1[i+6]=a[i];
25

t2[i]=b[i];
26

t2[i+6]=b[i];
27

t3[i]=a[5-i];
28

t3[i+6]=a[5-i];
29

}
30

while(1)
31

{
32

if(p1>5||p2>5)
33

{
34

res=false;
35

break;
36

}
37

if(q1-p1>=6)
38

{
39

res=true;
40

break;
41

}
42

if(t1[q1]==t2[q2])
43

{
44

q1++;
45

q2++;
46

}
47

else if(t1[q1]>t2[q2])
48

{
49

p1=q1+1;
50

q1=p1;
51

q2=p2;
52

}
53

else
54

{
55

p2=q2+1;
56

q2=p2;
57

q1=p1;
58

}
59

}
60

p2=0;q2=0;
61

if(res)return res;
62

while(1)
63

{
64

if(p3>5||p2>5)
65

{
66

res=false;
67

break;
68

}
69

if(q3-p3>=6)
70

{
71

res=true;
72

break;
73

}
74

if(t3[q3]==t2[q2])
75

{
76

q3++;
77

q2++;
78

}
79

else if(t3[q3]>t2[q2])
80

{
81

p3=q3+1;
82

q3=p3;
83

q2=p2;
84

}
85

else
86

{
87

p2=q2+1;
88

q2=p2;
89

q3=p3;
90

}
91

}
92

return res;
93

}
94

void Hash(int kk)
95

{
96

int now=kk%prime;
97

while(hash[now].next!=-1)
98

{
99

if(compare(hash[pos].zhi,hash[hash[now].next].zhi))
100

{
101

finish=true;
102

return;
103

}
104

else now=hash[now].next;
105

}
106

hash[pos].next=-1;
107

hash[now].next=pos;
108

pos++;
109

}
110

int main()
111

{
112

scanf("%d",&n);
113

finish=false;
114

pos=130000;
115

init();
116

while(n--)
117

{
118

sum=0;
119

for(i=0;i<6;i++)
120

{
121

hash[pos].zhi[i]=0;
122

ch=getchar();
123

while(!(ch>='0'&&ch<='9'))ch=getchar();
124

125

while((ch>='0'&&ch<='9'))
126

{
127

hash[pos].zhi[i]*=10;
128

hash[pos].zhi[i]+=ch-'0';
129

ch=getchar();
130

}
131

sum+=hash[pos].zhi[i];
132

}
133

if(!finish)Hash(sum);
134

}
135

if(finish)printf("Twin snowflakes found.\n");
136

else printf("No two snowflakes are alike.\n");
137

return 0;
138

}
139

小結: 這道題目著實郁悶了我一天,先是TLE,再是WA,然后就在TLE和WA之間徘徊,在WA了N次之后終于AC了,錯的原因竟然是Hash的函數出了一點錯,即下面代碼中的pos的起始值錯了.不該為0的,而因從大于表長的某個數開始,因為我的Hash表,的前面的m個(m即為表長)元素是作為結點的,所以不存值的,但是我寫的時候卻存了值,這就是WA那么多次的原因所在,淚奔.......

posted on 2009-07-17 20:04 蝸牛也Coding 閱讀(317) 評論(0) 編輯收藏引用