f(sixleaves) = sixleaves

 1 #include <set>
 2 #include <string>
 3 #include <vector>
 4 #include <map>
 5 #include <stack>
 6 #include <iostream>
 7 #include <algorithm>
 8 #define ALL(x) x.begin(), x.end()
 9 #define INS(x) inserter(x, x.begin())
10 
11 using namespace std;
12 
13 typedef set<int> Set;
14 map<Set, int> IDCache;
15 vector<Set> Setcache;
16 // 主要的想法是能想到用map<set<int>, int>這種數據結構來把集合映射成整數
17 // 關鍵實現在ID函數，對于給定的set<int>都能返回一個唯一編號、vector雖然不能保證元素的唯一性。
18 // 但是我們可以先對map進行檢查來保證vector中元素的唯一性，這樣每個元素就能唯一編號，剛好可以利用他們的整數索引。
19 // 其中set_union、set_intersection中得實現原理不是重點，先學會怎么用才是重點。
20 // ID函數實現了對新的集合存儲，并且
21 int ID(Set x);
22 int main() {
23 
24     
25     stack<int> s;
26     int t, n;
27     string op;
28     cin >> t;
29     while (t--) {
30         cin >> n;
31         IDCache.clear();
32         Setcache.clear();
33         for (int i = 0; i < n; i++) {
34 
35             cin >> op;
36             if (op[0] == 'P') s.push(ID(Set())); // Set()就是空集
37             else if(op[0] == 'D') s.push(s.top());
38             else {
39                 
40                 Set x1 = Setcache[s.top()]; s.pop();
41                 Set x2 = Setcache[s.top()]; s.pop();
42                 Set x;
43                 if (op[0] == 'U') set_union (ALL(x1), ALL(x2), INS(x));
44                 if (op[0] == 'I') set_intersection (ALL(x1), ALL(x2), INS(x));
45                 if (op[0] == 'A') { x = x2; x.insert(ID(x1)); }
46                 s.push(ID(x));
47                 
48             }
49             
50             cout << Setcache[s.top()].size() << endl;
51         }
52         cout << "***" << endl;
53     
54     }
55     return 0;
56 }
57 
58 // 相當于數據庫中得auto_increment, 返回一個唯一的ID值
59 int ID(Set x) {
60     
61     if (IDCache.count(x)) return IDCache[x];
62     Setcache.push_back(x);
63     return IDCache[x] = Setcache.size() - 1;
64 
65 }