526互联

uva12096集合栈计算机 The SetStack Computer

发布时间 2023-12-05 10:20:14作者: 黑屿白

洛谷链接集合栈计算机 The SetStack Computer - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

一道典型的以栈为背景的数据结构题。题目简单但是程序却并不简单（个人观点）。普及组的难度有点低了感觉。

个人认为这道题目可以帮助自己熟悉或者说更好的掌握STL的使用以及妙用。

难点：1、首先出栈入栈的是集合，如果单纯的使用set的话会出现set<set<set<...>>>的情况。所以用一个ID 代替一种集合的想法就显而易见了（很值得学习）。

2、并集交集的实现。两种方法，一种是自带的函数set_union(取并集)、set_intersection（取交集）、set_difference（取差集）。

有兴趣可以了解关于C++中使用set_union、set_intersection、set_difference，set_symmetric_difference、merge的总结-CSDN博客，其中也展现了如果不用自带函数该咋做。

#include<bits/stdc++.h>
using namespace std;
typedef set<int> Set;  //类型定义使代码更简洁 
map<Set,int> ID;   //由map映射来表示一个集合的ID 
vector<Set> idsearch;  //由idsearch的右边界来表示ID，其次还可以根据idsearch[i]可以取出对应的Set 
int IDsearch(Set x){ //查找ID 
    if (ID.count(x)) return ID[x];
    idsearch.push_back(x);
    return ID[x]=idsearch.size()-1;
}
int main(){
    stack<int> Stack; //栈 
    int t;
    cin>>t;
    while(t--){
        int n;string s;
        cin>>n;
        for (int i=0;i<n;i++){
            cin>>s;
            if (s[0]=='P') Stack.push(IDsearch(Set()));
            else if (s[0]=='D') Stack.push(Stack.top());
            else {
                Set x1=idsearch[Stack.top()];Stack.pop();
                Set x2=idsearch[Stack.top()];Stack.pop();
                Set x;
                if (s[0]=='U') set_union(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));  //取并集 
                if (s[0]=='I') set_intersection(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));//取交集 
                if (s[0]=='A') {x=x2;x.insert(IDsearch(x1));}
                Stack.push(IDsearch(x));
            }
            cout<<idsearch[Stack.top()].size()<<endl;
        }
        cout<<"***"<<endl;
    }
    return 0;
}

Ps:个人认为是一道很有价值的题目