poj 2785 4 Values whose Sum is 0（折半枚举（双向搜索））

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 =  . 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 ). We then have n lines containing four integer values (with absolute value as large as  ) 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

-   -

- -

-  -

-  - -

 - -

- - -

Sample Output

Hint

Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-, -, , ), (, , -, -), (-, , , -),(-, , -, ), (-, -, , ).

AC代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <set>

 using namespace std;

 #define ll long long

 #define N 4006

 int n;

 int mp[N][N];

 int A[N],B[N],C[N],D[N];

 int CD[N*N];

 void solve(){

    for(int i=;i<n;i++){

        for(int j=;j<n;j++){

           CD[i*n+j]=C[i]+D[j];

        }

    }

    sort(CD,CD+n*n);

    ll ans=;

    for(int i=;i<n;i++){

        for(int j=;j<n;j++){

           int cd = -(A[i]+B[j]);

           ans+=upper_bound(CD,CD+n*n,cd)-lower_bound(CD,CD+n*n,cd);

        }

    }

    printf("%I64d\n",ans);

 }

 int main()

 {

     while(scanf("%d",&n)==){

        for(int i=;i<n;i++){

           for(int j=;j<;j++){

              scanf("%d",&mp[i][j]);

           }

        }

        for(int i=;i<n;i++){

           A[i] = mp[i][];

           B[i] = mp[i][];

           C[i] = mp[i][];

           D[i] = mp[i][];

        }

        solve();

     }

     return ;

 }

巴特西

poj 2785 4 Values whose Sum is 0（折半枚举（双向搜索））

最新文章

热门文章