UVA12096 - The SetStack Computer(set + map映射)

题目链接

题目大意：有五个动作：

push ： 把一个空集合{}放到栈顶。

dup ： 把栈顶的集合取出来，在入栈两次。

add ： 出栈两次。把第一个集合作为一个元素放入第二个集合中，再将第二个集合入栈

union： 出栈两次，取这两个集合的并集。将结果入栈。

intersect： 出栈两次。取这两个集合的交集，将结果入栈。

每次运行动作后还须要输出眼下栈顶集合的元素个数。

解题思路：这题能够用栈和set来模拟，push就把空的集合入栈，可是在并集和交集的时候就须要判段集合是否同样，所以这里能够用map把出现过的集合手动的映射成数字。

代码：

#include <cstdio>

#include <cstring>

#include <stack>

#include <set>

#include <map>

using namespace std;

char op[15];

int n;

typedef set<int> E;

stack<E> s;

map<E, int> vis;

E tmp1, tmp2;

set<int>::iterator it;

int num;

void hash (E a) {

    if (!vis.count(a))

        vis[a] = ++num;

}

void Push () {

    tmp1.clear();

    s.push (tmp1);

}

void Dup () {

    tmp1 = s.top();

    s.push (tmp1);

}

void Add () {

    tmp2 = s.top();

    s.pop();

    tmp1 = s.top();

    s.pop();

    tmp1.insert (vis[tmp2]);

    hash(tmp1);

    s.push(tmp1);

}

void Union () {

    tmp2 = s.top();

    s.pop();

    tmp1 = s.top();

    s.pop();

    for (it = tmp1.begin(); it != tmp1.end(); it++)

        tmp2.insert (*it);

    hash (tmp2);

    s.push (tmp2);

}

void Intersect () {

    tmp2 = s.top();

    s.pop();

    tmp1 = s.top();

    s.pop();

    E tmp;

    for (it = tmp1.begin(); it != tmp1.end(); it++)

        if (tmp2.count(*it))

            tmp.insert (*it);

    hash (tmp);

    s.push(tmp);

}

void solve () {

    switch (op[0]) {

        case 'P' : Push();     break;

        case 'D' : Dup();      break;

        case 'U' : Union();    break;

        case 'I' : Intersect(); break;

        case 'A' : Add();      break;

    }

    printf ("%d\n", s.top().size());

}

void init () {

    num = 1;

    while (!s.empty()) {

        s.pop();

    }

    vis.clear();

}

int main () {

    int T;

    scanf ("%d", &T);

    while (T--) {

        scanf ("%d", &n);

        while (n--) {

            scanf ("%s", op);

            solve();

        }

        printf ("***\n");

    }

    return 0;

}