poj 2785 4 Values whose Sum is 0(hash) - c++编程基础

4 Values whose Sum is 0

Time Limit: 15000MS		Memory Limit: 228000K
Total Submissions: 14140		Accepted: 4002
Case Time Limit: 5000MS

Description

The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .

Input

The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2²⁸ ) that belong respectively to A, B, C and D .

Output

For each input file, your program has to write the number quadruplets whose sum is zero.

Sample Input

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

Sample Output

Hint

Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

Source

Southwestern Europe 2005

题意：

给你四列数。每列里找一个数使得他们的和为0.问一共有多少这样的数。

思路：

把前两列的数任意组合的和hash。在任意组合后两列。然后去查hash表看能否使值为0.

详细见代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
             //#pragma comment(linker,"/STACK:1024000000,1024000000") using namespace std; const int INF=0x3f3f3f3f; const double eps=1e-8; const double PI=acos(-1.0); const int maxn=4010; const int up=536870912; const int mod=13000007; const int sz=maxn*maxn; typedef __int64 ll; int maze[5][maxn]; int h[sz],f[sz]; void Insert(int x) { int key=(x+up)%mod; while(f[key]&&h[key]!=x) key=(key+1)%sz; if(!f[key]) h[key]=x; f[key]++; } int getf(int x) { int key=(x+up)%mod; while(f[key]&&h[key]!=x) key=(key+1)%sz; return f[key]; } int main() { int n,i,j; ll ans; while(~scanf("%d",&n)) { memset(f,0,sizeof f); for(j=0;j