題目描述很簡(jiǎn)單，難點(diǎn)在于如何對(duì)集合進(jìn)行編碼，因?yàn)槭菬o限的，好像沒有一個(gè)方向進(jìn)行編碼。
紫書給的題解十分巧妙：給新出現(xiàn)的集合進(jìn)行編碼
的確，我們沒有必要為所有可能出現(xiàn)的集合編碼后再開始，我們就可以簡(jiǎn)單的根據(jù)出現(xiàn)的次序分配一個(gè)映射值即可，這個(gè)值只要能夠代表這個(gè)集合并且不發(fā)生碰撞。
另一個(gè)巧妙的點(diǎn)是STL中的map竟然支持從對(duì)set的哈希，這個(gè)也太神奇了，雖然不明白是怎么做的，可能要看源碼才能理解。
代碼如下：

需要注意的一點(diǎn)是在switch語句中的case語句后面不能直接聲明局部變量，要放在大括號(hào)里面，形成一個(gè)局部變量。其原因是如果直接定義的話，其他case語句也是可以看到這個(gè)變量的，但是如果不執(zhí)行那個(gè)定義的case語句，就會(huì)導(dǎo)致變量聲明卻沒有定義。原因在于switch其實(shí)就是一種奇特的goto。

#include <iostream> #include <map> #include <set> #include <vector> #include <stack> #include <string> #include <algorithm> #include <iterator>using namespace std; using Set = set<int>;class SetHash {vector<Set> num2set; //保存num到set的映射map<Set, int> set2num; //保存set到num的映射 public:int operator ()(Set s); //獲取一個(gè)set的hash值Set operator ()(int num);//獲取一個(gè)hash值為num的setint getSize(int num) const; };int SetHash::operator()(Set s) {if (!set2num.count(s)) {set2num[s] = num2set.size();num2set.push_back(s);return num2set.size() - 1;} else {return set2num[s];} }Set SetHash::operator()(int num) {return num2set[num]; }int SetHash::getSize(int num) const {return num2set[num].size(); }stack<int> stk; //用于保存集合棧int main() {ios::sync_with_stdio(false);int T, n;string cmd;SetHash setHash;cin >> T;while (T--) {cin >> n;while (n--) {cin >> cmd;if (cmd[0] == 'P') stk.push(setHash(Set()));else if (cmd[0] == 'D') stk.push(stk.top());else {Set a = setHash(stk.top()); stk.pop();Set b = setHash(stk.top()); stk.pop();switch (cmd[0]) {case 'U':b.insert(a.begin(), a.end());stk.push(setHash(b));break;case 'I':{Set c;set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.begin()));stk.push(setHash(c));break;}case 'A':b.insert(setHash(a));stk.push(setHash(b));break;} //}cout << setHash.getSize(stk.top()) << "\n";}cout << "***\n";} }

總結(jié)

以上是生活随笔為你收集整理的UVA - 12096：The SetStack Computer的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。