集合栈计算机 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 ***

代码

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