The SetStack Computer UVA12096（集合栈计算机）

ゝ一世哀愁。 2024-02-17 18:47 53阅读 0赞

解题思路：本题是集合的集合，通过唯一的ID编号(int)对应于相应的集合，typedef set<int> set1 自定义集合类型，map<set1，int>映射出ID; 把所有不相同的集合存放在vector<set1> vec容器当中， 然后通过ID号获得集合（vec\[id\]）。

1.  \#include<cstdio>
2.  \#include<string>
3.  \#include<map>
4.  \#include<set>
5.  \#include<vector>
6.  \#include<stack>
7.  \#include<algorithm>
8.  \#include<iostream>
9.  using namespace std;
10.   
    
11. \#define ALL(x) x.begin(),x.end() //宏
12. \#define INS(x) inserter(x,x.begin())
13.   
    
14. typedef set<int> set1; //自定义集合类型
15. map<set1,int>mp; //把集合印成ID
16. vector<set1>vec; //根据ID取集合
17.   
    
18. int ID(set1 s)\{ //查找给定集合s的ID，如果找不到，分配一个新的ID
19.  if(mp.count(s))return mp\[s\];
20.  vec.push\_back(s);
21.  mp\[s\]=vec.size()-1;
22.  return mp\[s\];
23. \}
24.   
    
25. int main()\{ 
26.  int T;
27.  scanf("%d",&T);
28.  while(T--)\{ 
29.  stack<int>st;
30.  int n;
31.  scanf("%d",&n);
32.  for(int i=0;i<n;i++)\{ 
33.  string str;
34.  cin>>str;
35.  if(str\[0\]=='P')st.push(ID(set1()));
36.  else if(str\[0\]=='D')st.push(st.top());
37.  else \{ 
38.  set1 s1=vec\[st.top()\];st.pop();
39.  set1 s2=vec\[st.top()\];st.pop();
40.  set1 s;
41.  if(str\[0\]=='U') set\_union(ALL(s1),ALL(s2),INS(s));
42.  if(str\[0\]=='I') set\_intersection(ALL(s1),ALL(s2),INS(s));
43.  if(str\[0\]=='A')\{ 
44.  s=s2,s.insert(ID(s1));
45.  \} 
46.  st.push(ID(s));
47.  \}
48.  cout<<vec\[st.top()\].size()<<endl;
49.  \}
50.  cout<<"\*\*\*"<<endl;
51.  \}
52.  return 0;
53. \}

本题旨在锻炼思维，其中内容涉及到宏，超出了目前为止我所学的，所以我们现在只需理解成“类似于函数的东西”

另外用到STL中内置的集合操作（set\_union和 set\_intersection）位于头文件<algorithm>中.