嗯……这道题大思路很明显,但是细节好烦人……
大体上就是stack+set
对于栈中的元素,可以发现每个元素都是一个集合(set),而集合中的元素也是集合
因此,应该对每个集合(元素)进行编号 typedef set<int> element
,这样就能把每个元素看作保存整数的栈 stack s;
用map和vector进行映射集合(元素)和编号
map<element,int> ID_eache;
vector<int> ID_eache2;
然后再按照要求写就行了
其中可用switch case
判断操作。
要注意每个case
都需要 break;
因为case只是入口,并不是出口。只要进去后,没有break就会一直运行下去
#include <cstdio> #include <set> #include <stack> #include <iostream> #include <map> #include <vector> using namespace std; class LOVE{ private: int n; typedef set<int> element; stack <int> s; map<element,int> ID_cache; vector<element> ID_cache2; int ID(element x){ if(ID_cache.count(x))return ID_cache[x]; ID_cache2.push_back(x); return ID_cache[x]=ID_cache2.size()-1; } public: void start(){ scanf("%d",&n); char com[10]; while(n--){ scanf("%s",com); element temp1,temp2,temp3; element::iterator it1,it2,it; switch(com[0]){ case 'P': s.push(ID(element())); break; case 'D': s.push(s.top()); break; case 'U': temp1=ID_cache2[s.top()]; s.pop(); temp2=ID_cache2[s.top()]; s.pop(); for(it=temp2.begin();it!=temp2.end();it++) temp1.insert(*it); s.push(ID(temp1)); break; case 'I': temp1=ID_cache2[s.top()]; s.pop(); temp2=ID_cache2[s.top()]; s.pop(); for(it1=temp1.begin();it1!=temp1.end();it1++){ for(it2=temp2.begin();it2!=temp2.end();it2++){ if(*it1==*it2){ temp3.insert(*it1); temp2.erase(*it2); break; } } } s.push(ID(temp3)); break; case 'A': temp1=ID_cache2[s.top()]; s.pop(); temp2=ID_cache2[s.top()]; s.pop(); temp2.insert(ID(temp1)); s.push(ID(temp2)); break; } cout<<ID_cache2[s.top()].size()<<endl; } } }; int main(){ //freopen("in.txt","r",stdin); int n; scanf("%d",&n); while(n--){ LOVE LIVE; LIVE.start(); printf("***\n"); } return 0; }