[Shoi2007]Setstack 集合堆栈机

Time Limit:1000MS Memory Limit:65536K
Total Submit:22 Accepted:8

Description

中学数学里集合的元素往往是具体的数字，比如A = {1,2,3}，B = {}（空集）等等。但是要特别注意，集合的元素也可以是另一个集合，比如说C = {{}}，即说明C有且仅有一个元素——空集B，所以称B是C的子集或者称B是C的元素都是正确的。所谓一个集合的势，就是这个集合的元素个数，一般记为|S|，空集的势为0。在上例中，|A| = 3，|B| = 0，|C| = 1。
鉴于集合论是现代数学的基础理论这一事实，一群异想天开的科学家开始着手建造一台新式的超级计算机——集合堆栈机Alpha，这台机器操作的将是集合而不是数字。不过由于Alpha的竣工之日遥遥无期，科学家们希望你为他们编写一台虚拟机，好让他们检查自己的原型设计是否合理。
Alpha的存储设备只有一个栈，栈的每个单元都只能放置一个集合。一开始，栈是空的，在每个操作结束后，计算机就会输出位于栈顶单元的那个集合的势。Alpha拥有五种不同的指令，分别为：PUSH、DUP、UNION、INTERSECT和ADD，他们的功能如下：

Input

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

Output

输出虚拟机的输出结果即可。每行输出一个大于或等于0的整数，代表虚拟机执行该条指令后的输出。选手们务必仔细考量程序的执行效率。

Sample Input

Sample Output

Hint

对于20%的数据，n ≤ 10。
对于100%的数据，n ≤ 2000。

Source
额。。这道题目只要给每个集合设计一个Hash函数就好办了。。我看oimaster大神说的是
全部xor一个值然后乘起来。。然后我自己也想了一个。。就是把所有的子集的Hash值排序一下
然后直接效仿Rabin—Karp..关键是如果这么搞全是0.。。所以再加个修正值。。。神奇的1A囧。。
Code：
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define All(x) x.begin(),x.end()
const int seed=13331;
using namespace std;
typedef unsigned long long ull;
typedef vector<ull> set;
ull Code(const set&s)
{
    ull ret=0;
    rep(i,s.size())ret*=seed,ret+=s[i]+78;
    return ret;
}
void Normal(set&s)
{
    sort(All(s));
    s.resize(unique(All(s))-s.begin());
}
stack<set> S;
int main()
{
    int n;scanf("%d",&n);char cmd[10];set a,b;
    while(n–)
    {
        scanf("%s",cmd);
        switch(cmd[0])
        {
            case ‘P’:S.push(set());break;
            case ‘D’:S.push(S.top());break;
            case ‘A’:a=S.top();S.pop();b=S.top();S.pop();b.pb(Code(a));
                    Normal(b);S.push(b);break;
            default:a=S.top();S.pop();b=S.top();S.pop();set c(a.size()+b.size());
                if(cmd[0]==’U’)c.resize(set_union(All(a),All(b),c.begin())-c.begin());
                else c.resize(set_intersection(All(a),All(b),c.begin())-c.begin());
                Normal(c);S.push(c);break;
        }
        printf("%dn",S.top().size());
    }
}

001011222

9PUSHDUPADDPUSHADDDUPADDDUPUNION