UVA 12096 STL map set 的使用-白红宇

UVA 12096 STL map set 的使用

阅读量：5161 次

发布时间：2019-06-13

本文共 1740 字，大约阅读时间需要 5 分钟。

set这个容器也是STL库的一员，并且在algorithm内直接有 set_union set_intersection 这样求并集交集的操作

map 最方便的地方就是支持下标访问

举例说明：

1 #include
     
       2 include
      
        3 #include
       
         4 #include
        
          5 #include
          6 #include
          
            7 #include
           
             8 #include
            
              9 10 using namespace std;11 12 int main(void)13 {14 map
             
               smap;15 smap["Hello"]=3;16 smap["World"]=1;17 string ss;18 cin>>ss;19 cout<

上面的是 map的用法特殊的地方只有 15 16 行而且很好理解，不做解释了

map<string,int> 简单理解指的就是把 string作为下标数组内的元素为int

实际上是建立起 key-value 的一个对应关系 0.0

下面是题目pdf ：

本题的思想就是给每个集合一个独特的ID

同一个集合共享一个ID

代码如下

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
             9 10 #define ALL(x) x.begin(),x.end()11 #define INS(x) inserter(x,x.begin())12 13 using namespace std;14 15 typedef set
             
               Set;16 map
              
                IDcache;17 vector
               
                 Setcache;18 19 int ID(Set x)20 {21 if(IDcache.count(x)) return IDcache[x];22 Setcache.push_back(x);23 return IDcache[x]=Setcache.size()-1;24 }25 26 int main(void)27 {28 stack
                
                  s;29 int n;30 int T;31 cin>>T;32 while(T--)33 {34 cin>>n;35 while(n--)36 {37 char op[10];38 scanf("%s",op);39 if(op[0]=='P')40 s.push(ID(Set()));41 else if(op[0]=='D')42 s.push(s.top());43 else44 {45 Set x1=Setcache[s.top()];s.pop();46 Set x2=Setcache[s.top()];s.pop();47 Set x;48 if(op[0]=='U')49 //x=set_union(ALL(x1),ALL(x2),INS(x));50 set_union(ALL(x1),ALL(x2),INS(x));51 if(op[0]=='I')52 //x=set_intersection(ALL(x1),ALL(x2),INS(x));53 set_intersection(ALL(x1),ALL(x2),INS(x));54 if(op[0]=='A')55 {x=x2;x.insert(ID(x1));}56 s.push(ID(x));57 }58 cout<
                 
                  <