题意:
A,B,C,D四组数中各取一个数,使这四个数相加为0,问有多少组取法?
分析:
四个数列有n4种取法,规模较大,但是可以将他们分成AB,CD两组,分别枚举,最后再合并。
代码:
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 4005, maxm = 16000025;
int cd[maxm], a[maxn], b[maxn],c[maxn],d[maxn];
int main (void)
{int n;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++){cd[i*n+j] = c[i]+d[j];}}ll res = 0;sort(cd, cd+n*n);for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){int tmp = -(a[i] + b[j]);res += upper_bound(cd, cd + n * n, tmp) - lower_bound(cd, cd + n * n, tmp);}}printf("%I64d\n",res);
}