题目大意：
对于一个以集合为元素的栈，初始时栈为空。
输入的命令有如下几种：
PUSH：将空集{}压栈
DUP：将栈顶元素复制一份压入栈中
UNION：先进行两次弹栈，将获得的集合A和B取并集，将结果压栈
INTERSECTION：先进行两次弹栈，将获得的集合A和B取交集，将结果压栈
ADD：先进行两次弹栈，将获得的集合A和B中，先出栈的集合（如A先）加入到后出栈的集合，将结果压栈
输出每一步操作后栈顶集合的元素的个数。
题目详细信息见传送门
思路如下：
对于集合的集合，我们很难直接表示，因此，我们可以换一种想法，既然集合的集合难以表示，我们就只需要给每种集合一个唯一的ID就可以了，这样，集合中的元素就可以通过ID来表示。一个集合就可以表示为一个set<int>
在这里，我们使用STL中的set进行表示，就会容易很多，加入栈中的元素也就可以是int类型了。
在进行操作时，我们可以用map将每种集合与对应的ID关联起来，这样做既可以完成查找ID的任务，还可以同时判定是否出现了新的集合。
我们可以用vector作为存储每种集合的cache，这样，每当map中没有相应的ID时，我们就向vector中加入一个set<int>元素，并将下标作为ID进行唯一的标识。
使用vector将set存储起来的好处是，反过来我们也可以用ID查询到对应的set，这样，通过map和vector，我们实现了set 到ID 的双射。
最后，输出栈顶集合的size属性，即可。
代码如下：
1 //UVA12096 集合栈计算机 2 #include<cstdio> 3 #include<iostream> 4 #include<algorithm>//set_union等函数定义在这里 5 #include<vector> 6 #include<set> 7 #include<map> 8 #include<stack> 9 10 #define ALL(x) x.begin(),x.end() 11 #define INS(x) inserter(x,x.begin()) //注意宏的括号和inserter 12 13 using namespace std; 14 15 typedef set<int> Set; 16 map<Set,int> IDCache; 17 vector<Set> setCache; 18 int t,n; 19 char cmd[10]; 20 int getID(Set s){ 21 if(IDCache.count(s))return IDCache[s]; 22 setCache.push_back(s); //将新集合加入Setcache 23 return IDCache[s]=setCache.size()-1;//将ID加入map ，同时返回新分配的ID值 24 } 25 26 int main(){ 27 scanf("%d",&t); 28 while(t--){ 29 scanf("%d",&n); 30 // setCache.clear(); 31 stack<int> s; 32 while(n--){ 33 scanf(" %s",&cmd); 34 if(cmd[0]=='P')s.push(getID(Set())); 35 else if(cmd[0]=='D')s.push(s.top()); 36 else{ 37 Set s1=setCache[s.top()];s.pop(); 38 Set s2=setCache[s.top()];s.pop(); 39 Set x; 40 if(cmd[0]=='U')set_union(ALL(s1),ALL(s2),INS(x)); 41 if(cmd[0]=='I')set_intersection(ALL(s1),ALL(s2),INS(x)); 42 if(cmd[0]=='A'){ x=s2; x.insert(getID(s1)); } 43 s.push(getID(x)); 44 } 45 printf("%d ",setCache[s.top()].size()); 46 } 47 puts("***"); 48 } 49 }
注意：
第30行的setCache.clear()是必须注释掉的，因为如果存在这一句，那么vector就会清空，但是对应的map却没有清空，就会出现wa的情况。
从另一个角度说，只需要map和vector始终保持一致那么set和ID 的双射关系就不会发生改变，此时我们就不需要将map和vector清空，因为不影响后续操作的结果。