集合栈计算机 stack+map+set

题目描述

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