UVA12096(The SetStack Computer )

题目描述：UVA12096传送门
题目大意：
PUSH：向栈中放一个空集合。
DUP：复制栈顶集合。
UNION：取栈顶的两个集合，取并集后放回。
INTERSECT：取栈顶的两个集合，取交集后放回。
ADD：取栈顶两个集合，将第一个集合作为元素放到第二个集合中，并将第二个集合放回栈。
每次操作后输出栈定集合中元素的个数。
思路：参照紫书（刘汝佳的算法竞赛入门经典）思路，此题为STL模板题，主要是熟悉STL内set，map，stack数据结构的使用。这题难点主要是对题意的理解与对集合的具体化，不理解题意的小伙伴最好先按照样例推一遍不然就像我没看样例傻傻看题看半天（暴露智商了。。），理解完题意再来看题，解题思路就是利用map将集合映射成一个具体的ID，例如{} = 0，{{}} = 1，{{{}}} = 3,这样就把抽象的集合转化成ID，再将不同的ID取一次集合，方便调用。这题还利用了set_union()和set_intersection()两个STL求并集与交集的函数。
附上代码:

#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <iterator>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
using namespace std;

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()
{
    //freopen("text.txt","r",stdin);
    int t,n;
    cin>>t;
    while(t--){
        stack<int>s;
        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));          //set_union求两个set容器的交集
                if(op[0]=='I') set_intersection (ALL(x1),ALL(x2),INS(x));   //set_intersection求两个set容器的并集
                if(op[0]=='A') {
                    x = x2;
                    x.insert(ID(x1));
                }
                s.push(ID(x));
            }
            cout<<Setcache[s.top()].size()<<endl;
        }
        cout<<"***"<<endl;
    }
    return 0;
}

最后附上set_union()和set_intersection()的代码演示实例,辅助理解一下

#include <algorithm>
#include <iterator>
#include <string>
#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> x1 = {1,2,3,4};
    set<int> x2 = {3,4,5,6};
    set<int> result;
    set_union(x1.begin(),x1.end(),
              x2.begin(),x2.end(),
              inserter(result,result.begin()));

    for(set<int>::iterator it = result.begin();it!=result.end();it++)
        cout<<*it<<" ";
    cout<<endl;
    /*
    输出结果应为:1 2 3 4 5 6
    */

    result.clear();

    set_intersection(x1.begin(),x1.end(),
                     x2.begin(),x2.end(),
                     inserter(result,result.begin()));

    for(set<int>::iterator it = result.begin();it!=result.end();it++)
        cout<<*it<<" ";
    /*
    输出结果应为：3 4
    */
    return 0;
}