POJ 2785 4 Values whose Sum is 0

传送门：http://poj.org/problem?id=2785

解题思路：

从这四个数列中选择的话总有n的4次方中情况，所以全部判断一遍不可行。不过将他们对半分成AB和CD再考虑的话就可以解决了。从两个数列中选择的话只有n的2次方中组合。所以可以枚举。从A，B中取出a，b后，为了使总和为0则需要从C，D中取出a+b=-（c+d）；先将a和b数组的和存在一个数组ab里面，再将c和d相加的相反数-（c+d）在ab数组里面查找，用的是二分查找。

实现代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN=4005;

int a[MAXN][4];
int b[MAXN*MAXN];

void solve(int n){
    memset(b,0,sizeof(b));

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            b[i*n+j]=a[i][0]+a[j][1];
    sort(b,b+(n*n));

    int ans=0;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++){
        int tmp=-(a[i][2]+a[j][3]);
        ans+=upper_bound(b,b+(n*n),tmp)-lower_bound(b,b+(n*n),tmp);
    }
    printf("%d
",ans);

}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<4;j++)
            scanf("%d",&a[i][j]);
    solve(n);
}