关于哈希我有些神奇的想法
题面
POJ 3349 Snowflake Snow Snowflakes
一片雪花有六个臂，用六个整数来表示（0<= Li <= 1000000）。
定义两片雪花相同当且仅当雪花经过一系列旋转或翻折后可以重合。
输入N(1<=N<=100000)片雪花的信息，求这些雪花中是否有两片相同。
常规哈希
考虑到各个臂长是地位相等的，所以类似进制哈希的想法可以放弃了。
可以考虑连加或连乘的哈希函数，使得各个臂长值对哈希值的贡献地位相等。
然后用哈希挂链的方法来解决冲突的问题。
相同的雪花一定会挂在同一条链上，如何确定两个哈希值相同的雪花相同?
事实上，将臂长数组视作一个环，取环的字典序最小的表示序列可唯一确定一种雪花。
如
4 5 6 1 2 3 -> 1 2 3 4 5 6
5 3 1 6 7 2 -> 1 3 5 2 7 6
这个方法难度不大。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int lengths[100010][7];
int orderMat[20][10];
int hashST[65537];
bool ordered[100100];
int orderArray[7];
int tmp[7];
void orderLengths(int x)
{
for(int i=0;i<6;i++){
if(tmp[i]>orderArray[i]) return ;
else if(tmp[i]<orderArray[i]) break;
}
for(int i=0;i<6;i++) orderArray[i]=tmp[i];
}
void getOrder(int x)
{
int minn = 0x7f7f7f7f;
memset(orderArray,0x7f7f7f7f,sizeof(orderArray));
for(int i=0;i<6;i++) minn=min(minn,lengths[x][i]);
for(int i=0;i<6;i++)
{
if(lengths[x][i]==minn)
{
int j=0;
if(lengths[x][(i+5)%6]>=lengths[x][(i+1)%6])
{
for(j=0;j+i<6;j++) tmp[j]=lengths[x][i+j];
for(int jj=0;jj<i;jj++,j++) tmp[j]=lengths[x][jj];
orderLengths(x);
}
if(lengths[x][(i+5)%6]<=lengths[x][(i+1)%6])
{
j=0;
for(j=0;i-j>=0;j++) tmp[j]=lengths[x][i-j];
for(int jj=5;jj>i;jj--,j++) tmp[j]=lengths[x][jj];
orderLengths(x);
}
}
}
for(int i=0;i<6;i++) lengths[x][i]=orderArray[i];
minn--;
}
int hashCalc(int x)
{
int hashV=0;
for(int i=0;i<6;i++) hashV=(hashV+lengths[x][i])%65537;
return hashV;
}
bool judge(int a,int b)
{
getOrder(a);
getOrder(b);
for(int i=0;i<6;i++){
if(lengths[a][i]!=lengths[b][i]) return false;
}
return true;
}
bool query(int x)
{
int pos=hashCalc(x);
if(hashST[pos]==0)
{
hashST[pos]=x;
return false;
}
else
{
int now=hashST[pos];
while(!judge(now,x) && lengths[now][6]!=-1) now=lengths[now][6];
if(judge(now,x)) return true;
else {
lengths[now][6]=x;
return false;
}
}
}
int main()
{
bool flag=0;
memset(hashST,0,sizeof(hashST));
memset(ordered,0,sizeof(ordered));
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=0;j<6;j++) scanf("%d",&lengths[i][j]);
lengths[i][6]=-1;
}
for(int i=1;i<=n;i++)
{
if(query(i))
{
flag=1;
break;
}
}
if(!flag) printf("No two snowflakes are alike.");
else printf("Twin snowflakes found.");
while(1);
return 0;
}
|
字典树哈希？
由雪花的唯一表达序列入手，如果把这个序列插入到字典树里，岂不是变成了字典树查询+插入的无脑操作？
连哈希都不用了耶！
然而这样做有两个问题
1 字典树的节点数量比较大
插入到字典树之前，需要将表示序列变成字符数组，最长有48位，一共有10w片雪花，则最多有480w个节点。
每个节点还要维护一个bool表示一个记录，10个儿子指向’0’ ~ ‘9’字符，也就是10个int。
没算错的话是183M，当然生成的数据没这么变态，所以还没有报MLE。
2 时间开销也不小
没有两片相同雪花的情况下会有10w次查询插入操作，最多执行480w次节点访问操作。
一开始还没注意计算唯一表示序列的时间复杂度，看起来没什么，改着改着出了问题。
计算函数没写好，所用的时间可能比查询插入的时间还要多，即使重写优化了计算函数，还是没有卡过。
而且个人认为问题大概就出现在这里。
原因分析
为什么用字典树哈希过不了？（原谅我自创名词）
1 背离了哈希的初衷
哈希函数在可以较短的时间内解决了数据索引的问题，同时还将表长控制在可以接受的范围内。
将时间复杂度转移到了解决哈希冲突的处理上来。
还要注意的是空间开销和哈希冲突概率总是成反比，有时候可以从这里入手来一波时间空间互换。
如果将字典树上的节点视作雪花的哈希值，
一个是6次加法，另一个是48层的树高，在树上节点的转移、新建节点的时间开销也不可忽略。
这样一来，查询或者新建一个节点大概需要上百个基本操作时间。
虽然字典树上没有冲突，但是计算函数耗时太多。
而且方法一的冲突大概不会太多，基本可以忽略。
那么字典树的方法完败了……
2 获取唯一序列函数复杂
这个函数我写过两个版本
一是生成环的12种表示序列，然后去选其中字典序最小的。
二是从环中值最小的位置向两边扩展的到序列，开一个tmp数组取字典序最小。
即使是第二个版本，得到一片雪花的唯一表示序列至少需要几十次的基本操作时间。
得到10w片的唯一表示序列又用去了几千万次基本操作时间。
加一加差不多就过亿了吧……
虽然没卡过，还是腆着脸贴一下代码，欢迎指正。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int lengths[100010][6];
int orderMat[20][10];
struct node{
bool cnt;
int kids[10];
}Tire[4800100];
int total=0;
int strNum[50];
int lens=0;
int orderArray[7];
int tmp[7];
int hashST[65537];
void orderLengths(int x)
{
for(int i=0;i<6;i++){
if(tmp[i]>orderArray[i]) return ;
else if(tmp[i]<orderArray[i]) break;
}
for(int i=0;i<6;i++) orderArray[i]=tmp[i];
}
void getOrder(int x)
{
int minn = 0x7f7f7f7f;
memset(orderArray,0x7f7f7f7f,sizeof(orderArray));
for(int i=0;i<6;i++) minn=min(minn,lengths[x][i]);
for(int i=0;i<6;i++)
{
if(lengths[x][i]==minn)
{
int j=0;
if(lengths[x][(i+5)%6]>=lengths[x][(i+1)%6])
{
for(j=0;j+i<6;j++) tmp[j]=lengths[x][i+j];
for(int jj=0;jj<i;jj++,j++) tmp[j]=lengths[x][jj];
orderLengths(x);
}
if(lengths[x][(i+5)%6]<=lengths[x][(i+1)%6])
{
j=0;
for(j=0;i-j>=0;j++) tmp[j]=lengths[x][i-j];
for(int jj=5;jj>i;jj--,j++) tmp[j]=lengths[x][jj];
orderLengths(x);
}
}
}
for(int i=0;i<6;i++) lengths[x][i]=orderArray[i];
minn--;
}
bool query(int x)
{
lens=0;
for(int i=0;i<6;i++){
int tmp=lengths[x][i];
while(tmp){
strNum[lens++]=tmp%10;
tmp/=10;
}
}
int now=0;
bool flag=1;
for(int i=0;i<lens;i++)
{
if(Tire[now].kids[strNum[i]]==0)
{
Tire[now].kids[strNum[i]]=(++total);
Tire[total].cnt=0;
now=total;
}
else now=Tire[now].kids[strNum[i]];
}
flag=Tire[now].cnt;
Tire[now].cnt=1;
return flag;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=0;j<6;j++) scanf("%d",&lengths[i][j]);
getOrder(i);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<6;j++) printf("%d",lengths[i][j]);
printf("\n");
}
for(int i=1;i<=n;i++)
{
if(query(i))
{
printf("Twin snowflakes found.");
while(1);
return 0;
}
}
printf("No two snowflakes are alike.");
while(1);
return 0;
}
|
本文来得很草率，计算分析过程非常不严谨，源于笔者对程序运行过程不甚了解。