[SHOI2007]SETSTACK 集合堆栈机

第一行只有一个整数n（0 ≤ n ≤ 2000），代表将要执行的指令条数。接下来有n行，每行有包含一条大写的指令，我们保证每条指令都是上述五条指令中的一条，并且虚拟机总是能正确执行完所有的指令。

C++11(clang++ 3.9) 解法, 执行用时: 759ms, 内存消耗: 21608K, 提交时间: 2019-03-16 13:07:47

#include<bits/stdc++.h>
using namespace std;
struct cmp{
    inline bool operator()(const set<int>&a,const set<int>b){
        if(a.size()!=b.size())return a.size()<b.size();
        set<int>::iterator ita=a.begin(),itb=b.begin();
        while(ita!=a.end()&&*ita==*itb)++ita,++itb;
        return ita==a.end()?false:(*ita<*itb);
    }
};
stack<int>stk;
map<set<int>,int,cmp>mp;
vector<set<int> >vec;
inline int findid(set<int>x){
    if(mp[x])return mp[x];
    vec.push_back(x);
    return mp[x]=vec.size()-1;
}
int main(){
    string s;
    int q;
    scanf("%d",&q);
    while(q--){
        cin>>s;
        if(s[0]=='P')stk.push(findid(set<int>()));
        else if(s[0]=='D')stk.push(stk.top());
        else{
            set<int>x1=vec[stk.top()],tmp;
            stk.pop();
            set<int>x2=vec[stk.top()];
            stk.pop();
            if(s[0]=='U')set_union(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(tmp,tmp.begin()));
            else if(s[0]=='I')set_intersection(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(tmp,tmp.begin()));
            else tmp=x2,tmp.insert(findid(x1));
            stk.push(findid(tmp));
        }
        cout<<vec[stk.top()].size()<<'\n';
    }
    return 0;
}

详情