链接:

http://codeforces.com/gym/100722/attachments/download/3466/20062007-northwestern-european-regional-contest-nwerc-2006-en.pdf

set的重要性...

题意:

给你一个空序列(栈),你要进行5个操作:

1,(P)在栈顶加一个空集合

2,(D)弹出栈顶,加入两个与其一样的集合(复制一份)

3,(I)弹出顶上两个,压入交集

4,(U)弹出顶上两个,压入并集

5,(A)弹出顶上两个,把先弹出的作为一个元素加入到第二个集合内

每次操作完了求顶端集合的大小

================================

STL的函数不全好用啊,set_union和set_insection好难用..

百度一下,你就知道...

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
set<long long> que[2005];
long long hash(set<long long> &a)
{
    long long hash_val=0;
    set<long long>::iterator ii;
    for (ii=a.begin();ii!=a.end();ii++)
    {
        hash_val*=10007;
        hash_val+=(*ii)+233;
    }
    return hash_val;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        int front=0;
        int n;
        scanf("%d",&n);
        int i;
        for (i=0;i<n;i++)
        {
            static char a[1005];
            scanf("%s",a);
            if (a[0]=='A')
            {
                front--;
                que[front-1].insert(hash(que[front]));
            }
            else if (a[0]=='D')
            {
                que[front]=que[front-1];
                front++;
            }
            else if (a[0]=='I')
            {
                set<long long> temp;
                set_intersection(que[front-2].begin(),que[front-2].end(),que[front-1].begin(),que[front-1].end(),inserter(temp,temp.begin()));
                front--;
                que[front-1]=temp;
            }
            else if (a[0]=='P')
            {
                que[front++]=set<long long>();
            }
            else if (a[0]=='U')
            {
                set<long long> temp;
                set_union(que[front-2].begin(),que[front-2].end(),que[front-1].begin(),que[front-1].end(),inserter(temp,temp.begin()));
                front--;
                que[front-1]=temp;
            }
            printf("%d\n",que[front-1].size());
        }
        printf("***\n");
    }
    return 0;
}