糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 3121 The SetStack Computer 哈希

可以开一个闭hash表。栈里面存放的只是hash表的下标。这样比较两个set是否一样,就只需要比较他们的下标是否一样。
同时对每个set,要保存它的孩子,一样存放的是hash表的下标。

union和intersect操作,如果是按序存放孩子的话,复杂度可以低至O(N)。
空间复杂度为O(N^2)。

#include <stdio.h>
#include 
<string.h>
#include 
<algorithm>
#include 
<cmath>

using namespace std;

#define SIZE 4096
struct slot {
    
int *arr;
    
int cnt;
    
int hash;
}
 table[SIZE];
int stack[SIZE], *sp;
int _pool[SIZE*1024], *pool;

int gethash(int *arr, int cnt)
{
    unsigned 
int h = 0x1653;
    
while (cnt--
        h 
= (h*31 + *arr++& 0x7fffffff;
    
return h;
}


int insert(int *arr, int cnt)
{
    
int h = gethash(arr, cnt);
    
int i = h%SIZE;
    
while (table[i].hash && table[i].hash != h)
        i 
= (i+1)%SIZE;
    
if (!table[i].hash) {
        memcpy(pool, arr, cnt
*sizeof(int));
        table[i].hash 
= h;
        table[i].arr 
= pool;
        table[i].cnt 
= cnt;
        pool 
+= cnt;
    }

    
return i;
}


void set_union(int *a, int ca, int *b, int cb, int *arr, int *cnt)
{
    
int i, j;

    memcpy(arr, a, ca
*sizeof(int));
    memcpy(arr 
+ ca, b, cb*sizeof(int));
    sort(arr, arr 
+ ca + cb);
    
for (i = j = 0; i < ca + cb; i++{
        
if (i && arr[i] == arr[i-1])
            
continue;
        arr[j
++= arr[i];
    }

    
*cnt = j;
}


int do_union(int a, int b)
{
    
int arr[SIZE], cnt;

    set_union(
            table[a].arr, table[a].cnt, 
            table[b].arr, table[b].cnt, 
            arr, 
&cnt
            );
    
return insert(arr, cnt);
}


int do_intersect(int a, int b)
{
    
int arr[SIZE], cnt, i, j;

    cnt 
= 0;
    
for (i = 0; i < table[a].cnt; i++{
        
for (j = 0; j < table[b].cnt; j++)
            
if (table[b].arr[j] == table[a].arr[i]) {
                arr[cnt
++= table[a].arr[i];
                
break;
            }

    }

    
return insert(arr, cnt);
}


int do_add(int a, int b)
{
    
int arr[SIZE], cnt;

    set_union(table[b].arr, table[b].cnt, 
&a, 1, arr, &cnt);
    
return insert(arr, cnt);
}


int main()
{
    
char op[128];
    
int t, i, n;

    scanf(
"%d"&t);
    
while (t--{
        pool 
= _pool;
        sp 
= stack-1;
        
for (i = 0; i < SIZE; i++)
            table[i].hash 
= 0;
        scanf(
"%d"&n);
        
while (n--{
            scanf(
"%s", op);
            
if (!strcmp(op, "PUSH")) {
                
*++sp = insert(NULL, 0);
            }
 else if (!strcmp(op, "DUP")) {
                sp[
1= *sp;
                sp
++;
            }
 else if (!strcmp(op, "UNION")) {
                sp[
-1= do_union(sp[0], sp[-1]);
                sp
--;
            }
 else if (!strcmp(op, "INTERSECT")) {
                sp[
-1= do_intersect(sp[0], sp[-1]);
                sp
--;
            }
 else if (!strcmp(op, "ADD")) {
                sp[
-1= do_add(sp[0], sp[-1]);
                sp
--;
            }

            printf(
"%d\n", table[*sp].cnt);
        }

        printf(
"***\n");
    }


    
return 0;
}

posted on 2011-02-23 14:41 糯米 阅读(706) 评论(1)  编辑 收藏 引用 所属分类: POJ

评论

# re: POJ 3121 The SetStack Computer 哈希  回复  更多评论   

请问这个题 你还记得怎么对 集合 做的hash 吗?? 搞不懂。。
2013-03-20 22:12 | OceanLight

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理