题目
有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈，并且支持以下操作：
-
PUSH：空集“{}”入栈
-
DUP：把当前栈顶元素复制一份后再入栈
-
UNION：出栈两个集合，然后把两者的并集入栈
-
INTERSECT：出栈两个集合，然后把二者的交集入栈
-
ADD：出栈两个集合，然后把先出栈的集合加入到后出栈的集合中，把结果入栈
每次操作后，输出栈顶集合的大小（即元素个数）。
例如栈顶元素是A={ {}， {{}} }， 下一个元素是B={ {}， {{{}}} }，
则：
UNION 操作将得到{ {}， {{}}， {{{}}} }，输出 3
INTERSECT 操作将得到{ {} }，输出 1
ADD 操作将得到{ {}， {{{}}}， { {}， {{}} } }，输出 3
Input:
6
PUSH
PUSH
UNION
PUSH
PUSH
ADD
Output:
0
0
0
0
0
1
分析
题意理解：
这集合嵌套属实脑壳痛，现在可以确定会用到 stack 和 set 两种数据类型
PUSH 只需要在栈顶加个空集合，DUP也很好实现
UNION 和 INTERSECT 取交并集可以使用 algorithm 库来实现
ADD 则可以使用 集合自带的 .insert
但是，set 指明类型时并不能 指set，也就是说 set<set> Set 这条命令是无效的
直接导致 ADD 操作无法实现，所以我们需要重新规划一下数据类型
数据类型：
经过取舍，int类的集合是比较好，我们可以用 数字 来指代每一个独立不重复的集合
例如 {} -- 0 ;
{{},{}} -- 用{0,0}表示 -- 2
{{{},{}} , {{},{}} } -- 用{2 ,2}表示 -- 3
(当然 stack 也是 int类)
以此类推，每得到一个新的集合就用新的数字标识，然后组成以后出现的 集合
那么 vector 就是很好的容器，
vector<Set> Setcache; // Set 是通过 typedef set<int> Set 定义，减少代码量，不必每次都写 set<int>
每一个新的集合就用 加入后的下标 标识 Setcache.size() - 1
从数字找到对应集合解决了，还有从集合找到对应的数字（至于为什么，想想PUSH如何实现就好）
这种映射关系显然可以使用 map
map<Set,int> IDcache;
至于栈中的集合，就用数字来表示
那么数据类型大概就是
map, vector, set, stack 这四种
typedef set<int> Set;
map<Set,int> IDcache;
vector<Set> Setcache;
stack<int> ans;
操作实现：
- PUSH ：
使用 Set() 来生成一个空集合，ans.push() 来加入栈顶，
因为加入的是空集合对应的数字，我们自定义一个函数来实现 集合与数字的转换
ans.push( ID( Set() ) ) // ID() 即为转换函数，后文会介绍
- DUP：
ans.top() 来获得当前栈顶的元素，再用 ans.push() 加入进去即可
ans.push(ans.top())
- UNION 和 INTERSECT ：
使用 algorithm 库里的 set_union 和 set_intersection 来实现
这是它的参数（两个相同）
set_union(
A.begin(),
A.end(), // 第一个集合的开始与结尾
B.begin(),
B.end(), // 第二个集合的开始与结尾
inserter( C , C.begin() ) // 意思是将集合 A、B 取合集后的结果存入集合 C 中
);
如果都要全写上实在有点繁琐，而且两个的参数都类似
我们可以使用 宏函数 来使它简化
// 宏函数在预编译时，用函数定义的代码段来替换函数名，将函数代码段嵌入到当前程序，不会产生函数调用
// 可以理解为一段代码的代替物，但相对于函数效率要高（代码量小的情况下）
#define ALL(x) x.begin(),x.end()
#define ITE(x) inserter(x, x.begin())
所以可这么写
set_union(ALL(x1),ALL(x2),ITE(x));
set_intersection(ALL(x1), ALL(x2), ITE(x));
- ADD：
x.insert() 来加入 集合对应的数字 即可
x = x2;
x.insert( ID(x1) )
因为后三个操作都需要提取两个集合，可以分为一组处理，最后加上 push 操作
- ID()：
传入的是集合类型，所以参数设为 Set set 返回数字
int ID(Set set)
{
if (IDcache.count(set)) return IDcache[set]; // 若已经生成过对应的数字则直接返回
Setcache.push_back(set); // 将集合插入 vector 容器中
return IDcache[set] = Setcache.size() - 1; // 计算当前下标赋值给 map容器 并返回
}
完全体
#include <iostream> // 经典输入输出
#include <set>
#include <vector>
#include <map>
#include <stack>
#include <string> // 取指令需要
#include <algorithm>
#include <iterator> // inserter 需要
#define ALL(x) x.begin(),x.end()
#define ITE(x) inserter(x,x.begin())
using namespace std;
typedef set<int> Set;
map<Set, int> IDcache;
vector<Set> Setcache;
stack<int> ans;
int ID(Set set);
int main()
{
int n = 0;
cin >> n;
string cmd;
for (int i = 0; i < n; i++)
{
cin >> cmd;
if (cmd[0] == 'P') ans.push( ID( Set() ) );
else if (cmd[0] == 'D') ans.push(ans.top());
else {
Set x1 = Setcache[ans.top()]; ans.pop();
Set x2 = Setcache[ans.top()]; ans.pop();
Set x;
if (cmd[0] == 'U') set_union(ALL(x1), ALL(x2), ITE(x));
if (cmd[0] == 'I') set_intersection(ALL(x1), ALL(x2), ITE(x));
if (cmd[0] == 'A')
{
x = x2;
x.insert(ID(x1));
}
ans.push(ID(x));
}
cout << Setcache[ans.top()].size() << endl;
}
}
int ID(Set set)
{
if (IDcache.count(set)) return IDcache[set];
Setcache.push_back(set);
return IDcache[set] = Setcache.size() - 1;
}
技术性总结
相比上次的 vector 应用，这回操作实现并不复杂，数据类型的组织反而复杂起来了
使用了 map set stack 这几个新的容器，收获丰富
还有宏定义的手法，又能摸鱼了（？）
用时一个下午，做题 + 写总结