• 如果喜欢本站,您可以按CTRL+D收藏本站,方便下次访问。

  • 欢迎来自五湖四海的朋友,期待为您分享有价值的资源 :oops:

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

POJ解题 第四度 10年前 (2010-08-23) 31次浏览 0个评论 扫描二维码

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;
}

本网站采用BY-NC-SA 4.0协议进行授权 | 转载请注明原文链接:https://www.disidu.com/post/1012.html
如果觉得本文对您有帮助或者您心情好~可以微信打赏支持一下本站:↓↓↓
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址