本文共 1728 字，大约阅读时间需要 5 分钟。
题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=42064
#include #include #include #include #include #include #include #define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())using namespace std;/*************************************************************************************************************** 题意：利用栈模拟一些操作 学习： 1，不定长数组vector，集合set，映射map，栈stack的综合应用，非常好的一道题 2， a,利用set符合集合的特性来做集合的容器 b,利用映射来给每个集合设置唯一的编号 id c,利用不定长数组和集合编号 id 可以轻易的访问到每个集合 d,将每个集合的编号入栈，保存处理极为方便 3， algorithm库里面的内置交集，并集函数，注意参数和用法 4， 刚开始很难想到怎么处理空集，最后明白，空集也是一种特殊的集合，在全局定义一个set，将它作为一个 特殊集合处理即可，初始化空集编号为-1 5， 一个小技巧： 对于输入的每条指令，如果首字母可以当作唯一标识字符。 那么可用 op[0] == 'P' 代替 op == "PUSH";这样可能会降低消耗吧，毕竟比较两个string要调用C++库函数的***************************************************************************************************************/set Set; //集合,利用set的 1，不重复性 （恰好就是集合的特性）map ,int > ID; //集合和集合编号一一对应，每个集合有唯一的编号。空集编号为-1vector > Setcache; //根据id取集合int fuc(set x){ if(ID.count(x)) //如果集合 x 已经保存过，直接返回编号 return ID[x]; Setcache.push_back(x); //否则将集合入队列 Setcache 且映射集合编号 return ID[x]=Setcache.size()-1; //映射集合编号，从0开始}int main(){ int T; cin>>T; while(T--) { int n; cin>>n; stack s; //栈，将集合编号入栈 for(int i = 1;i <= n;i ++){ string op; cin>>op; if(op[0] == 'P') s.push(fuc(Set)); else if(op[0] == 'D') s.push(s.top()); else{ set x1=Setcache[s.top()]; s.pop(); set x2=Setcache[s.top()]; s.pop(); set x; if(op[0] == 'U') set_union(ALL(x1),ALL(x2),INS(x)); //内置并集函数 if(op[0] == 'I') set_intersection(ALL(x1),ALL(x2),INS(x)); //内置交集函数 if(op[0] == 'A'){ x=x2; x.insert(fuc(x1)); } s.push(fuc(x)); } cout< <
转载于:https://www.cnblogs.com/Jstyle-continue/p/6351976.html