題目鏈接

有一個專門為了集合運算而設計的“集合棧”計算機。該機器有一個初始為空的棧，并且
支持以下操作。

• PUSH：空集“{}”入棧。
• DUP：把當前棧頂元素復制一份后再入棧。
• UNION：出棧兩個集合，然后把二者的并集入棧。
• INTERSECT：出棧兩個集合，然后把二者的交集入棧。
• ADD：出棧兩個集合，然后把先出棧的集合加入到后出棧的集合中，把結果入棧。

每次操作后，輸出棧頂集合的大小（即元素個數）。例如，棧頂元素是A={{}，
{{}}}，下一個元素是B={{}，{{{}}}}，則：

• UNION操作將得到{{}，{{}}，{{{}}}}，輸出3。
• INTERSECT操作將得到{{}}，輸出1。
• ADD操作將得到{{}，{{{}}}，{{}，{{}}}}，輸出3。

輸入不超過2000個操作，并且保證操作均能順利進行（不需要對空棧執行出棧操作）。
【分析】
本題的集合并不是簡單的整數集合或者字符串集合，而是集合的集合。為了方便起見，此處為每個不同的集合分配一個唯一的ID，則每個集合都可以表示成所包含元素的ID集合，這樣就可以用STL的set<int>來表示了，而整個棧則是一個stack<int>。?

#include<iostream> #include<string> #include<set> #include<map> #include<stack> #include<vector> #include<algorithm> using namespace std;#define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin())typedef set<int> Set; map<Set,int> IDcache; // 把集合映射成ID vector<Set> Setcache; // 根據ID取集合// 查找給定集合x的ID。如果找不到，分配一個新ID int ID (Set x) {if (IDcache.count(x)) return IDcache[x];Setcache.push_back(x); // 添加新集合return IDcache[x] = Setcache.size() - 1; }int main () {int T;cin >> T;while(T--) {stack<int> s; // 題目中的棧int n;cin >> n;for(int i = 0; i < n; i++) {string op;cin >> op;if (op[0] == 'P') s.push(ID(Set()));else if (op[0] == 'D') s.push(s.top());else {Set x1 = Setcache[s.top()]; s.pop();Set x2 = Setcache[s.top()]; s.pop();Set x;if (op[0] == 'U') set_union (ALL(x1), ALL(x2), INS(x));if (op[0] == 'I') set_intersection (ALL(x1), ALL(x2), INS(x));if (op[0] == 'A') { x = x2; x.insert(ID(x1)); }s.push(ID(x));} cout << Setcache[s.top()].size() << endl;}cout << "***" << endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的The SetStack Computer UVA - 12096 集合栈计算机 set集合的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。