程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 12096 - The SetStack Computer(STL)

uva 12096 - The SetStack Computer(STL)

編輯：C++入門知識

uva 12096 - The SetStack Computer(STL)

題目鏈接：uva 12096 - The SetStack Computer

題目大意：一個棧，有5種操作；

PUSH：向棧中放一個空集合。
DUP：復制棧頂集合。
UNION：取棧頂的兩個集合，取並集後放回。
INTERSECT：取棧頂的兩個集合，取交集後放回。

ADD：取棧頂兩個集合，將第一個集合作為元素放到第二個集合中，並將第二個集合放回棧。

每次操作後輸出棧定集合中元素的個數。

解題思路：將所有集合映射成一個值，用map記錄，然後模擬操作即可。

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef set sint;
typedef set::iterator iter;

int hn;
stack stak;
map g;

void hashadd (sint u) {
    if (g.count(u))
        return;
    g[u] = hn++;
}

void putsize () {
    if (stak.empty())
        return;
    printf("%d\n", (int)stak.top().size());
}

void sf_push () {
    sint u;
    hashadd(u);
    stak.push(u);
}

void sf_dup () {
    sint u = stak.top();
    stak.push(u);
}

void sf_union () {
    sint f = stak.top();
    stak.pop();
    sint u = stak.top();
    stak.pop();

    for (iter i = f.begin(); i != f.end(); i++)
        u.insert(*i);
    hashadd(u);
    stak.push(u);
}

void sf_inct () {
    sint u;
    sint f = stak.top();
    stak.pop();
    sint s = stak.top();
    stak.pop();

    for (iter i = f.begin(); i != f.end(); i++) {
        if (s.count(*i))
            u.insert(*i);
    }

    hashadd(u);
    stak.push(u);
}

void sf_add () {
    sint f = stak.top();
    stak.pop();
    sint s = stak.top();
    stak.pop();

    s.insert(g[f]);
    hashadd(s);
    stak.push(s);
}

void solve () {
    char order[10];
    scanf("%s", order);
    switch (order[0]) {
        case 'P':
            sf_push();
            break;
        case 'D':
            sf_dup();
            break;
        case 'U':
            sf_union();
            break;
        case 'I':
            sf_inct();
            break;
        case 'A':
            sf_add();
            break;
    }
    putsize();
}

int main () {
    int cas, n;
    scanf("%d", &cas);

    while (cas--) {
        hn = 0;
        g.clear();
        while (!stak.empty())
            stak.pop();

        scanf("%d", &n);
        while (n--)
            solve();
        printf("***\n");
    }
    return 0;
}