集合栈计算机(The SetStack Computer, UVa12096)

Dear 丶 2022-05-19 14:09 157阅读 0赞

题目:
有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈,并且支持以下操作:
*PUSH:空集“{ }“入栈
*DUP:把当前栈顶元素复制一份后再入栈
*UNION:出栈两个集合,然后把二者的并集入栈。
*INTERSECT:出栈两个集合,然后把二者的交集入栈。
*ADD:出栈两个集合,然后把先出栈的集合加入到后出栈的集合中,把结果入栈。
每次操作之后,输出栈顶集合的大小(即元素个数)。例如:栈顶元素是A={ { },{ { }} },下一个元素是B={ { },{ { { }}} },则:
UNION操作得到:{ { },{ { }},{ { { }}} },输出3.
INTERSECT操作得到:{ { } },输出1.
ADD操作得到:{ { }, { { { }}}, { { },{ { }}} }.,输出3

分析
本题的集合并非简单的整数或字符串集合,而是集合的集合。很难直接表示,所以为方便起见,为每个不同的集合分配一个唯一的ID
,则每个集合表示为所包含元素(集合)的ID集合。这样就可以用STL中的set<int>来表示,而整个栈则是一个stack<int>

  1. 在进行操作时,使用map将每种集合与对应ID相关联,既可完成查找ID,也可判定是否出现新集合。
  2. 使用vector作为存储每种集合的cache,当map中没有相应的ID时,向vector加入一个set<int>元素,并将下标作为ID进行唯一标识。
  3. 使用vector将Set存储:可以用ID查询到对应的set。这样通过map和vector实现set到ID的双射。
  4. 最后 ,输出栈顶集合的大小(元素个数)。

AC代码如下:

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm> //set_union函数定义在其中
  4. #include<set>
  5. #include<map>
  6. #include<vector>
  7. #include<stack>
  8. #define ALL(x) x.begin(),x.end()
  9. #define INS(x) inserter(x,x.begin())
  10. using namespace std;
  11. typedef set<int> Set; //每个集合表示为所包含元素的ID集合
  12. map<Set,int> IDcache; //把集合映射成ID(用map将每种集合与对应的ID关联起来)
  13. vector<Set> Setcache; //根据ID取集合。
  14. //查找给定集合x的ID。如果找不到,分配一个新的ID
  15. int ID(Set x) {
  16. if(IDcache.count(x)) return IDcache[x];
  17. Setcache.push_back(x); //添加新集合
  18. return IDcache[x] =Setcache.size()-1; //将ID值加入map,同时返回新分配的ID值。
  19. }
  20. int main(){
  21. stack<int> s;
  22. int n,t;
  23. string op;
  24. scanf("%d",&t);
  25. while(t--){
  26. cin>>n;
  27. for(int i=0;i<n;i++){
  28. cin>>op;
  29. if(op[0]=='P') s.push(ID(Set()));
  30. else if(op[0]=='D') s.push(s.top());
  31. else{
  32. Set x1=Setcache[s.top()];s.pop();
  33. Set x2=Setcache[s.top()];s.pop();
  34. Set x;
  35. if(op[0]=='U')set_union(ALL(x1),ALL(x2),INS(x));
  36. if(op[0]=='I')set_intersection(ALL(x1),ALL(x2),INS(x));
  37. if(op[0]=='A'){ x=x2;x.insert(ID(x1));}
  38. s.push(ID(x));
  39. }
  40. cout<<Setcache[s.top()].size()<<endl;
  41. }
  42. printf("***\n");
  43. }
  44. return 0;
  45. }

解释说明:

  1. 对任意集合s(类型是上面定义的Set),IDcache[s]就是其ID,而Setcache[ IDcache[s] ]就是其s本身。
  2. ALL和INS两个宏分别表示:“所有的内容”和”插入迭代器” .

发表评论

表情:
评论列表 (有 0 条评论,157人围观)

还没有评论,来说两句吧...

相关阅读

    相关 集合计算机

     有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈,并且支持以下操作: PUSH:空集“\{\}”入栈 DUP:把当前栈顶元素复制一份后再入栈