【刘汝佳书】例题5-5 UVA12096 （stack、map的练习）

113 阅读 0 评论 75 点赞

我是靠谱客的博主辛勤荔枝，这篇文章主要介绍【刘汝佳书】例题5-5 UVA12096 （stack、map的练习），现在分享给大家，希望可以做个参考。

自己的想法：用set<string>来存集合，把括号当成字符串中的字符
结果：超时，遂抄书上代码

用map<set, int>为集合建立ID，再用vector<set>根据ID取集合，这两个要学会

复制代码

#include <iostream>
#include <stack>
#include <set>
#include <map>
#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取集合
stack<int> s;           //装集合ID的栈

int getID(Set s) {
    if(IDcache.count(s)) return IDcache[s];
    Setcache.push_back(s);
    IDcache[s] = Setcache.size()-1;
    return Setcache.size()-1;
}

int main()
{
    //freopen("C:\Users\Summer\Desktop\input.txt", "r", stdin);
    //freopen("C:\Users\Summer\Desktop\output.txt", "w", stdout);

int test_num, opre_num;
    string opre;
    cin>>test_num;
    while(test_num--) {
        while(!s.empty()) s.pop();

cin>>opre_num;
        while(opre_num--) {
            cin>>opre;
            if(opre == "PUSH") {
                s.push(getID(Set()));
            }
            else if(opre == "DUP") {
                s.push(s.top());
            }
            else {
                Set a = Setcache[s.top()]; s.pop();
                Set b = Setcache[s.top()]; s.pop();
                Set c;

if(opre[0] == 'U')      set_union(ALL(a), ALL(b), INS(c));
                else if(opre[0] == 'I') set_intersection(ALL(a), ALL(b), INS(c));
                else {  //opre == "ADD"
                    c = b;
                    c.insert(getID(a));
                }
                s.push(getID(c));
            }

cout<< Setcache[s.top()].size() <<endl;
        }
        cout<<"***"<<endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <stack>
#include <set>
#include <map>
#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取集合
stack<int> s;           //装集合ID的栈

int getID(Set s) {
    if(IDcache.count(s)) return IDcache[s];
    Setcache.push_back(s);
    IDcache[s] = Setcache.size()-1;
    return Setcache.size()-1;
}

int main()
{
    //freopen("C:\Users\Summer\Desktop\input.txt", "r", stdin);
    //freopen("C:\Users\Summer\Desktop\output.txt", "w", stdout);

    int test_num, opre_num;
    string opre;
    cin>>test_num;
    while(test_num--) {
        while(!s.empty()) s.pop();

        cin>>opre_num;
        while(opre_num--) {
            cin>>opre;
            if(opre == "PUSH") {
                s.push(getID(Set()));
            }
            else if(opre == "DUP") {
                s.push(s.top());
            }
            else {
                Set a = Setcache[s.top()]; s.pop();
                Set b = Setcache[s.top()]; s.pop();
                Set c;

                if(opre[0] == 'U')      set_union(ALL(a), ALL(b), INS(c));
                else if(opre[0] == 'I') set_intersection(ALL(a), ALL(b), INS(c));
                else {  //opre == "ADD"
                    c = b;
                    c.insert(getID(a));
                }
                s.push(getID(c));
            }

            cout<< Setcache[s.top()].size() <<endl;
        }
        cout<<"***"<<endl;
    }
    return 0;
}