SPOJ SETSTACK 题解

题意

有一个装着集合的栈，需要你实现以下操作：

• PUSH. 将把空集 \(\{\}\) 推到堆栈上。
• DUP. 将复制最顶层的集合（弹出堆栈，然后将该集合推入堆栈两次）。
• UNION. 会弹出堆栈两次，然后将两个集合的联合值推入堆栈。
• INTERSECT. 会弹出堆栈两次，然后将两个集合的交集推到堆栈上。
• ADD. 会弹出堆栈两次，将第一个集合加入第二个集合，然后将得到的集合推到堆栈上。

对于每一次操作，输出操作后栈顶集合的大小，集合的大小为集合中元素的个数，嵌套的集合算一个，具体举个例子：

• \(s = \{\{\{\{\{\}\}\}\},\, \{\{\}\}\}\)，\(|s| = 2\)。

思路

其实很简单，依题意模拟即可。

PUSH 和 DUP 比较简单，不讲。我们下面开始考虑如何进行其他三个操作：

• ADD. 对于这个操作，我们将第一个集合取出来，然后用一个哈希表保存集合的唯一编号，将编号加入第二个集合即可。
• INTERSECT. 注意不是 INTERSECTION ！！！！！我因为这个交了整整一页，在这里对洛谷和 SPOJ 表示诚挚的歉意。废话不多说，我们考虑如何求这两个集合的交集。观察到 algorithm 库中有一个叫做 set_intersection 的函数，看起来可以求交集。的确可以，假设我们有三个集合 \(s_1,\,s_2,\,s_3\)，我们要求 \(s_1 \cap s_2\) 的代码就是 set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(s3, s3.begin())); 很简单，对吧！
• UNION. 再次观察到 algorithm 库中还有一个叫做 set_union 的函数，显然可以求并集。用法如下：set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(s3, s3.begin()));

对于每一次操作，很容易发现其实答案就是栈顶元素的 size，因为每一次有新的集合出现都会被压缩成一个数字，不会产生嵌套被多次统计的情况。

简单实现即可，注意千万不要打错 INTERSECT！！！！！！

代码

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>

#define int long long

using namespace std;

int t, n, cnt;
string s;
set<int> emp;
map<set<int>, int> mp;
stack<set<int>> stk;

void sign_up(set<int> st) {
    if (!mp.count(st)) {
        mp[st] = ++cnt;
    }
}

signed main() {
    cin >> t;
    while (t--) {
        cin >> n;
        while (n--) {
            cin >> s;
            if (s == "PUSH") {
                sign_up(emp);
                stk.push(emp);
            } else if (s == "DUP") {
                set<int> s1 = stk.top();
                stk.push(s1);
            } else if (s == "UNION") {
                set<int> s1, s2, s3;
                s1 = stk.top();
                stk.pop();
                s2 = stk.top();
                stk.pop();
                set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(s3, s3.begin()));
                sign_up(s3);
                stk.push(s3);
            } else if (s == "INTERSECT") {
                set<int> s1, s2, s3;
                s1 = stk.top();
                stk.pop();
                s2 = stk.top();
                stk.pop();
                set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(s3, s3.begin()));
                sign_up(s3);
                stk.push(s3);
            } else if (s == "ADD") {
                set<int> s1, s2;
                s1 = stk.top();
                stk.pop();
                s2 = stk.top();
                stk.pop();
                s2.insert(mp[s1]);
                sign_up(s2);
                stk.push(s2);
            }
            cout << stk.top().size() << endl;
        }
        cout << "***\n";
    }
}