很久没写博客了，今天终于回来了，没错我就是成绩不咋地noip考的很渣的zhcnyuyang。
今天要讲的是uva第12096题，题意大家也都清楚。本题特殊的地方在于，本题中的集合里的元素不是数字，不是字符，而是集合。所以要用到map类（需要导入map头文件，即在程序开头出写上#include<map>），让每一个集合都对应一个int数字。为什么要这样做呢。比方说你有一个集合，里边有俩元素，一个是空集，一个里边还套着一个集合，那你怎么办？是把这个集合定义为set<set<int>>还是set<set<set<int>>>啊？所以莫不如让每个集合都对应一个数字，当你要把一个集合添加到另一个集合里时，直接把它对应的数字添加进去就行了，像这样：
//把集合s2添加到s1中 set<int> s1; set<int> s2; map<set<int>,int> m; m[s2]=1; s1.insert(m[s2]);
每个集合对应的整数值可以任意赋值。但值得注意的是,集合在m中对应的数字，取决于集合的值。比方说如果s1和s2的值相等，那么m[s1]和m[s2]就也相等,如果s1的值发生了改变，那么s1的值改变前后所对应的值也不一样。
比如现在有一个栈
{{}}//s2
{}//s1
现在用DUP将栈顶元素复制一份后入栈，变成了
{{}}//s3
{{}}//s2
{}//s1
这时s3和s2的值是一样的，所以s2和s3对应的数值也是相等的。现在定义一个map类型数组
map<set<int>,int> m;
则m[s2]与m[s3]是相等的。而s1由于值与s2不相等，所以m[s1]与m[s2]不相等。
现在输入DUP命令，栈中元素为
{{}，{{}}}//s2
{}//s1
这时m[s2]的值与操作前m[s2]的值不相等。
因此，当出现一个新集合，或者改变原有集合的值时，一定要看map数组中是否有与新集合或集合的新值相等的元素，如果没有，再给新集合或集合新值在map数组中对应的数字赋新值。
上代码：
/* Name: uva12096-The SetStack Computer Copyright: Author: yuyang Date: 08/01/17 13:55 Description: */ #include<cstdio> #include<stdlib.h> #include<algorithm> #include<iostream> #include<set> #include<map> #include<cstring> #include<string> #include<stack> using namespace std; typedef set<int> Set; typedef map<set<int>,int> Map; typedef stack<set<int> > Stack; int t,n,num; string op; Map mp; Set st,st2,emptyst; Stack stk; void clear(){ while(!stk.empty()){ stk.pop(); } } void output(){ Set s=stk.top(); cout<<s.size()<<"\n"; } void push(){ Set sst; //mp[sst]=++num; stk.push(sst); output(); } void dup(){ st=stk.top(); stk.push(st); output(); } void Union(){ st=stk.top(); stk.pop(); st2=stk.top(); stk.pop(); Set st3=st2; for(set<int>::iterator i=st.begin();i!=st.end();i++){ st3.insert(*i); } if(st2.empty()){ stk.push(st); }else if(st.empty()){ stk.push(st2); }else{ mp[st3]=++num; stk.push(st3); } output(); } void intersect(){ st=stk.top(); stk.pop(); st2=stk.top(); stk.pop(); Set st3; mp[st3]=++num; for(set<int>::iterator i=st.begin();i!=st.end();i++){ if(st2.count(*i)!=0){ st3.insert(*i); } } if(st3==st){ stk.push(st); }else if(st3==st2){ stk.push(st2); }else{ if(!mp.find(st3)){ mp[st3]=++num; } stk.push(st3); } output(); } void add(){ st=stk.top(); stk.pop(); st2=stk.top(); stk.pop(); st2.insert(mp[st]); if(!mp.find(st2)){ mp[st2]=++num; } stk.push(st2); output(); } int main(){ freopen("uva12096in.txt","r",stdin); cin>>t; mp[emptyst]=-1;//空集对应的数值为-1 for(int i=1;i<=t;i++){ num=0; cin>>n; for(int i=1;i<=n;i++){ cin>>op; if(op=="PUSH"){ push(); }else if(op=="DUP"){ dup(); }else if(op=="UNION"){ Union(); }else if(op=="INTERSECT"){ intersect(); }else if(op=="ADD"){ add(); } } cout<<"***\n"; clear(); } return 0; }
uva12096 The SteStack Computer
原文：http://www.cnblogs.com/zhcnyuyang/p/6263193.html