UVA12096 集合栈计算机 The SetStack Computer

题目传送门

一道非常好的 STL 综合练习题。

题目大意：

有五个动作：

push：把一个空集合放到栈顶。

dup：把栈顶的集合取出来，在入栈两次。

add：出栈两次。把第一个集合作为一个元素放入第二个集合中，再将第二个集合入栈。

union：出栈两次，取这两个集合的并集。将结果入栈。

intersect：出栈两次。取这两个集合的交集，将结果入栈。

每次运行动作后还须要输出当前栈顶集合的元素个数。

思路：

用栈和 set 集合容器来模拟，push 就把空的集合入栈，可是在并集和交集的时候就须要判段集合是否同样，所以这里能够用 map 映照容器把出现过的集合手动的映射成数字。

CODE ：

#include<bits/stdc++.h> 
#define int long long
using namespace std;
inline int read(){//快读
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
char op[15];
int n,t;
stack<set<int> >s;
map<set<int>,int>vis;
set<int>tmp1,tmp2;
int num;
inline void Hash(set<int> a){//哈希
    if(!vis.count(a))vis[a]=++num;
}
inline void push(){
    tmp1.clear();//清空集合
    s.push(tmp1);//将其放到栈顶            
}
inline void dup(){
    tmp1=s.top();//取出栈顶
    s.push(tmp1);//入栈
}
inline void add(){
    tmp2=s.top();
    s.pop();//弹出栈顶
    tmp1=s.top();
    s.pop();//弹出栈顶
    tmp1.insert(vis[tmp2]);//将第一个集合放入第二个集合中
    Hash(tmp1);
    s.push(tmp1);//哈希后将第二个集合入栈
}
inline void Union(){
    tmp2=s.top();    
    s.pop();//弹出栈顶
    tmp1=s.top();
    s.pop();//弹出栈顶
    for(set<int>::iterator it=tmp1.begin();it!=tmp1.end();it++)tmp2.insert(*it);//用 set 的特性--去重找到两个集合的并集
    Hash(tmp2);
    s.push(tmp2);//入栈   
}
inline void intersect(){
    tmp2=s.top();
    s.pop();//弹出栈顶
    tmp1=s.top();
    s.pop();//弹出栈顶
    set<int>tmp;
    for(set<int>::iterator it=tmp1.begin();it!=tmp1.end();it++)
        if(tmp2.count(*it))tmp.insert(*it);//同样用 set 的特性取出两个集合的并集
    Hash(tmp);
    s.push(tmp);//入栈
}
inline void solve(){//五个操作，放在函数里更清晰一些
    switch(op[0]){
        case'P':push();break;
        case'D':dup();break;
        case'U':Union();break;
        case'I':intersect();break;
        case'A':add();break;
    }
    cout<<s.top().size()<<endl; 
}
signed main(){
    t=read();
    while(t--){
        n=read();
        while(n--){
            cin>>op;
            solve();                
        }
        cout<<"***"<<endl;
    }
    return 0;
}