The SetStack Computer UVA - 1209

https://vjudge.net/problem/UVA-12096

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

using namespace std;

#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x, x.begin())

typedef set<int> Set;
map<Set, int> IDcache;  // 把集合映射成ID
vector<Set> Setcache;   // 根据ID取集合

// 查找给定集合x的ID。如果找不到，分配一个新的ID
int ID(Set x) {
    if (IDcache.count(x))
        return IDcache[x];
    Setcache.push_back(x);  // 添加新集合
    return IDcache[x] = Setcache.size() - 1;
}

int main() {
    stack<int> s;
    int n, kase;
    cin >> kase;
    for (int j = 0; j < kase; ++j) {

        cin >> n;
        for (int i = 0; i < n; ++i) {
            string op;
            cin >> op;
            if (op[0] == 'P')
                s.push(ID(Set()));
            else if (op[0] == 'D')
                s.push(s.top());
            else {
                Set x1 = Setcache[s.top()];
                s.pop();
                Set x2 = Setcache[s.top()];
                s.pop();
                Set x;
                if (op[0] == 'U')
                    set_union(ALL(x1), ALL(x2), INS(x));
                if (op[0] == 'I')
                    set_intersection(ALL(x1), ALL(x2), INS(x));
                if (op[0] == 'A') {
                    x = x2;
                    x.insert(ID(x1));
                }
                s.push(ID(x));
            }
            cout << Setcache[s.top()].size() << endl;
        }
        cout << "***" << endl;
    }

    return 0;
}

本题的集合不是简单的整数集合或字符串集合，而是集合的集合。为了方便起见，为每个不同的集合分配一个唯一的ID。

set_union()和set_intersection分别是取并集和交集是algorithm头文件中的函数。

• C++inserter插入迭代器

• set_union的几个例子