uva12096
用于对于集合的操作
algorithm库
set_union合并2个集合,求并集
set_intersection求2个集合的交集
都可以使用于任何类型
//对于set #include<iostream> #include<set> #include<algorithm> #include<vector> using namespace std; int main() {
set<int> a,b,c; for(int i=1;i<=10;i++) a.insert(i); for(int i=2;i<=11;i++) b.insert(i); set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin()));//inserter for(auto x:c) cout<<x<<endl; return 0; }
讯享网
讯享网//对于vector #include<iostream> #include<set> #include<algorithm> #include<vector> using namespace std; int main() {
vector<int> a,b,c; for(int i=1;i<=10;i++) a.push_back(i); for(int i=2;i<=11;i++) b.push_back(i); set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin()));//inserter for(auto x:c) cout<<x<<endl; return 0; }
//输出结果 1 2 3 4 5 6 7 8 9 10 11
set_intersection
讯享网//set_intersection #include<iostream> #include<set> #include<algorithm> #include<vector> using namespace std; int main() {
vector<int> a,b,c; for(int i=1;i<=10;i++) a.push_back(i); for(int i=2;i<=11;i++) b.push_back(i); set_intersection(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin()));//inserter for(auto x:c) cout<<x<<endl; return 0; }
2 3 4 5 6 7 8 9 10
这个题是一个关于集合的运算,所以容易想到set
然后这个集合运算是对于栈的,但是set又只可以表示一个集合
首先题中要进行的操作有
1,空集入栈
2.栈顶再入栈
3,4,5都是先从栈中出2个,然后进行合并,交集,连接等操作后入栈
所以栈顶是一个集合,但是里面的元素可能也是集合
所以考虑把所有集合映射一下,于是用到了map,把每一个集合映射成一个int,现在需要考虑的就是映射成怎样的int
考虑到进行映射后,只能通过集合知道ID,但是是需要取集合的,所以用一个vector来保存集合,然后把ID映射成下标
然后每个集合保存的其实是他包含的集合的ID
讯享网#include<iostream> #include<set> #include<vector> #include<stack> #include<algorithm> #include<map> #include<string> using namespace std; /* 首先把每一个集合用map映射到了一个ID,那么这个stack就是一个关于ID的,那么就还需要一个把ID映射到集合的 这里用的是vector,里面的元素是集合,为了好引用,所以把集合映射到下标 */ stack<int> stk;//把每一个不同的集合映射成一个唯一的ID,所以栈就可以是一个int的,他保存的是一个集合的ID vector<set<int>> vec;//保存每一个集合,通过下标也就是集合对应的ID取集合 map<set<int>,int> ID;//把集合映射成ID int get_ID(set<int> t) {
if(ID.count(t)) return ID[t]; vec.push_back(t); return ID[t]=vec.size()-1; } int main() {
int t; cin>>t; while(t--) {
int n; cin>>n; while(n--) {
string op; cin>>op; if(op[0]=='P') stk.push(get_ID(set<int>()));//set<int>()表示空集 else if(op[0]=='D') stk.push(stk.top()); else {
set<int> a=vec[stk.top()]; stk.pop(); set<int> b=vec[stk.top()]; stk.pop(); set<int> res; if(op[0]=='U') set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(res,res.begin())); else if(op[0]=='I') set_intersection(a.begin(),a.end(),b.begin(),b.end(),inserter(res,res.begin())); else if(op[0]=='A') res=b,res.insert(get_ID(a)); stk.push(get_ID(res)); } cout<<vec[stk.top()].size()<<endl; } cout<<"*"<<endl; } return 0; }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/80036.html