学步园

题目链接：uva 12096 - The SetStack Computer

题目大意：一个栈，有5种操作；

• PUSH：向栈中放一个空集合。
• DUP：复制栈顶集合。
• UNION：取栈顶的两个集合，取并集后放回。
• INTERSECT：取栈顶的两个集合，取交集后放回。
• ADD：取栈顶两个集合，将第一个集合作为元素放到第二个集合中，并将第二个集合放回栈。

每次操作后输出栈定集合中元素的个数。

解题思路：将所有集合映射成一个值，用map记录，然后模拟操作即可。

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <stack>
#include <algorithm>

using namespace std;
typedef set<int> sint;
typedef set<int>::iterator iter;

int hn;
stack<sint> stak;
map<sint, int> g;

void hashadd (sint u) {
    if (g.count(u))
        return;
    g[u] = hn++;
}

void putsize () {
    if (stak.empty())
        return;
    printf("%d\n", (int)stak.top().size());
}

void sf_push () {
    sint u;
    hashadd(u);
    stak.push(u);
}

void sf_dup () {
    sint u = stak.top();
    stak.push(u);
}

void sf_union () {
    sint f = stak.top();
    stak.pop();
    sint u = stak.top();
    stak.pop();

    for (iter i = f.begin(); i != f.end(); i++)
        u.insert(*i);
    hashadd(u);
    stak.push(u);
}

void sf_inct () {
    sint u;
    sint f = stak.top();
    stak.pop();
    sint s = stak.top();
    stak.pop();

    for (iter i = f.begin(); i != f.end(); i++) {
        if (s.count(*i))
            u.insert(*i);
    }

    hashadd(u);
    stak.push(u);
}

void sf_add () {
    sint f = stak.top();
    stak.pop();
    sint s = stak.top();
    stak.pop();

    s.insert(g[f]);
    hashadd(s);
    stak.push(s);
}

void solve () {
    char order[10];
    scanf("%s", order);
    switch (order[0]) {
        case 'P':
            sf_push();
            break;
        case 'D':
            sf_dup();
            break;
        case 'U':
            sf_union();
            break;
        case 'I':
            sf_inct();
            break;
        case 'A':
            sf_add();
            break;
    }
    putsize();
}

int main () {
    int cas, n;
    scanf("%d", &cas);

    while (cas--) {
        hn = 0;
        g.clear();
        while (!stak.empty())
            stak.pop();

        scanf("%d", &n);
        while (n--)
            solve();
        printf("***\n");
    }
    return 0;
}