UVA12096 - The SetStack Computer(set + map映射)

題目鏈接

題目大意：有五個動作：
push ： 把一個空集合{}放到棧頂。
dup ： 把棧頂的集合取出來，在入棧兩次。
add ： 出棧兩次，把第一個集合作為一個元素放入第二個集合中，再將第二個集合入棧
union： 出棧兩次，取這兩個集合的并集，將結果入棧。
intersect： 出棧兩次，取這兩個集合的交集，將結果入棧。
每次執行動作后還需要輸出目前棧頂集合的元素個數。

解題思路：這題可以用棧和set來模擬，push就把空的集合入棧，但是在并集和交集的時候就需要判段集合是否相同，所以這里可以用map把出現過的集合手動的映射成數字。

代碼：

#include <cstdio> #include <cstring> #include <stack> #include <set> #include <map>using namespace std;char op[15]; int n;typedef set<int> E; stack<E> s; map<E, int> vis; E tmp1, tmp2; set<int>::iterator it; int num;void hash (E a) {if (!vis.count(a))vis[a] = ++num; }void Push () {tmp1.clear();s.push (tmp1); }void Dup () {tmp1 = s.top();s.push (tmp1); }void Add () {tmp2 = s.top();s.pop();tmp1 = s.top();s.pop();tmp1.insert (vis[tmp2]);hash(tmp1);s.push(tmp1); }void Union () {tmp2 = s.top(); s.pop();tmp1 = s.top();s.pop();for (it = tmp1.begin(); it != tmp1.end(); it++)tmp2.insert (*it);hash (tmp2);s.push (tmp2); }void Intersect () {tmp2 = s.top();s.pop();tmp1 = s.top();s.pop();E tmp;for (it = tmp1.begin(); it != tmp1.end(); it++)if (tmp2.count(*it))tmp.insert (*it);hash (tmp);s.push(tmp); }void solve () {switch (op[0]) {case 'P' : Push(); break;case 'D' : Dup(); break;case 'U' : Union(); break;case 'I' : Intersect(); break;case 'A' : Add(); break;}printf ("%d\n", s.top().size()); }void init () {num = 1;while (!s.empty()) {s.pop();}vis.clear(); }int main () {int T;scanf ("%d", &T);while (T--) {scanf ("%d", &n);while (n--) {scanf ("%s", op);solve(); }printf ("***\n");}return 0; }

總結

以上是生活随笔為你收集整理的UVA12096 - The SetStack Computer(set + map映射)的全部內容，希望文章能夠幫你解決所遇到的問題。

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