4 Values whose Sum is 0
The 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 x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
Input
The first line of the input file 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 228 ) that belong respectively to A, B, C and D .
Output
For each input file, your program has to write the number quadruplets whose sum is zero.
Sample 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
Sample Output
5
Hint
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).
Source
题目类型：数字型Hash查找
算法分析：直接使用暴力枚举是一定会TLE的，这里使用的Hash可以将时间复杂度降到O(2*N^2)，将输入的前两列数字枚举和并插入到Hash表中，然后对于输入的后两列数字枚举和并查询和的相反数是否在表中，如果在则累加sum，最后输出sum即可
|
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const int MOD = 10000007; const int maxn = 4000 + 66; struct Node { int v, next, num; }; Node edge[3999972]; int head[3999972]; int Hash (int val) { return (val + 3899971) % 3999971; } int tot; void add_edge (int val) { int key = Hash (val); for (int i = head[key]; i != -1; i = edge[i].next) { if (edge[i].v == val) { edge[i].num++; return ; } } edge[tot].v = val; edge[tot].num = 1; edge[tot].next = head[key]; head[key] = tot++; } int Find (int val) { int key = Hash (val); for (int i = head[key]; i != -1; i = edge[i].next) { if (edge[i].v == val) { return edge[i].num; } } return 0; } int a[maxn],b[maxn],c[maxn],d[maxn]; int main () { // freopen ("aaa.txt", "r", stdin); int n, i, j; while (scanf("%d", &n) != EOF) { tot = 0; memset (head,-1,sizeof(head)); for (i = 1; i <= n; i++) scanf ("%d%d%d%d",&a[i], &b[i], &c[i], &d[i]); for (i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { add_edge (a[i] + b[j]); } } long long ans = 0; for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { ans += Find (-c[i] - d[j]); } } printf("%lld\n",ans); } return 0; } |
- « 上一篇：poj2777
- poj2823：下一篇 »