|
可以开一个闭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; }
|