二分搜索+upper_bound,lower_bound

原文链接：http://www.spoj.com/problems/SUMFOUR/

题意：有四个数列A，B，C，D。 每个数列n个数，在每个数列中都任意取出一个数。要求这四个数相加等于0，问这样的四个数组合共有多少组？

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
Output:
5      

解法：hash或者二分搜索

二分答案：

#include <bits/stdc++.h>
using namespace std;
const int maxn=2600;
int n,a[maxn],b[maxn],c[maxn],d[maxn],cd[maxn*maxn];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;++j)
    {
        cd[i*n+j]=c[i]+d[j];
    }
    sort(cd,cd+n*n);
    int res=0;
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j)
        {
            int k=-(a[i]+b[j]);
            res+=upper_bound(cd,cd+n*n,k)-lower_bound(cd,cd+n*n,k);
        }

    }
    cout<<res<<endl;

    return 0;
}
           

题意：有四个数列A，B，C，D。 每个数列n个数，在每个数列中都任意取出一个数。要求这四个数相加等于0，问这样的四个数组合共有多少组？