POJ 2785 -- 4 Values whose Sum is 0

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 .

http://blog.csdn.net/lp_opai/article/details/38231259?utm_source=tuicool

1. int ab[4010*4010],cd[4010*4010];  
2. int main()  
3. {  
4.       
5.     int n,i,k,j,count,a[4010],b[4010],c[4010],d[4010];  
6.     while(~scanf("%d",&n))  
7.     {  
8.           
9.         for(i=0;i<n;i++)  
10.             scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);  
11.         int cot1=0;  
12.         int cot2=0;  
13.         for(i=0;i<n;i++)  
14.         {  
15.             for(j=0;j<n;j++)  
16.             {  
17.                 ab[cot1++]=a[i]+b[j];  
18.                 cd[cot2++]=-(c[i]+d[j]);  
19.             }  
20.         }  
21.         sort(cd,cd+cot2);  
22.         count=0;  
23.         for(i=0;i<cot1;i++)  
24.         {     
25.             int left=0;  
26.             int right=n*n-1;  
27.             while(left<=right)  
28.             {  
29.                 int mid=(left+right)/2;  
30.                 if(ab[i]==cd[mid])  
31.                 {  
32.                     count++;  
33.                     for(k=mid+1;k<cot2;k++)  
34.                     {  
35.                         if(ab[i]==cd[k])  
36.                             count++;  
37.                         else  
38.                             break;  
39.                     }  
40.                     for(k=mid-1;k>=0;k--)  
41.                     {  
42.                         if(ab[i]==cd[k])  
43.                             count++;  
44.                         else  
45.                             break;  
46.                     }  
47.                     break;  
48.                 }  
49.                 else if(ab[i]<cd[mid])  
50.                      right=mid-1;  
51.                 else  
52.                      left=mid+1;  
53.   
54.             }  
55.         }  
56.         printf("%d\n",count);  
57.     }  
58.     return 0;  
59. }  

1. int erfen(int left,int right,int k)  
2. {  
3.     int i;  
4.     while(left<=right)  
5.     {  
6.       int mid=(left+right)/2;  
7.       int num=0;  
8.       if(num2[mid]==k)  
9.        {  
10.         num=1;  
11.          for(i=mid-1;i>=0&&num2[i]==k;i--)  num++;  
12.          for(i=mid+1;i<n*n&&num2[i]==k;i++)  num++;  
13.          return num;  
14.        }  
15.       else if(num2[mid]>k)  
16.         right=mid-1;  
17.        else left=mid+1;  
18.     }  
19.     return 0;  
20.   
21. }  
22. int main()  
23. {  
24.     int i,j;  
25.     while(scanf("%d",&n)!=EOF)  
26.     {  
27.         int num=0;  
28.         c=0;  
29.         for(i=0;i<n;i++)  
30.         {  
31.             scanf("%d %d %d %d",&a[0][i],&a[1][i],&a[2][i],&a[3][i]);  
32.         }  
33.         for(i=0;i<n;i++)  
34.             for(j=0;j<n;j++)  
35.             {  
36.                  num1[c]=a[2][i]+a[3][j];  
37.                  num2[c++]=-(a[0][i]+a[1][j]);  
38.             }  
39.             sort(num2,num2+c);  
40.         for(i=0;i<c;i++)  
41.             {  
42.                 num+=erfen(0,n*n-1,num1[i]);  
43.             }  
44.         printf("%d\n",num);  
45.     }  
46.     return 0;  
47. }  

http://blog.csdn.net/hnust_xiehonghao/article/details/9329613
hash  做法 - we can use hashmap directly in java

1. int n,a[4040],b[4040],c[4040],d[4040],ans;  
2. int hash[size],sum[size];  
3. void Insert(int num)  
4. {  
5.     int tmp=num;  
6.     num=(num+MAX)%size;  
7.     while(hash[num]!=MAX && hash[num]!=tmp)  
8.         num=(num+key)%size;  
9.     hash[num]=tmp;  
10.     sum[num]++;  
11. }  
12. int Find(int num)  
13. {  
14.     int tmp=num;  
15.     num=(num+MAX)%size;  
16.     while(hash[num]!=MAX && hash[num]!=tmp)  
17.         num=(num+key)%size;  
18.     if(hash[num]==MAX)  
19.         return 0;  
20.     else  
21.         return sum[num];  
22. }  
23. int main()  
24. {  
25.     int i,j;  
26.     scanf("%d",&n);  
27.     for(i=0;i<n;i++)  
28.         scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);  
29.     for(i=0;i<size;i++)  
30.         hash[i]=MAX;  
31.     for(i=0;i<n;i++)  
32.         for(j=0;j<n;j++)  
33.             Insert(a[i]+b[j]);  
34.     for(i=0;i<n;i++)  
35.         for(j=0;j<n;j++)  
36.             ans+=Find(-(c[i]+d[j]));  
37.     printf("%d\n",ans);  
38. }

Read full article from 2785 -- 4 Values whose Sum is 0