题目描述
懒的copy英文了，反正大家都是看中文的题目。
有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈，并且支持以下操作：
PUSH：空集“{}”入栈 DUP：把当前栈顶元素复制一份后再入栈
UNION：出栈两个集合，然后把两者的并集入栈
INTERSECT：出栈两个集合，然后把二者的交集入栈
ADD：出栈两个集合，然后把先出栈的集合加入到后出栈的集合中，把结果入栈 每次操作后，输出栈顶集合的大小（即元素个数）。
例如栈顶元素是A={ {}， {{}} }， 下一个元素是B={ {}， {{{}}} }，则： UNION操作将得到{ {}， {{}}， {{{}}} }，输出3. INTERSECT操作将得到{ {} }，输出1 ADD操作将得到{ {}， {{{}}}， { {}， {{}} } }，输出3。
样例输入
2 9 PUSH DUP ADD PUSH ADD DUP ADD DUP UNION 5 PUSH PUSH ADD PUSH INTERSECT
样例输出
0 0 1 0 1 1 2 2 2 *** 0 0 1 0 0 ***
代码
代码语言：javascript复制#include<iostream>
#include<set>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
int main(){
stack<set<int>>computer;
map<set<int>,int>setint;
int t,o,whole=0;
string instruction;
cin>>t;
while(t--){
cin>>o;
while(o--){
cin>>instruction;
set<int>temp;
if(instruction=="PUSH"){temp.clear();}
else if(instruction=="DUP"){temp=computer.top();}
else{
set<int>a=computer.top();
computer.pop();
set<int>b=computer.top();
computer.pop();
if(instruction=="UNION"){set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(temp,temp.begin()));}
else if(instruction=="INTERSECT"){set_intersection(a.begin(),a.end(),b.begin(),b.end(),inserter(temp,temp.begin()));}
else{
temp=b;
temp.insert(setint[a]);
}
}
computer.push(temp);
if(!setint.count(temp))setint[temp]=whole ;
cout<<computer.top().size()<<endl;
}
cout<<"***"<<endl;
}
}思路分析
第一次看到题目，觉得没什么问题，然后准备开打，发现 {} 这玩意好像实现有点困难，不行了，看书上代码吧，看得我一脸懵逼，集合和编号，有点烧脑，都是空集，怎么这么多花样？这是怎么从0变1的，最重要的是ADD是怎么实现的？
先说一下书主刘汝佳的思路，对于这个集合的集合，完了还是空集的集合，一堆空集被套，大哥的思路是用一个编号对应一个集合，先是用一个map映射把集合映射成int编号，再用一个vector把所有集合存起来，并让其下标成为集合的编号存进map，定义了一个int型的stack，存储集合的编号。
这个题最关键的地方就是ADD的怎么实现，大哥的思路就是把前一个集合的编号当作元素插入后一个集合里面。
而我的思路则是在此基础上进行了改进，将原代码砍了一半，对于集合的集合，我让他仍是集合，我直接定义了一个set型的stack，这样更加符合题目的认知，就是一个集合栈，而对于集合中的元素集合，就采用int型来表示。
再说一下细节：
对于并集和交集，algorithm库里面有对应打包好的函数可以直接调用。
