POJ 2785-4 Values whose Sum is 0（a+b+c+d=0-折半枚举）

雨点打透心脏的1/2处 2022-09-21 05:33 95阅读 0赞

4 Values whose Sum is 0

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;15000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;228000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;19331</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;5783</td> 
  </tr> 
  <tr> 
   <td colspan="3" align="center" style="color:rgb(14,173,0)"><strong>Case Time Limit:</strong>&nbsp;5000MS</td> 
  </tr> 
 </tbody> 
</table>

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 28 ) 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][]

## 题目意思： ##

有abcd四个数组，各抽取一个数使得四个数之和为0；问共有多少种取法。

## 解题思路： ##

先取cd中的。再用折半枚举算出所需要的ab中的和的值。

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<malloc.h>
    #include<algorithm>
    #define MAXN 4005
    #define inf 0x3f3f3f3f
    using namespace std;
    int n;
    int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
    int cd[MAXN*MAXN];//c,d中数字的组合方法
    
    void solve()
    {
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                cd[i*n+j]=c[i]+d[j];//枚举c,d数字之和的所有情况
        sort(cd,cd+n*n);
        long long res=0;
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
            {
                int addcd=-(a[i]+b[j]);//需要加上的数
                //参数：数组，数组长度，目标值
                //upper_bound返回第一个出现的位置
                //lower_bound返回最后一个的后面一个出现的位置
                //都没有就返回应该出现的位置使得sort依然有序
                res+=upper_bound(cd,cd+n*n,addcd)-lower_bound(cd,cd+n*n,addcd);
            }
        cout<<res<<endl;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>n;
        for(int i=0; i<n; ++i)
            cin>>a[i]>>b[i]>>c[i]>>d[i];
        solve();
        return 0;
    }
    /*
    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
    */

[Southwestern Europe 2005]: http://poj.org/searchproblem?field=source&key=Southwestern+Europe+2005