一道综合set，map，stack的STL题目，非常有意思！！（当然确实有一点绕）

 

 

UVA12096  AC码

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<set>
#include<stack>
using namespace std;

int n,m;
typedef set<int> jihe;//栈（sta）里存的都是int，而int所代表的集合里也是int
map<jihe,int> quanzhi;
vector<jihe>idinsetout;
stack<int>sta;//栈（sta）里存的都是int(表示集合)，因为是集合套集合所以集合里也是int(表示另一集合)


#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

int setinidout(jihe c)
{
    if(quanzhi.count(c)) return quanzhi[c];//之前写的是：idinsetout.count(c)，被绕晕了
    idinsetout.push_back(c);           //（第一次忘了这个）在vector里新加上一个
    return quanzhi[c]=idinsetout.size()-1;//他的角标就是他的权值（这两步新建集合）
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>m;
        for(int j=1;j<=m;j++)
        {
            string s;
            cin>>s;
            if(s[0]=='P') sta.push(setinidout(jihe()));//这里jihe()
            else if(s[0]=='D') sta.push(sta.top());//stack和vector的push操作有区别
            else
            {
                jihe a=idinsetout[sta.top()];
                sta.pop();
                jihe b=idinsetout[sta.top()];
                sta.pop();
                jihe x;
                if(s[0]=='U') set_union (ALL(a),ALL(b),INS(x));
                if(s[0]=='I') set_intersection (ALL(a),ALL(b),INS(x));
                if(s[0]=='A') {x=b;x.insert(setinidout(a));}
                sta.push(setinidout(x));
            }
            cout<<idinsetout[sta.top()].size()<<endl;
        }
        cout<<"***"<<endl;
    }
}

 

 

 

 

很多要注意的点