中国海洋大学第四届朗讯杯高级组 I Cuckoo for Hashing

时间:2023-03-09 07:35:45
中国海洋大学第四届朗讯杯高级组 I Cuckoo for Hashing

http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2719&cid=1203

题意 :意思就是哈希来的,具体大意就是说有两个哈希表,然后有这样一组数据,让你把这组数据存到这两个哈希表里,然后不能重复,先让数据往表1里存,就是对表1的长度进行取余,如果余数这个位置没有数就存上,如果有的话,就存上这个数,让原来的数再去表2里存,也是按照这个方式。就是来回踢。。。我觉得。。。。

思路:两个哈希表,一个循环找即可。。。当时做的时候把自己绕进去了。。。。

#include <stdio.h>
#include <string.h>
#include <map>
#include <iostream> using namespace std ;
int ch[];
int sh[];
int main()
{
int n1,n2,k ;
int t = ;
while(scanf("%d%d%d",&n1,&n2,&k)!=EOF)
{ memset(ch,-,sizeof(ch));
memset(sh,-,sizeof(sh)) ;
if(n1 == &&n2==&&k==) break;
int x ;
for(int i = ; i <= k ; i++)
{
scanf("%d",&x);
while()
{
int s=x%n1;
if(ch[s] == -)
{
ch[s]=x;
break;
}
else
{
int temp=ch[s];
ch[s]=x;
int tt=temp%n2;
if(sh[tt]==-)
{
sh[tt]=temp;
break;
}
else
{
x=sh[tt];
sh[tt]=temp;
}
}
}
}
printf("Case %d:\n",t);
t++;
int flag = ;
for(int i = ; i < n1 ; i++)
{
if(ch[i] != -)
{
flag = ;
break ;
}
}
if(flag)
{
printf("Table 1\n");
for(int i = ; i < n1 ; i++)
{
if(ch[i] != -)
{
printf("%d:%d\n",i,ch[i]) ;
}
}
}
flag = ;
for(int i = ; i < n2 ; i++)
{
if(sh[i] != -)
{
flag = ;
break ;
}
}
if(flag)
{
printf("Table 2\n");
for(int i = ; i < n2 ; i++)
{
if(sh[i] != -)
{
printf("%d:%d\n",i,sh[i]) ;
}
}
}
}
return ;
}

下面这个是用map做的,不厚道,直接用的二货的。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
using namespace std;
int main()
{
int n1,n2,m,c,t=;
while(scanf("%d%d%d",&n1,&n2,&m)!=EOF)
{
map<int,int>q1;
map<int,int>q2;
if(n1==&&n2==&&m==) break;
for(int i=; i<=m; i++)
{
scanf("%d",&c);
while()
{
int s=c%n1;
if(q1.find(s)==q1.end())
{
q1[s]=c;
break;
}
else
{
int cc=q1[s];
q1[s]=c;
int tt=cc%n2;
if(q2.find(tt)==q2.end())
{
q2[tt]=cc;
break;
}
else
{
c=q2[tt];
q2[tt]=cc;
}
}
}
}
printf("Case %d:\n",t);
t++;
if(!q1.empty())
{
printf("Table 1\n");
map<int,int>::const_iterator inter=q1.begin();
while(inter!=q1.end())
{
cout<<inter->first<<':';
cout<<inter->second<<endl;
inter++;
}
}
if(!q2.empty())
{
printf("Table 2\n");
map<int,int>::const_iterator inter1=q2.begin();
while(inter1!=q2.end())
{
cout<<inter1->first<<':';
cout<<inter1->second<<endl;
inter1++;
}
}
}
return ;
}