集合栈计算机(The SetStack Computer, UVa12096）

Dear 丶 2022-05-19 14:09 82阅读 0赞

**题目：**  
有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈，并且支持以下操作：  
\*PUSH：空集“\{ \}“入栈  
\*DUP：把当前栈顶元素复制一份后再入栈  
\*UNION：出栈两个集合，然后把二者的并集入栈。  
\*INTERSECT：出栈两个集合，然后把二者的交集入栈。  
\*ADD：出栈两个集合，然后把先出栈的集合加入到后出栈的集合中，把结果入栈。  
每次操作之后，输出栈顶集合的大小（即元素个数）。例如：栈顶元素是A=\{ \{ \}，\{ \{ \}\} \}，下一个元素是B=\{ \{ \}，\{ \{ \{ \}\}\} \},则：  
UNION操作得到：\{ \{ \}，\{ \{ \}\}，\{ \{ \{ \}\}\} \}，输出3.  
INTERSECT操作得到：\{ \{ \} \},输出1.  
ADD操作得到：\{ \{ \}, \{ \{ \{ \}\}\}, \{ \{ \},\{ \{ \}\}\} \}.，输出3

**分析**  
本题的集合并非简单的整数或字符串集合，而是集合的集合。很难直接表示，所以为方便起见，为每个不同的集合分配一个唯一的ID  
，则每个集合表示为所包含元素（集合）的ID集合。这样就可以用STL中的`set<int>`来表示，而整个栈则是一个`stack<int>`。

1.  在进行操作时，使用map将每种集合与对应ID相关联，既可完成查找ID，也可判定是否出现新集合。
2.  使用vector作为存储每种集合的cache，当map中没有相应的ID时，向vector加入一个`set<int>`元素，并将下标作为ID进行唯一标识。
3.  使用vector将Set存储：可以用ID查询到对应的set。这样通过map和vector实现set到ID的双射。
4.  最后 ，输出栈顶集合的大小（元素个数）。

**AC代码如下：**

#include<iostream>
    #include<cstdio>
    #include<algorithm> //set_union函数定义在其中 
    #include<set>
    #include<map>
    #include<vector> 
    #include<stack>
    
    #define ALL(x) x.begin(),x.end() 
    #define INS(x) inserter(x,x.begin()) 
    using namespace std;
    
    typedef set<int> Set;    //每个集合表示为所包含元素的ID集合
    map<Set,int> IDcache;    //把集合映射成ID（用map将每种集合与对应的ID关联起来）
    vector<Set> Setcache;    //根据ID取集合。
    
    //查找给定集合x的ID。如果找不到，分配一个新的ID 
    int ID(Set x) { 
    	if(IDcache.count(x)) return IDcache[x];
    	Setcache.push_back(x);         //添加新集合
    	return IDcache[x] =Setcache.size()-1;   //将ID值加入map，同时返回新分配的ID值。 
    }
    
    int  main(){ 
    	stack<int> s;
    	int n,t;
    	string op;
    	scanf("%d",&t);
    	while(t--){ 
    	cin>>n;
    	for(int i=0;i<n;i++){ 
    		cin>>op;
    		if(op[0]=='P') s.push(ID(Set()));
    		else if(op[0]=='D') s.push(s.top());
    		else{ 
    			Set x1=Setcache[s.top()];s.pop();
    			Set x2=Setcache[s.top()];s.pop();
    			Set x;
    			if(op[0]=='U')set_union(ALL(x1),ALL(x2),INS(x));
    			if(op[0]=='I')set_intersection(ALL(x1),ALL(x2),INS(x));
    			if(op[0]=='A'){  x=x2;x.insert(ID(x1));}
    			s.push(ID(x));
    		}
    		cout<<Setcache[s.top()].size()<<endl;
    	}
    	printf("***\n");
    }
    	return 0;
    }

解释说明：

1.  对任意集合s(类型是上面定义的Set），IDcache\[s\]就是其ID，而Setcache\[ IDcache\[s\] \]就是其s本身。
2.  ALL和INS两个宏分别表示：“所有的内容"和"插入迭代器” .