首页 > 程序开发 > 综合编程 > 其他综合 >

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;

inline int read()
{
    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;
}
相关文章
最新文章
热点推荐