Steven_MengのBlog

传送门

考虑把$A+B+C+D=0$转换成$-A-B=C+D$,于是预处理出$C+D$的数组,sort一遍以后二分查找即可。

时间复杂度$O(n^2\log (n^2))$(反正不会爆就是了)

我以前写的代码,码风可能有点清奇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int A[4005], B[4005], C[4005], D[4005];
int SumCD[4005 * 4005];
int main()
{
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++)
{
SumCD[i + j * n] = C[i] + D[j];
}
}
sort(SumCD, SumCD + n * n);
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int find = A[i] + B[j];
ans += upper_bound(SumCD, SumCD + n * n, -find) - lower_bound(SumCD, SumCD + n * n, -find);
}
}
printf("%d\n", ans);
}

 评论