懒的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 ***
#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库里面有对应打包好的函数可以直接调用。