POJ 2785-4 Values whose Sum is 0 hash 哈希表

file

题意简单,就是找四个数的和为零.先把前两列的和算出来,O(n^2),存到hash表中,再把后两列的两两和算出来,在hash表中找相反数.用线性探测法就可以解决该问题了.

/*Source CodeProblem: 2785        User: y09shendazhi
Memory: 160132K        Time: 2610MS
Language: G++        Result: Accepted

Source Code*/
#include <iostream>
#include<stdio.h>
using namespace std;
const int size=20345677;
int hash[size];
int sum[size];
const int key=1777;
const int MAX=1000000000;

void Insert(int num)
{
    int temp=num;
    num=(num+MAX)%size;
    while(hash[num]!=MAX && hash[num]!=temp)
        num=(key+num)%size;
    hash[num]=temp;
    sum[num]++;

}
int Find(int num)
{
    int temp=num;
    num=(num+MAX)%size;
    while(hash[num]!=MAX && hash[num]!=temp)
        num=(num+key)%size;
    if(hash[num]==MAX)
        return 0;
    else
        return sum[num];
}

int main()
{
    int n;
    int i,j;
    int a[4005],b[4005],c[4005],d[4005];

    scanf(“%d“,&n);
    int ans=0;
    for(i=0;i<n;i++)
    {
        scanf(“%d%d%d%d“,&a[i],&b[i],&c[i],&d[i]);
    }
    for(i=0;i<size;i++)
    {
        hash[i]=MAX;
    }
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        Insert(a[i]+b[j]);
    }
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        ans+=Find(-(c[i]+d[j]));
    }
    printf(“%dn“,ans);

    return 0;
}