题目意思是每行给你四个数，然后再每列选一个数，四列任取一组之和等于0，求有多少组这种组合？

一开始想复杂了，以为是动态规划，后来比完才知道是二分，暴力也可以做（不知道为什么暴力时间还短一些）。

暴力的话就是先a、b组合排序，然后c、d组合排序。从ab的开头开始找，从cd的末尾开始找，这样时间会快点。

二分的话就是，排列的的时候将cd组合为-(c+d)，然后排序之后二分查找和ab相同的即可。

代码：

暴力：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 4005
int ab[MAX*MAX], cd[MAX*MAX];
int a[MAX], b[MAX], c[MAX], d[MAX];
int n, ans;
int main()
{
    while(~scanf("%d", &n)){
        for(int i=0;i<n;i++){
            scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                ab[i*n+j]=a[i]+b[j];
                cd[i*n+j]=c[i]+d[j];
            }
        }
        sort(ab, ab+n*n);
        sort(cd, cd+n*n);
        ans=0;
        int pos=n*n-1;
        for(int i=0;i<n*n;i++){
            while(ab[i]+cd[pos]>0&&pos>=0)pos--;
            if(pos<0)break;
            int t=pos;
            while(ab[i]+cd[t]==0&&t>=0){
                ans++;t--;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

代码：

二分：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 4005
int a[MAX], b[MAX], c[MAX], d[MAX];
int ab[MAX*MAX], cd[MAX*MAX];
int n, ans;
int search_num(int x){
    int l=0,r=n*n-1,mid;
    while(l<=r){
        mid=(l+r)/2;
        if(cd[mid]==x){
            int cnt=0, pos=mid;
            while(pos>=0&&cd[pos--]==x)cnt++;
            pos=mid+1;
            while(pos<n*n&&cd[pos++]==x)cnt++;
            return cnt;
        }
        else if(cd[mid]<x)l=mid+1;
        else r=mid-1;
    }
    return 0;
}
int main()
{
    while(~scanf("%d", &n)){
        for(int i=0;i<n;i++)scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                ab[i*n+j]=a[i]+b[j];
                cd[i*n+j]=-(c[i]+d[j]);
            }
        }
        sort(ab, ab+n*n);
        sort(cd, cd+n*n);
        for(int i=0;i<n*n;i++)ans+=search_num(ab[i]);
        printf("%d\n", ans);
    }
    return 0;
}