首页 > 代码库 > uva12096

uva12096

点击打开链接uva 12096
 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 #include<set> 6 #include<stack> 7 #include<vector> 8 #include<map> 9 #include<algorithm>//set_union函数在这个头文件里面;10 using namespace std;//set vector等需要使用命名空间才能使用;11 typedef set<int> Set;12 map<Set,int> IDcache;13 vector<Set> Setcache;14 15 int ID(Set x)16 {17   if(IDcache.count(x)) return IDcache[x];//map.count(r)是查找元素x出现的次数;18   Setcache.push_back(x);19   return IDcache[x]=Setcache.size()-1;20 }21 22 #define ALL(x) x.begin(),x.end() // 表示 所有内容23 #define INS(x) inserter(x,x.begin()) //表示 插入迭代器24 25 int main()26 {27   int t;28   scanf("%d",&t);29   while(t--)30   {31     stack<int> s;32     int n;33     cin>>n;34     for(int i=0; i<n; i++)35     {36       string op;37       cin>>op;38       if(op=="PUSH")39       {40         s.push(ID(Set()));41       }42       else if(op=="DUP") s.push(s.top());43       else44       {45         Set x1=Setcache[s.top()];46         s.pop();47         Set x2=Setcache[s.top()];48         s.pop();49         Set x;50         if(op=="UNION") set_union (x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));51         if(op=="INTERSECT") set_intersection (x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));52         if(op=="ADD")53         {54           x=x2;55           x.insert(ID(x1));56         }57         s.push(ID(x));58       }59       cout<<Setcache[s.top()].size()<<endl;60     }61     printf("***\n");62   }63   return 0;64 }
View Code

 

uva12096