UVA - 12096 The SetStack Computer - c++编程基础

维护 N(1≤N≤2000) 个操作, 可能的五种操作如下:
PUSH: 在栈顶加入一个空集合 A={} ;
DUP: 把栈顶集合 A 复制一遍再加进去;
UNION: 弹出栈顶集合 A 及其下集合 B , 把它们的并集加入栈;
INTERSECT: 弹出栈顶集合 A 及其下集合 B , 把他们的交集加入栈;
ADD: 弹出栈顶集合 A 及其下集合 B , 把栈顶集合 A 作为一个元素加入集合 B , 再把集合 B 加入栈中.

对于每个操作, 输出栈顶集合 A 中的元素个数.

思路：STL的各种应用，注意Add的时候要注意，本来判断是否出现这个集合，没有的话，才设置一个唯一值再加入集合，但是这样不对，不管是否出现都加入才对

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
       #include 
       
         using namespace std; const int MAXN = 2010; const int N = 20; int cnt; stack
        
          > stk; map
         
          , int> mp; set
          
            s1,s2; void pop(){ s1 = stk.top(); stk.pop(); s2 = stk.top(); stk.pop(); } void Push(){ set
           
             s; stk.push(s); printf("0\n"); } void Dup(){ set
            
              s; s = stk.top(); stk.push(s); printf("%d\n",s.size()); } void Union(){ pop(); set
             
              ::iterator it; for (it = s1.begin(); it != s1.end(); it++) s2.insert(*it); stk.push(s2); printf("%d\n",s2.size()); } void Intersect(){ pop(); set
              
                s3; set
               
                ::iterator it; for (it = s1.begin(); it != s1.end(); it++) if (s2.find(*it) != s2.end()) s3.insert(*it); stk.push(s3); printf("%d\n",s3.size()); } void Add(){ pop(); if (s1.empty()) s2.insert(0); else { if (!mp[s1]) mp[s1] = cnt++; s2.insert(mp[s1]); } stk.push(s2); printf("%d\n",s2.size()); } int main(){ int t,n; char str[N]; scanf("%d",&t); while (t--){ scanf("%d",&n); while (!stk.empty()) stk.pop(); cnt = MAXN; mp.clear(); while (n--){ scanf("%s",str); if (str[0] == 'P') Push(); else if (str[0] == 'D') Dup(); else if (str[0] == 'U') Union(); else if (str[0] == 'I') Intersect(); else Add(); } printf("***\n"); } return 0; }