Poj 2785 4 Values whose Sum is 0 hash 哈希表

题意简单,就是找四个数的和为零.先把前两列的和算出来,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(
"%d\n",ans);
    
    
    
return 0;
}

posted on 2010-08-23 08:23 若余 阅读(482) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

统计

常用链接

留言簿

随笔档案(16)

搜索

最新随笔

最新评论

评论排行榜