题目： 有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈，并且支持以下操作： *PUSH：空集“{ }“入栈 *DUP：把当前栈顶元素复制一份后再入栈 *UNION：出栈两个集合，然后把二者的并集入栈。 *INTERSECT：出栈两个集合，然后把二者的交集入栈。 *ADD：出栈两个集合，然后把先出栈的集合加入到后出栈的集合中，把结果入栈。 每次操作之后，输出栈顶集合的大小（即元素个数）。例如：栈顶元素是A={ { }，{{ }} }，下一个元素是B={ { }，{{{ }}} },则： UNION操作得到：{ { }，{{ }}，{{{ }}} }，输出3. INTERSECT操作得到：{ { } },输出1. ADD操作得到：{{ }, {{{ }}}, {{ },{{ }}} }.，输出3
分析 本题的集合并非简单的整数或字符串集合，而是集合的集合。很难直接表示，所以为方便起见，为每个不同的集合分配一个唯一的ID ，则每个集合表示为所包含元素（集合）的ID集合。这样就可以用STL中的set<int>来表示，而整个栈则是一个stack<int>。
在进行操作时，使用map将每种集合与对应ID相关联，既可完成查找ID，也可判定是否出现新集合。使用vector作为存储每种集合的cache，当map中没有相应的ID时，向vector加入一个set<int>元素，并将下标作为ID进行唯一标识。使用vector将Set存储：可以用ID查询到对应的set。这样通过map和vector实现set到ID的双射。最后 ，输出栈顶集合的大小（元素个数）。AC代码如下：
#include<iostream> #include<cstdio> #include<algorithm> //set_union函数定义在其中 #include<set> #include<map> #include<vector> #include<stack> #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) using namespace std; typedef set<int> Set; //每个集合表示为所包含元素的ID集合 map<Set,int> IDcache; //把集合映射成ID（用map将每种集合与对应的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; //将ID值加入map，同时返回新分配的ID值。 } int main(){ stack<int> s; int n,t; string op; scanf("%d",&t); while(t--){ cin>>n; for(int i=0;i<n;i++){ 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; } printf("***\n"); } return 0; }解释说明：
对任意集合s(类型是上面定义的Set），IDcache[s]就是其ID，而Setcache[ IDcache[s] ]就是其s本身。ALL和INS两个宏分别表示：“所有的内容"和"插入迭代器” .