Problem DescriptionThe SUM problem can be formulated as follows: given four lists A,B,C,D of integer values, compute how many quadruplet (a,b,c,d) ∈ A×B×C×D are such that a+b+c+d = 0. In the following, we assume that all lists have the same size n.
InputThe input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The ?rst line of the input ?le contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2^28) that belong respectively to A,B,C and D.
Output Sample Input Sample Output5
题解：这个题主要是太陈了，觉得是个大水题，但是第一次见的时候不是太容易想。思想很深刻，分块，明明都是暴力枚举，但即便不加二分查找这个方法也在数量级上碾压四重for循环，感觉上有一点不可思议，想想莫队算法是不是也利用了这个思想（分块真的可以出奇迹）。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 4000 + 10; 6 7 int a[maxn], b[maxn], c[maxn], d[maxn]; 8 int sum[maxn*maxn]; 9 int n; 10 11 int main() 12 { 13 //freopen("input.txt", "r", stdin); 14 int iCase; 15 scanf("%d", &iCase); 16 while (iCase--) { 17 scanf("%d", &n); 18 for (int i = 0; i < n; i++) { 19 scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]); 20 } 21 22 int cnt = 0; 23 for (int i = 0; i < n; i++) { 24 for (int j = 0; j < n; j++) { 25 sum[cnt++] = a[i] + b[j]; 26 } 27 } 28 sort(sum, sum + cnt); 29 long long ans = 0; 30 for (int i = 0; i < n; i++) { 31 for (int j = 0; j < n; j++) { 32 ans += upper_bound(sum, sum + cnt, -c[i] - d[j]) - lower_bound(sum, sum + cnt, -c[i] - d[j]); 33 } 34 } 35 36 printf("%lld\n", ans); 37 if (iCase) printf("\n"); 38 } 39 return 0; 40 }
UVA1152-4 Values whose Sum is 0（分块）
原文：https://www.cnblogs.com/npugen/p/9611070.html