UVa12096 - The SetStack Computer

題目大意：

模擬一個集合的堆疊計算機。該計算機有5種指令

1. PUSH：新增一個{}空集合到 Stack
2. DUP：複製 Stack 的 Top 集合，再Push到 Stack
3. ADD：將 Stack Pop 2個集合，最先 Pop 的集合 a 和第 2 個 Pop 的集合 b，將集合 a 加入至集合 b 後再 Push 到 Stack
4. UNION：將 Stack Pop 2 個集合做 Union 後，再 Push 到 Stack
5. INTERSECT：將Stack Pop 2個集合做Intersect後，再Push到Stack

輸入有T筆測資，每筆測資會有 n 個前面 5 種的指令，每當一個指令完成後，要輸出目前 Stack Top 的集合的元素數量。當N個指令完成後，輸出 ***。

分析：

這題我也是看其他優秀大神寫出來的，高手太多了，小弟我只是一個小孩子罷了。

STL 真的棒，省去底層的操作。

在操作 set 的過程中，請記住，不要就傻傻可愛的直接用 set ( set 裡面又有 set 的話，交、聯集的函式庫無法被使用的！)

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
map<set<int> , int> mapSet ;
map<int , set<int> > mapSetReverse ;
vector<int> vecStack ;
int intHash ;


int set_hash(set<int> setTemp){
    int &intTemp = mapSet[setTemp] ;
    if(!intTemp){
        mapSetReverse[intHash] = setTemp ;
        intTemp = intHash++ ;
    }
    return intTemp ;
}


int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout);
#endif // LOCAL
    int t , n ;
    string strCommand  ;
    set<int> setA , setB , setC ;
    int intA , intB , intC ;
    cin >> t ;
    while(t--){
        cin >> n ;
        intHash = 1 ;
        vecStack.clear() ;
        mapSet.clear() ;
        mapSetReverse.clear() ;
        while(n--){
            cin >> strCommand ;
            if(strCommand == "PUSH"){
                setA = {} ;
                vecStack.push_back(set_hash(setA)) ;
            }
            else if(strCommand == "DUP"){
                vecStack.push_back(vecStack.back()) ;
            }
            else if (strCommand == "UNION"){
                setA = mapSetReverse[vecStack.back()] ;
                vecStack.pop_back() ;
                setB = mapSetReverse[vecStack.back()] ;
                vecStack.pop_back() ;
                setC = {} ;
                set_union(setA.begin() , setA.end() , setB.begin() , setB.end() , inserter(setC , setC.begin())) ;
                vecStack.push_back(set_hash(setC)) ;
            }
            else if (strCommand == "INTERSECT"){
                setA = mapSetReverse[vecStack.back()] ;
                vecStack.pop_back() ;
                setB = mapSetReverse[vecStack.back()] ;
                vecStack.pop_back() ;
                setC = {} ;
                set_intersection(setA.begin() , setA.end() , setB.begin() , setB.end() , inserter(setC , setC.begin())) ;
                vecStack.push_back(set_hash(setC)) ;
            }
            else if(strCommand == "ADD"){
                intA = vecStack.back() ;
                vecStack.pop_back() ;
                setB = mapSetReverse[vecStack.back()] ;
                vecStack.pop_back() ;
                setB.insert(intA) ;
                vecStack.push_back(set_hash(setB)) ;
            }
            cout << mapSetReverse[vecStack.back()].size() << '\n' ;
        }

        cout << "***" << '\n';
    }
    return 0;
}