Uva 12096.The SetStack Computer

558


嗯……这道题大思路很明显,但是细节好烦人……

大体上就是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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论