hash例题
oj13351
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#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int step=7;
const int modprime=2323237;
int hash[modprime+5];
int a[100100],b[100100],an,bn;
int tong=0;//记录相同元素个数
void init()
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
scanf("%d",&an);
for(int i=1;i<=an;i++)
scanf("%d",&a[i]);
scanf("%d",&bn);
for(int i=1;i<=bn;i++)
scanf("%d",&b[i]);
}
int find(int k)//查找k元素
{
int temp=k%modprime;
while(hash[temp]!=k&&hash[temp]!=0)
{
temp+=step;
if(temp>=modprime)
temp-=modprime;
}
return temp;
}
void insert(int k)//插入hash表
{
int now=find(k);
hash[now]=k;
}
void check(int k)//在hash中查找元素
{
int now=find(k);
if(hash[now]==k)
tong++;
}
void work()
{
for(int i=1;i<=an;i++)
insert(a[i]);
for(int i=1;i<=bn;i++)
check(b[i]);
}
int main()
{
init();
work();
if(an==bn&&tong==an)
{
puts("A equals B");
return 0;
}
if(an<bn&&tong==an)
{
puts("A is a proper subset of B");
return 0;
}
if(an>bn&&tong==bn)
{
puts("B is a proper subset of A");
return 0;
}
if(tong==0)
puts("A and B are disjoint");
else
puts("I'm confused!");
return 0;
}
//hash hash Murs
hash有几个要素:
先是要制作获取hash地址的find函数
在一个表中insert进去然后查询
以拉链式进行最后比较相同元素数并进行特判其实这种思想在之前的一个problem中就有体现，不记得题号了但是是以char所对应的int值来做下标查询.