UVA 12096 STL map set 的使用

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             else
44             {
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 }