HDU-4334 Trouble 哈希表Or有序表查找-白红宇

HDU-4334 Trouble 哈希表Or有序表查找

阅读量：6832 次

发布时间：2019-06-26

本文共 3408 字，大约阅读时间需要 11 分钟。

这题就是一个数据量大点的a+b+c+d+e = 0的判定，可以用哈希表来做，也可以用来个有序表来寻找解。时间复杂度前者接近O(n^3)，后者则为O(N^3).

代码如下：

哈希表：

#include
     
      #include
      #define MOD 1000003LLusing namespace std;typedef long long LL;const int N = 205;LL a[6][N];int head[1000005], idx;struct Node{    LL v;    int next;    }e[40005];void add(LL key){    int rkey, flag = 0;    if (key > 0) {        rkey = key % MOD;    }    else {        rkey = (-key) % MOD;    }    for (int i = head[rkey]; i != -1; i = e[i].next) {        if (e[i].v == key) {            flag  = 1;            break;            }    }        if (!flag) {        ++idx;        e[idx].v = key;        e[idx].next = head[rkey];        head[rkey] = idx;    }}bool find(LL x){    int rkey;    if (x > 0) {        rkey = x % MOD;    }    else {        rkey = (-x) % MOD;    }    for (int i = head[rkey]; i != -1; i = e[i].next) {        if (e[i].v == x) {            return true;            }        }        return false;}int main(){    int t, n, flag;    LL key;    scanf("%d",&t);    while(t-- && scanf("%d",&n)){        idx = -1;        flag = 0;        memset(head, 0xff, sizeof (head));        for(int i = 1; i <= 5; i++){            for(int j = 1; j <= n; j++){                scanf("%I64d",&a[i][j]);                }        }         for(int i = 1; i <= n; i++){            for(int j = 1; j <= n; j++){                key = a[1][i] + a[2][j];                add(key);            }         }        for(int i = 1; i <= n && !flag; i++){             for(int j = 1; j <= n && !flag; j++){                for(int k = 1; k <= n; k++){                    if (find(-(a[3][i]+a[4][j]+a[5][k]))) {                        flag = 1;                        break;                    }                }                }        }        puts( flag? "Yes" : "No");    }    return 0;}

有序表查找：将a+b的所有组合放到一个表中，c+d放到另一个表中，都排序去重，再定义两个指针，分别指向第一个表的首，第二个表的尾。再向两边走。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long int Int64;int N, fidx, sidx;Int64 seq[5][205];Int64 flist[400005], slist[400005];int main(){    int T, ca = 0, flag, p1, p2;    Int64 sum, obj;    scanf("%d", &T);    while (T--) {        fidx = sidx = flag = 0;        scanf("%d", &N);        for (int i = 0; i < 5; ++i) {            for (int j = 1; j <= N; ++j) {                scanf("%I64d", &seq[i][j]);                    }        }        for (int i = 1; i <= N; ++i) {            for (int j = 1; j <= N; ++j) {                flist[++fidx] = seq[0][i] + seq[1][j];                slist[++sidx] = seq[2][i] + seq[3][j];            }        }        sort(flist+1, flist+1+fidx);        sort(slist+1, slist+1+sidx);        fidx = unique(flist+1, flist+1+fidx) - (flist+1);        sidx = unique(slist+1, slist+1+sidx) - (slist+1);        for (int i = 1; i <= N && !flag; ++i) {            p1 = 1, p2 = sidx;            obj = -seq[4][i];            while (p1 <= fidx && p2 >= 1) {                sum = flist[p1] + slist[p2];                if (obj > sum) {                    ++p1;                }                    else if (obj < sum) {                    --p2;                }                else {                    flag = 1;                    break;                }            }        }        printf(flag ? "Yes\n" : "No\n");    }    return 0;    }

转载于:https://www.cnblogs.com/Lyush/archive/2012/08/02/2620652.html

你可能感兴趣的文章