《算法竞赛入门经典》上的例题。 解题技巧蕴涵的东西不太懂,于是作篇记录。

题面

一个用于集合运算的计算机有一个存储集合的栈,它可以对栈作如下运算:

  • PUSH 在栈顶放上一个空集
  • DUP 在栈顶放上一个与原栈顶集合相同的集合
  • UNION 弹出两个集合,在栈顶放上两集合的并集
  • INTERSECT 弹出两个集合,在栈顶放上两集合的交集
  • ADD 弹出两个集合,将第一个集合作为第二个集合的元素,在栈顶放上第二个集合

输入

第一行包括一个数字0T50\leq T\leq 5,表示测试实例个数; 每个实例第一行包括一个数字0N20000\leq N\leq 2000,表示操作个数。 后接NN行,每行包括一个操作名,表示要进行的操作。

输出

每个操作完成后打印栈顶集合的元素个数。 每个实例后接一行***

样例

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
9
PUSH
DUP
ADD
PUSH
ADD
DUP
ADD
DUP
UNION
5
PUSH
PUSH
ADD
PUSH
INTERSECT

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0
0
1
0
1
1
2
2
2
***
0
0
1
0
0
***

题解

能往集合里添加元素的只有ADD操作 - 所以,集合只含有集合这一种元素。 直接储存集合是不太可行的,这样开销可能会很大。

可以仅储存不同的集合,每个集合用数字代号表示。栈中存储的仅为数字。 每次由于UNIONINTERSECTADD操作得到新的集合,存储该集合和分配新的代号。 从集合查询代号明显需通过map实现。

可以仅用一个map存储集合-代号对吗?不,因为无法实现从代号查找集合。 可以用第二个map吗?可以,但有更好的选择。 代号的分配是任意的,故而可以是线性的,数组下标是最好的选择 - 查询和存储操作代价最低。 因此选择vector

关键操作

维护三个数据结构: stackvectormap

1
2
3
4
5
6
7
8
9
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;

stack<int> stk;
vector<set<int>> v;
map<set<int>, int> mp;

从集合查询代号,操作如下 - 同时实现查询失败分配新代号的部分。

1
2
3
4
5
6
7
8
9
10
11
int get_id(set<int>& s) {
auto refer = mp.find(s);
if (refer != mp.end()) { // 查询成功
return refer->second;
} else {
v.push_back(s); // 存储
int id = v.size() - 1; // 代号即为数组下标
mp[s] = id;
return id; // 放入表中并返回
}
}

代号查集合。

1
2
3
set<int>& get_set(int id) {
return v[id];
}

完整代码

为了可读性做了些封装处理 - 实际用不着这么繁琐,但关键不在执行效率而在编写效率。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// data structure
#include <stack>
#include <map>
#include <vector>
#include <set>
// tools
#include <algorithm>
#include <iterator>
#include <functional>
// IO
#include <string>
#include <iostream>
using namespace std;
class M {
private:
using Set = set<int>;
using Id = int;
map<Set, Id> entry;
vector<Set> cache;
stack<Id> state;
Id id(Set st) {
auto res = entry.find(st);
if (res != entry.end()) {
return res->second;
} else {
cache.push_back(st);
return entry[st] = cache.size() - 1;
}
}
Set& get(Id id) {
return cache[id];
}
void with(function<Set(Set, Set)> f) {
Set s1 = get(state.top()); state.pop();
Set s2 = get(state.top()); state.pop();
Set st = f(s1, s2);
state.push(id(st));
}
public:
void print() {
cout << get(state.top()).size() << '\n';
}
void p() {
state.push(id(Set {}));
}
void d() {
state.push(state.top());
}
void u() {
with([](Set s1, Set s2) {
Set st;
set_union(s1.begin(), s1.end(),
s2.begin(), s2.end(),
inserter(st, st.begin()));
return st;
});
}
void i() {
with([](Set s1, Set s2) {
Set st;
set_intersection(s1.begin(), s1.end(),
s2.begin(), s2.end(),
inserter(st, st.begin()));
return st;
});
}
void a() {
with([&](Set s1, Set s2) {
s2.insert(id(s1));
return s2;
});
}
};
int main() {
ios::sync_with_stdio(0);
int t; cin >> t;
while (t--) {
M m; int n; cin >> n;
while (n--) {
string s; cin >> s;
switch (s[0]) {
case 'P': m.p(); break;
case 'D': m.d(); break;
case 'U': m.u(); break;
case 'I': m.i(); break;
case 'A': m.a(); break;
default: return -1;
}
m.print();
}
cout << "***\n";
}
}