哈希水题解P4305、P1102

这两道题都是经典的哈希,通过哈希的思想来减小时空复杂度,这两道题基本都是哈希的板子,因此理解并记住即可,代码里会有注释。

P4305 AC code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define hash(a) a%p
const int p=99843373;
typedef int int_;
#define int long long 
int h[100000];
int find(int x)//查找x在哈希表中的位置
{
    int y=abs(x);//因为x有可能为负数,所以要取绝对值
    while(h[y] and h[y]!=y)
        h[y]=hash(++y);//该位置有数据但不是他
    return y;
}
void push(int x)//向哈希表中加入元素
{
    h[find(x)]=x;
}
bool check(int x)//检查哈系表中是否有该元素
{
    return h[find(x)]==x;
}
int_ main()
{
    int t;
    scanf("%lld",&t);
    for(int i=1;i<=t;i++)
    {
        int n;
        scanf("%lld",&n);
        memset(h,0,sizeof(h));
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%lld",&x);
            if(!check(x))//如果该数未被列进哈希表
            {
                printf("%d ",x);//输出
                push(x);//推入哈希表
            }
        }
        printf("\n");//换行
    }
    return 0;
}

P1102 AC code

#include<cstdio>
#include<iostream>
#include<cmath>
#define mmm 1000000
typedef int int_;
#define int long long
int num[mmm];
const int mod =1000003;
using namespace std;
struct node{
    int x, y;
}a[mmm];
int ans=0;
int hash1(int x)
{
    return x%mod;
}
int find(int x)//查找该表的位置
{
    int y=hash1(abs(x));
    while(a[y].x and a[y].x!=x)
        y=hash1(++y);
    return y;
}
int check(int x)//检查表中是否有该数
{
    return a[find(x)].y;
}
int push(int x)//推入表
{
    int y=find(x);
    a[y].y++,a[y].x=x;
    return y;
}
int_ main()
{
    int n,c;
    cin>>n>>c;
    for(int i=1;i<=n;i++)
        cin>>num[i],push(num[i]);
    for(int i=1;i<=n;i++)
        ans+=check(num[i]-c);//计算
    cout<<ans<<endl;//输出
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注