UVA12096 The SetStack Computer 栈的应用 好题

题意翻译

对于一个以集合为元素的栈，初始时栈为空。 输入的命令有如下几种： PUSH：将空集{}压栈 DUP：将栈顶元素复制一份压入栈中 UNION：先进行两次弹栈，将获得的集合A和B取并集，将结果压栈 INTERSECTION：先进行两次弹栈，将获得的集合A和B取交集，将结果压栈 ADD：先进行两次弹栈，将获得的集合A和B中，先出栈的集合（如A先）加入到后出栈的集合，将结果压栈 输出每一步操作后栈顶集合的元素的个数。

感谢@UKE自动机 提供的翻译

题目描述

​​PDF​​

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例#1： 复制

2
9
PUSH
DUP
ADD
PUSH
ADD
DUP
ADD
DUP
UNION
5
PUSH
PUSH
ADD
PUSH
INTERSECT

输出样例#1： 复制

0
0
1
0
1
1
2
2
2
***
0
0
1
0
0
***

分析：

把集合变成数字，集合里套集合，就转变成装数字了。
vector保存不同的集合，每个元素是set<int>，下标代表集合的编号。
map:帮助快速得到集合的编号
 

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int N=200;
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
typedef set<int> Set;
map<Set,int>IDcache; //集合映射成数字编号
vector<Set>Setcache; //
int ID(Set x)     //加快查询速度，返回x的编号
{
  if(IDcache.count(x))
  {
    return IDcache[x];
  } 
  Setcache.push_back(x);//添加新集合
  return IDcache[x]=Setcache.size()-1;
}
int main()
{
  
  int T;
  cin>>T;
  int n;
  while(T--)
  {
  scanf("%d",&n);
  stack<int>s;
  for(int i=1;i<=n;i++)
  {
    string str;
    cin>>str;
    if(str[0]=='P')   s.push(ID(Set()));
    else if(str[0]=='D') s.push(s.top());
    else
    {
      Set x1=Setcache[s.top()];s.pop();
      Set x2=Setcache[s.top()];s.pop();
      Set x;
      if(str[0]=='U') set_union(ALL(x1),ALL(x2),INS(x));
      if(str[0]=='I') set_intersection(ALL(x1),ALL(x2),INS(x));
      if(str[0]=='A') {x=x2;x.insert(ID(x1));}
  
      s.push(ID(x));
    }
    printf("%d\n",Setcache[s.top()].size());
  }
  cout<<"***"<<endl;
    }
}