久久亚洲国产成人影院,久久国产香蕉视频,99精品国产免费久久久久久下载

pku 3349

2009年7月17日

題目鏈接:PKU 3349 Snowflake Snow Snowflakes

分類:哈希+最小表示

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

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

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

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

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

pku 3349

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜