首页 > 代码库 > UVA 12096 STL map set 的使用

UVA 12096 STL map set 的使用

2024-07-17 19:21:07   213人阅读

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

 

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

举例说明 ：

 1 #include<iostream> 2 include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<map> 6 #include<set> 7 #include<algorithm> 8 #include<string> 9 10 using namespace std;11 12 int main(void)13 {14     map<string,int> smap;15     smap["Hello"]=3;16     smap["World"]=1;17     string ss;18     cin>>ss;19     cout<<smap[ss];20     return 0;21 }

 

 

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

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

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

 

 

下面是题目pdf ：

uva.onlinejudge.org/external/120/12096.pdf

 

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

同一个集合共享一个ID

代码如下

 1 #include<iostream> 2 #include<string> 3 #include<cstdio> 4 #include<vector> 5 #include<set> 6 #include<stack> 7 #include<algorithm> 8 #include<map> 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<int> Set;16 map<Set,int> IDcache;17 vector<Set> 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<int> 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<<Setcache[s.top()].size()<<endl;59         }60         cout<<"***"<<endl;61     }62     return 0;63 }

 

 
 
 


联系
我们