# Uva1152 4题目解答

2017-02-04

Uva1152 4题目解答：这道题若是我们直接枚举，时间复杂度达到O(n^4)显然不可行。因此我们可以考虑折半枚举(中途相遇法)，即：每次先用hash表记录前两个集合中ai+bj的和。

Uva1152 4题目解答：这道题若是我们直接枚举，时间复杂度达到O(n^4)显然不可行。因此我们可以考虑折半枚举(中途相遇法)，即：每次先用hash表记录前两个集合中ai+bj的和，然后用hash表判断后两个集合中是否存在ck+dj=-ai-bj

```#include
#include
#include
using namespace std;

const int Inf = 2147483647;
const int maxn = 4005, maxl = 100987, maxs = 4001 * 4001;
vector  Hash[maxl];
int s[5][maxn], n, t, ans;

{
char c;
do {
c = getchar();
}while(c < &#39;0&#39; || c > &#39;9&#39;);
int sum = 0;
do {
sum = sum * 10 + c - 48;
c = getchar();
}while(c >= &#39;0&#39; && c <= &#39;9&#39;);
return sum;
}

inline int abs(int a)
{
if(a > 0) return a;
return -a;
}

inline void push(int x)
{
Hash[abs(x) % maxl].push_back(x);
}

inline int search(int x)
{
int i, k = abs(x) % maxl;
int sz = Hash[k].size(), sum = 0;
for(i = 0; i < sz; i++)
if(Hash[k][i] == x) sum++;
return sum;
}

int main()
{
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
register int i, j;
scanf("%d", &t);
for(int k = 1; k <= t; k++) {
for(i = 0; i < maxl; i++)  //记得将hash表清0
Hash[i].clear();
scanf("%d", &n);
for(j = 1; j <= n; j++)
for(i = 1; i <= 4; i++)
scanf("%d", &s[i][j]);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
push(s[1][i] + s[2][j]);
ans = 0;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
ans += search(-s[3][i] - s[4][j]);
printf("%d\n", ans);
if(k < t) printf("\n");
}
return 0;
}
```