蜗牛の狂奔笔记
对于蜗牛来说,狂奔虽不代表极速,但展现的却是一种拼尽全力的姿态........
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
阅读(293)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 蜗牛也Coding
<
2009年7月
>
日
一
二
三
四
五
六
28
29
30
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
1
2
3
4
5
6
7
8
导航
C++博客
首页
新随笔
联系
聚合
管理
统计
随笔 - 78
文章 - 0
评论 - 96
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(8)
给我留言
查看公开留言
查看私人留言
随笔档案
(78)
2011年7月 (1)
2011年4月 (1)
2010年11月 (4)
2010年10月 (4)
2010年9月 (2)
2010年8月 (7)
2010年3月 (1)
2010年2月 (5)
2009年12月 (2)
2009年10月 (1)
2009年9月 (1)
2009年8月 (16)
2009年7月 (31)
2009年6月 (2)
搜索
积分与排名
积分 - 91683
排名 - 259
最新评论
1. re: 关于 OpenGl
太谢谢了。
--袁锋
2. re: 关于 OpenGl
太感谢!
--芙
3. re: 关于MAC系统win 7虚拟机不能上网的问题[未登录]
.vmx文件在哪里?
--a
4. re: MFC中如何将 CFormView放置到一个CDockablePane中
注释掉的创建部分,指针调用
为何不用友元类声明下,就可以用了的。CreateOne,有点绕。
感谢博主分享。
--ren
5. re: 关于 OpenGl
非常感谢~~
--无叶莲
阅读排行榜
1. pragma comment的使用(转)(17177)
2. MFC中如何将 CFormView放置到一个CDockablePane中(8154)
3. (转)关于OpenGL的安装(4821)
4. 关于 OpenGl(4391)
5. VC 界面窗口,静态分割后如何锁定分隔条或限制分隔条的移动范围(4272)
评论排行榜
1. 据说是来自chrome的代码里的一个模板(13)
2. 关于 OpenGl(10)
3. Visual Studio 历史简介(转)(6)
4. pku 1200(6)
5. 推免--北航(5)